8. Binary Search Trees

binary tree이다. 뭐 ancestor, descendant 다양한 용어가 있지만 쉬우니 넘어가자

높이가 H인 full tree는 2**h - 1개의 노드를 갖는다.

N개 노드를 가질때 최대/최소 높이:
최대 높이는 일렬로 노드가 늘어설 때 이므로 N이고 최소 높이는 full tree일때 이므로 log(N+1)이다. 

linked list 와 binary tree, 서치 시간복잡도 비교
둘다 최악의 경우 O(N)으로 똑같음 ㄷ

색다른 binary tree: 오른쪽 루트노드는 중간보다 크고 왼쪽은 작음, 서치 시간 복잡도 O(logN)으로 링크드 리스트보다 효율적임

CountNodes(recursive)

졸라 간단하다. 복잡하게 생각할 수 도있으나 이렇게 간단하게 짤 수 있으니 알아둘 것.

RetrieveItem

대소비교해서 걍 찾으면 됨. 대소비교하고 다시 recursive 써서 함수 불러서 또 대소비교 하는 거임

Insert (recursive)

reference type을 이용하면 tree->info = item 만 해줘도 알아서 그 전꺼랑 붙음

DeleteItem

(1) leaf를 지울때 => 걍 지우면 그만임
(2) one child node를 지울때 => 지우고 이어줘야 됨
(3) two children node를 지울때 => 먼저 지울 자리에 들어올 대체자 구한다음에 바꾸고 지워야됨

Print

왼쪽 tree먼저 프린트하고 가운데하고 오른쪽 프린트하는 순서이다.

Constructor

root=NULL;

Destructor

딱봐도 왼쪽지우고 오른쪽지우고 가운데 지우는 순서이다.

CopyTree

왼쪽 먼저 복사하고 오른쪽 복사하는 코드이다.

Traversal

1) Inorder Traversal: 왼중오
2) Postorder Traversal: 왼오중
3) Preorder Traversal: 중왼오

Big-O comparison

Array 

center node: tree.nodes[index]
right child: tree.nodes[index*2+2]
left child: tree.nodes[index*2+1]
parent: tree.nodes[(index-1)/2]

Definition

Full Binary Tree: all of the leaves at same level and nonleaf node has two children
Complete Binary Tree: full or full through the next-to-last level, leaf는 왼쪽부터 채워넘