Binary Search Tree
-
Binary Search Tree자료구조 2019. 9. 2. 17:24
필요한 기능: IsEmpty(), Search(key), Insert(key, value), Delete(key) Search(), Insert(), Delete()의 시간복잡도 각 노드는 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가 있음