이진 검색 트리(BST)

이진 검색 트리(BST, Binary Search Tree)는 널리 사용되는 형태의 이진 트리입니다.

이진 검색트리의 특징

부모 노드의 값 >= 왼쪽 자식 노드의 값

부모 노드의 값 <= 오른쪽 자식 노드의 값

 

이러한 관계식은 원소 검색을 위해 루트노트부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어듭니다.

BST가 마지막 레벨을 제외한 모든 노드에 두 개의 자식 노드가 있을 경우 이 트리의 높이는 log2N이 됩니다. 여기서 N은 원소의 개수를 나타냅니다. 이로 인해 BST의 검색 및 삽입 동작은 O(log N)의 시간 복잡도를 갖습니다. 

이러한 형태의 이진 트리를 완전 이진 트리(complete binary tree)라고 합니다.

 

 

이진 검색 트리에서  숫자 7을 찾기 위한 과정

루트노드와 7을 비교한다. 찾으려는 숫자 7은 12보다 작기 떄문에 왼쪽 자식노드로 이동한다.

왼쪽 자식노드 10과 7을 비교한다. 숫자 7은 10보다 작기 때문에 왼쪽 자식노드로 이동한다.

왼쪽 자식노드 8과 7을 비교한다. 숫자 7은 8보다 작기 때문에 왼쪽 자식노드로 이동한다.

왼쪽 자식노드 4와 7을 비교한다. 숫자 7은 4보다 크기 떄문에 오른쪽 자식노드로 이동한다.

오른쪽 자식노드 7과 7을 비교한다. 7을 찾았다!

 

BST에 새 원소 삽입하기

원소18추가

새로운 원소를 추가하려면 먼저 원소가 삽입될 위치의 부모 노드를 찾아야 합니다. 루트 노드부터 시작하여 각 노드를 추가할 원소와 비교하면서 원소가 삽입될 위치로 이동해야 합니다.

 

 

BST에서 원소 삭제하기

이번에는 BST에서 원소를 삭제하는 방법에 대해 알아보겠습니다.

삭제할 노드를 찾는 것이 첫 번쨰 단계입니다. 그 후 세가지 경우를 따져봐야 합니다.

 

자식 노드가 없는 경우

단순히 해당 노드를 삭제하면 됩니다.

 

자식 노드가 하나만 있는 경우

노드 삭제 후, 부모 노드의 포인터가 해당 자식 노드를 가리키도록 조정합니다.

 

자식 노드가 두 개 있는 경우

노드 삭제 후, 현재 노드를 후속 노드(successor)로 대체합니다.

 

여기서 후속 노드란 현재 노드 다음으로 큰 숫자를 가진 노드를 말합니다. 즉, 현재 원소보다 큰

원소들 중에서 가장 작은 원소를 의미합니다. 

가장 작은 노드를 찾으려면 현재 노드의 오른쪽 서브 트리로 이동한 후, 여기서 가장 작은 값을 찾으면 됩니다. 서브 트리에서 가장 왼쪽에 위치한 노드로 이동하면 됩니다.

 

 

1번 과정

그림에서 12를 삭제하려고 합니다.

2번 과정

후속노드인 15를 삭제할 노드에 복사합니다.

3번 과정

12를 삭제하고 후속 노드인 15를 삭제한 위치에 복사하고 후속노드 자리는 오른쪽 자식노드가 대체하게 됩니다. 후속노드는 오른쪽 자식노드만 가질 수 있습니다. 왼쪽 자식노드가 있다면 그것은 후속노드가 아닐겁니다. 이유는 삭제 할 노드보다 큰 노드중에 가장 작은 노드가 후속 노드이기 떄문에 삭제할 노드의 오른쪽 자식노드로 이동후 가장 왼쪽에 있는 자식노드가 후속노드이기 때문입니다.

 

트리 연산의 시간 복잡도

검색

매번 검색할 때마다 범위가 절반으로 줄어든다고 할 수 있습니다. T(N) = T(N/2) + 1

시간 복잡도로 표현하면 O(log N)입니다.