마지막으로 자식이 두 개 있는 루트 노드 6을 삭제한 후 전위 순회를 해 보겠습니다. 잘 작동한다면 노드 6의 대체 노드 5가 루트가 되고 노드 6은 사라져야 합니다.
코드 8-11
bst.delete(6)
bst.preorder_traverse(bst.get_root(), f)
실행 결과만 확인해 보겠습니다.
key 6 is deleted
5 3 2 4 8 10 9 11
노드 6이 삭제되었고 노드 5가 루트가 된 것을 알 수 있습니다. 전체 실행 결과는 다음과 같습니다.
****************************************************************************************************
2 3 4 5 6 8 9 10 11
searched key : 8
prev key : 6
next key : 9
MIN(bst) : 2
MAX(bst) : 11
key 6 is deleted
5 3 2 4 8 10 9 11
****************************************************************************************************
이로써 이진 탐색 트리를 모두 구현해 보았습니다. 이진 탐색 트리 연산들의 빅오는 무엇일까요? 트리 높이가 h일 때 삽입, 삭제, 검색 모두 O(h)입니다. 우리는 평균적으로 트리 높이 h가 log n이라고 짐작합니다. 그리고 대부분의 경우 이는 맞습니다. 하지만 특별한 경우에 이진 탐색 트리의 빅오는 O(n)이 됩니다. 대체 언제일까요?