Binary Search Tree

필요한 기능:  IsEmpty(), Search(key), Insert(key, value), Delete(key)

Search(), Insert(), Delete()의 시간복잡도

Hash Table, Binary Search Tree, Balanced Binary Search Tree간 시간복잡도 비교

각 노드는 key와 value로 구성되어있고, root의 왼쪽 subtree의 키는 항상 root의 key보다 작으며 오른쪽은 root의 key보다 큼

Indexed Binary Search Tree는 key,value이외에 left subtree의 node개수도 저장 

InOrder로 읽으면 sort된 배열의 key가 나옴

Binary search tree를 밸런싱하기 위한 방법으로는 AVL tree와 RB tree가 있음