이진 트리에서는 하나의 Node 가 1개의 key(data) 와 2개의 자식 node 를 가리키는 link(left,right) 를 가지고있습니다. BST(이진 탐색 트리)는 검색, 삽입, 삭제은 평균 O(log n) 의 시간 복잡도를 가집니다. 하지만 최악의 경우 편향이진트리(구글 이미지 검색) 생성되면 최악의 효율O(n)이 발생합니다. 이를 보완하고 좌우 균형을 맞추어 탐색 효율을 목적으로 B tree라는 것을 사용합니다. 아래의 java 소스코드는 해외 블로그를 참고하였습니다. 탐색,삽입 하는 코드는 비교적 간결하고, 트리의 node 를 삭제하는 logic 은 3가지로 분류 됩니다. 삭제 node 의 자식이 없는 경우 - node 를 바로 삭제 합니다. 삭제 node 의 자식이 1개 인 경우 - 자..
선형 자료구조(list)는 배열로 구현하는 방법과 여러 객체(Node) 생성하고, 포인터로 연결하여 구현하는 방법이 있습니다. 신속한 삽입과 삭제를 허용하는 순서 리스트를 유지해야 할 경우에는 후자의 방법으로 리스트를 구현하고, 이것을 연결리스트라 합니다. Node class(list의 각 항목) class Node { public int data; public Node next; Node (int data){ // 생성자 this.data = data; } Node (int data,Node next){ // 2번째 생성자 this.data = data; this.next = next; } } Node 클래스는 자기 참조(self) 형태입니다. 하나의 node 는 data 와 Node 객체를 참조하는 ..
Tree(트리) 트리는 어떤 속성을 만족하는 node(노드)와 방향 간선의 집합입니다. 또한, 하나의 노드가 root 노드를 가리키는 사이클 없는 그래프로 정의할 수 있습니다. 위키피디아 Tree Terminology(전문 용어) Root : 부모가 없는 노드(트리의 가장 상위 노드) Leaf : 차수가 0인 노드 Root-to-leaf path(루트 경로) : 루트로부터 해당 노드까지의 유일한 경로 Size of tree (트리의 크기) : 연결된 모든 node의 개수 Subtree(서브 트리) : 자식 node 가 있을 때 이 노드를 root로 하는 tree (level 이 1 줄어듭니다.) Height of tree : 최장 루트 경로의 길이 단독트리 : 노드가 1개이고 높이는 0인 트리 (NIL)..
Heap(히프) Heap 은 root 가 최대값인 max-heap, 최소값인 min-heap이 있는데 다른 언급이 없으면 max-heap 을 의미합니다. heap은 아래에서 위로 순서를 가지고 있는 이진 트리이므로 모든 leaf-root path 를 따라 가는 순회는 오름차순으로 key 를 방문합니다. 이것은 어떠한 key도 부모보다 크지 않다고 말하는 것과 같습니다. 히프화 알고리즘은 2 * log n 번 이상의 비교를 하지 않습니다. 히프화 알고리즘은 특정 노드를 root로 하는 서브트리에 대해 heap 특성이 만족됩니다. 가장 하위 내부 노드 부터 시작하여 root 에 이르기까지 각각의 x 에 대한 이 연산을 반복함에 의해 전체 트리를 히프화할 수 있습니다. 이러한 과정을 히프 구축(Heap Bui..