Binary Search Tree(이진 탐색 트리)

이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성을 가지고 있습니다.

• 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함됩니다
• 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함됩니다.
• 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 여야합니다.
• 중복된 키를 허용하지 않습니다.

검색/삽입 시간복잡도

위에서 검색/삽입 연산을 살펴보시면 아시겠지만, 모든 원소를 탐색하지 않는것이 특징입니다.

최악의 경우는 트리의 높이 만큼 탐색하는 경우라 볼 수 있겠습니다.

따라서 높이가 H 인경우의 검색/삽입의 시간 복잡도는 O(H) 입니다.

하지만, 시간복잡도는 원소의 개수로 표기할 때, 조금 더 좋은 표현이라 할 수 있습니다.

H 를 원소의 개수 N 으로 표현해볼 수 없을까요?

이진 트리는 대개, 원소의 개수가 N 이면 log_2Nlog2​N 으로 치환 가능합니다.

이진 검색트리 구조가 완전 이진 트리라 가정할 때의 경우로 한정적이긴 합니다. 그래서 최악의 경우로 규정짓는 빅오 표기법으로는 애매하긴 합니다.

따라서, 검색/삽입 연산의 시간복잡도는 O(log_2N)O(log2​N)으로 표기 가능합니다.

삭제 시간복잡도

삭제 시간복잡도는 왜 따로 다룰까요?

검색/삽입과 동일하게 다룰 수 없는 찜찜한 구석이 있지 않았나요?

네 맞습니다. 삭제할 노드의 자식 노드가 2개인 경우 에는 추가 연산이 있기에 시간 복잡도를 다시 따져봐야 할거 같습니다.

검색 시간복잡도는 O(H) 로 삭제할 대상을 검색하는 것도 동일하게 시간이 소모됩니다.

이때, 삭제할 노드가 단말 노드, 삭제할 노드의 자식 노드가 1개 인 경우는 지우거나 참조값만 붙여주면 되므로, O(1) 의 시간이 소모된다고 볼 수 있습니다. 따라서 총 시간 복잡도는 O(H + 1) → O(H) 라 할 수 있겠네요.

그렇다면 우리가 궁금한 삭제할 노드의 자식 노드가 2개 인 경우는 어떨까요?

검색 후, 대체할 노드만 찾는다면 대체 노드의 참조값만 바꿔주면 되므로 O(1) 입니다.

그말은, 대체할 노드를 찾는게 얼마나 걸리는지에 따라 시간 복잡도가 규정 된다는 점입니다.

생각해보자면, 대체할 노드를 찾는것도 결국 탐색이 필요합니다. 다만 Full-Tree 가 아닌 Sub-Tree 에서의 검색이지요. 시간복잡도를 간단하게 정의해본다면 O(H-K) 정도가 될것입니다.

K 는 탐색을 시작할 높이 값입니다.

시간복잡도는 최악의 경우를 생각해야 하므로, 최악의 경우의 K는 0 이 되는 경우가 있겠네요.

이 경우는 루트를 지운다는 의미입니다.

결국 서브트리를 탐색하는 시간복잡도도 O(H) 라 생각할 수 있겠습니다.

정리해보자면, 아래의 작업이 필요합니다.

• 삭제 노드를 탐색 O(H)

• 대체 노드를 찾기 위한 서브 트리를 탐색 O(H)

• 참조값 변경 O(1)

따라서 삭제 연산의 시간 복잡도는 O(H + H + 1) → O(2H) → O(H) 라 볼 수 있습니다. 위에서 N으로 치환한것과 마찬가지로 O(log_2N)O(log2​N) 으로 표기 가능하겠습니다.

결론적으로 탐색/삽입/삭제 시간복잡도는 전부 동일하게 O(log_2N)O(log2​N) 라고 정의할 수 있습니다.