이진 탐색 트리 (Binary Search Tree)

👑 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 이진 트리의 특수한 형태로, 왼쪽 서브트리의 모든 값은 부모 노드의 값보다 작고,

오른쪽 서브트리의 모든 값은 부모 노드의 값보다 큰 이진트리이다. 아래의 그림을 보면, 루트 노드인 7의

왼쪽 서브트리의 값은 모두 7보다 작고, 오른쪽 서브트리의 값은 모두 7보다 큰 것을 볼 수 있다. 또한

어떠한 노드에 대해 위의 정의를 대입해봐도 성립하는 것을 볼 수 있다.

이진 탐색 트리에서는 탐색, 삽입, 삭제를 모두 $ O(log N) $ 시간에 처리할 수 있다. 또한 해시와는 다르게

원소가 크기순으로 정렬되어 있어 관련 연산을 수행하기에 훨씬 수월하다. 또한 이진 탐색 트리를 중위 순회

하면, 정렬된 데이터를 얻을 수 있다.

💡 BST에서의 연산의 시간 복잡도

이진 탐색 트리에서의 연산의 시간 복잡도가 $ O(log N) $ 인 이유는 연산이 트리의 높이에 비례하여 수행되기

때문이다. 이진 탐색 트리의 이상적인 구성은 완전 이진 트리, 또는 포화 이진 트리의 모습을 하고 있을 때

이다. 이 경우 노드의 수를 $ n $ 이라고 할 때, 높이 $ h $ 는 다음과 같이 계산된다.

$ h = log_2(n + 1) - 1 $

삽입, 삭제, 탐색 등의 연산이 트리의 높이에 비례하여 수행된다고 했으므로, BST에서의 연산의 시간

복잡도는 $ O(log N) $ 가 되는 것이다.

하지만, 최악의 경우 트리가 한쪽으로 치우친 선형 구조가 될 수 있다. (이미 정렬된 데이터를 삽입하는 경우)

이 때, 트리의 높이 $ h $ 는 노드의 수 $ n $ 에 가까워지고, 시간복잡도가 $ O(N) $ 이 된다.

따라서, 이진 탐색 트리가 항상 $ O(log N) $ 의 성능을 유지하기 위해서는 트리가 균형 잡혀 있어야 한다.

이를 해결하기 위해 AVL 트리나 레드-블랙 트리와 같은 자가 균형 이진 검색 트리가 사용되며, 이들은 삽입

및 삭제 시 트리의 균형을 유지하여 항상 $ O(log N) $ 의 시간 복잡도를 보장한다.

💡 구현

다음은 C++로 구현한 간단한 이진 탐색 트리이다.