이진 검색 트리(BST)

📌 이진 검색 트리

이진 검색 트리(BST, Binary Search Tree)는 널리 사용되는 형태의 이진 트리입니다.
왼쪽 노드 <= 부모 노드 <= 오른쪽 노드 의 관계를 가집니다. 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고 크거나 같은 원소는 항상 오른쪽에 있기 때문에 원소 검색을 위한 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어들게 됩니다.

BST가 마지막 레벨을 제외한 모든 노드에 두 개의 자식 노드가 있을 경우, 트리의 높이는 log_2N 입니다(N은 원소의 개수). 즉 시간복잡도는 O(log N)을 가집니다. 이런 형태의 이진 트리를 완전 이진 트리(complete binary tree)라고 합니다.

🔸 BST 원소 검색

위 트리에서 7을 검색하기 위해서는 현재 노드보다 왼쪽 노드의 값이 작고 오른쪽 노드의 값이 크다는 것을 기억해야 합니다. 7은 루트 노드인 12보다 작기 때문에 왼쪽 노드로 향하고 자식 노드에서도 7보다 작은 값이면 왼쪽, 큰 값이면 오른쪽으로 이동합니다.

12 - 10 - 8 - 4 -7

모든 원소를 방문하지 않아도 되기 때문에 검색 범위가 반으로 줄어드는 것을 알 수 있습니다.

🔸 BST 원소 삽입

원소의 삽입도 검색과 비슷한 접근 방식을 이용합니다. 루트 노드에서부터 추가할 원소와 비교하며 내려갑니다. 추가될 원소 18은 17보다 크기 때문에 오른쪽 자식 노드에 추가할 수 있습니다.

🔸 BST 원소 삭제

루트 노드 12를 삭제하고 싶을 때, BST에서 원소를 삭제하는 것은 단순 노드를 삭제하는 것에서 끝나는 것이 아니라 노드 삭제 후 다른 적절한 노드로 삭제된 노드를 대체해야 합니다.
첫 번째로 삭제할 노드를 찾습니다. 그 후 세 가지 경우를 살펴봅니다.

• 자식 노드가 없는 경우 : 단순히 해당 노드 삭제
• 자식 노드가 하나만 있는 경우 : 노드 삭제 후, 부모 노드의 포인터가 해당 자식 노드를 가리키도록 조정
• 자식 노드가 두 개 있는 경우 : 노드 삭제 후, 현재 노드를 후속 노드(successor, 현재 노드 다음으로 큰 숫자를 가진 노드)로 대체

12의 오른쪽 서브 트리는 18 아래 부분의 트리입니다. 여기서부터 시작하여 왼쪽 자식 노드로 이동하면 15가 나타나는데, 15 노드는 왼쪽 자식이 없고 오른쪽 자식 노드는 16을 가지고 있으므로 15보다 큽니다. 그렇기에 12의 후속은 15가 됩니다. (후속 노드는 오른쪽 자식 노드 하나만 가질 수 있습니다.)
12를 15로 대체하려면 12를 먼저 지우고 후속 노드의 값으로 덮어씌웁니다. 그런 다음 원래 15가 있던 후속 노드를 삭제하면 아래 그림처럼 나타납니다.

🔸 트리 연산의 시간 복잡도

검색의 경우 이론적으로는 검색 범위가 절반으로 줄어든다고 할 수 있습니다. N개의 노드를 가지고 있는 BST에서 검색에 필요한 시간은 T(N)=T(N/2)+1 로 표현할 수 있습니다. 시간 복잡도로 T(N)=O(log N) 입니다.
그러나 트리의 모양은 원소 삽입 순서에 따라 결정됩니다. 그래서 검색 범위가 절반으로 줄어드는 것도 항상 성립되는 것은 아니기에 시간 복잡도 또한 정확하다고 보기 어렵습니다.
👉🏻 균형 트리에서 해결책에 대해 설명.

🔸 BST 코드 구현

코드 보러가기