BST 복습

 

BST란?

 

이진 검색 트리는 널리 사용되는 형태의 이진 트리이다.

BST는 다음과 같은 속성이 있다.

 

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

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

 

즉, 왼쪽 노드 <= 부모 노드 <= 오른쪽 노드의 관계를 가진다.

 

이러한 관계식은 재미난 특징이 있는데,

부모 노드보다 적거나 같은 모든 원소는 항상 왼쪽에 있고,

부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 된다.

따라서 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 

각 단계마다 검색 범위가 절반으로 줄어든다.

 

BST가 마지막 레벨을 제외한 모든 노드에 두 개의 자식 노드가 있을 경우,

이 트리의 높이는 lon2N이 된다.

여기서 N은 원소의 개수를 나타낸다.

이로 인해 BST의 검색 및 삽입 동작은 O(log N)의 시간 복잡도를 가지게 된다.

이러한 형태의 이진 트리를 완전 이진 트리라 한다.

 

이진 검색 트리에서 원소 검색, 삽입, 삭제 방법에 대하여 알아보자.

중복되지 않는 양수를 원소르 갖는 BST가 아래 그림 같이 구성되어 있다고 가정하자.

 

이진 검색 트리에서 원소 검색

 

그림에 있는 트리에서 숫자 7을 검색하는 방법에 대해 알아보겠다.

그림에서 화살표로 표현한 것처럼 각 노드의 숫자와 비교하여 어느 하위 노드로 이동할지를 결정해야 한다.

이진 검색 트리에서 현재 노드보다 왼쪽 노드는 값이 작고, 오른쪽 노드는 값이 크다는 점을 기억해야 한다.

먼저 루트 노드와 숫자 7을 비교한다. 루트 노드 값은 12이고, 7은 12보다 작기 떄문에 왼쪽 자식 노드로 이동해야 한다.

왜냐하면 12보다 작은 값을 갖는 노드는 모두 루트 노드의 왼쪽에 있기 때문이다.

 

이후 자식 노드에서도 그 값이 7보다 적으면 왼쪽,

7보다 크면 오른쪽 자식 노드로 이동한다

결국 4노드에서 오른쪽으로 이동하여 숫자 7을 찾을 수 있다.

 

BST에 새 원소 삽입하기

이번에는 원소 삽입에 대해 알아보겠다.

BST에 새로운 원소를 삽입하는 과정을 아래 그림처럼 나타내 보았다.

그림과 같이 18을 추가하게 되면 보라색 화살표의 루트를 따라 이동하여 새로운 원소를 추가하게 된다.

 

새로운 원소를 추가하려면 먼저 원소가 삽입될 위치의 부모 노드를 찾아야 한다.

이 과정에서 설명한 원소 검색과 비슷한 접근 방식을 사용하면 된다.

즉, 루트 노드부터 시작하여 각 노드를 추가할 원소와 비교하면서 원소가 삽입될 위치로 이동해야 한다.

그럼 그림에서 보듯 새 원소를 추가하기 위해 먼저 17이 저장된 노드까지 이동했으며,

18이 17보다 크므로 17의 오른쪽 자식 노드에 18을 추가했다.

 

BST에서 원소 삭제하기

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

삭제 과정을 설명하기 위해 간간히 그림을 사용할 예정이다.

이 그림에서 12노드를 삭제하려고 한다.

BST에서 원소를 삭제하는 작업은 단순히 노드를 삭제하는 것으로 끝나는 것이 아니라,

노드 삭제 후 전체 트리가 BST 속성을 만족하도록

다른 적절한 노드로 삭제된 노드를 대체해야 하기 때문에 삽입보다 좀 더 복잡하다.

 

첫 번째 단계는 삭제할 노드를 찾는 것이다.

그 후에는 다음과 같은 세 가지 경우를 따져봐야 한다.

 

• 자식 노드가 없는 경우 : 단순히 해당 노드를 삭제하면 된다.
• 자식 노드가 하나만 있는 경우 : 노드 삭제 후, 부모 노드이 포인터가 해당 자식 노드를 가리키도록 조정한다.
• 자식 노드가 두 개 있는 경우 :: 노드 삭제 후, 현재 노드를 후속 노드로 대체한다.

여기서 후속 노드란 현재 노드 다음으로 큰 숫자를 말한다.

즉, 현재 원소보다 큰 원소들 중에서 가장 작은 원소를 의미한다.

따라서 현재 노드의 오른쪽 서브 트리로 이동한 후,

여기서 가장 작은 값의 노드를 찾으면 된다.

가장 작은 노드를 찾으려면 서브트리에서 가장 왼쪽에 위치한 노드로 이동하면 된다.