많은 트리 모습 중, 가장 많이 사용하는 이진 트리와 이진 탐색 트리에 대해 알아보자.
이진 트리(Binary tree)
먼저, 이진 트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리로, 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.
이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리, 완전 이진 트리, 포화 이진 트리로 나뉜다.
이진 트리의 특징
- 정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
- 포화 이진 트리(Perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리다.
- 완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.
이러한 이진 트리는 이진 탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용된다.
이진 탐색 트리 (Binary Search Tree = BST)
이진 탐색 트리란 이진 탐색(binary search)과 연결 리스트(linked list) 결합한 이진트리를 말한다. 이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.
- 각 노도에 중복되지 않은 키가 있다.
- 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
- 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
- 좌우 서브트리도 모두 이진 탐색 트리여야 한다.
즉 이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다. 다음 사진이 이진 탐색 트리라고 할 수 있다.
이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다. 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.
이진 탐색 트리 특징
이진 탐색 트리는 기존 이진 트리보다 탐색이 빠르다는 장점이 있다. 이진 탐색 트리의 연산은 트리의 높이가 h라면 o의 복잡도를 가지게 된다.
이진 탐색 트리의 탐색 과정은 다음과 같다.
- 루트 노드의 키와 찾고자 하는 값을 비교한다. 만약 찾고자 하는 값이라면 탐색을 종료한다.
- 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
- 찾고자 하는 값이 루트 노드으 ㅣ키보다 크다면 오른쪽 서브 트리를 탐색한다.
이 과정을 찾고자 하는 값을 찾을 때까지 반복해 진행한다. 만약 값을 찾지 못한다면 그대로 연산을 종료하게 된다.
여기서 하나 중요한 점은, 트리 안에 찾고자 하는 값이 없더라도 최대 h번의 연산 및 탐색이 진행된다는 것이다.
