8. 이진 탐색 트리 (Binary Search Tree)
2020.10.13
내부노드에 (키, 원소) 쌍을 저장하며, 아래 조건을 만족하는 적정 이진 트리를 이진 탐색 트리라 한다. $u, v, w$가 모두 트리 노드이며, $u$와 $w$가 각각 $v$의 왼쪽과 오른쪽 부트리에 존재할 때, $\text{key}(u) key(v): # 찾는 k 보다 v가 작음 return treeSearch(v.right, k) # 더 큰 원소들이 있는 오른측 탐색 삽입 삽입에 앞서, 적절한 삽입 위치를 찾기위해 treeSearch로 $k$를 찾아준다. 당연히 $k$는 없겠지만, 이때 찾아진 위치에 외부 노드를 추가하여 삽입 위치로 쓰면 된다. def insertItem(k, e): w = treeSearch(root(), k) if isInternal(w): raise Exception("Key..