이진 탐색 트리

정의

이진 탐색 트리는 노드마다 왼쪽 서브트리 키가 작고 오른쪽 서브트리 키가 큰 이진 트리다.

이 규칙은 모든 서브트리에 재귀적으로 적용된다. 그래서 탐색은 한 방향만 골라 내려간다.

키 중복을 허용할지는 구현과 문헌마다 달라 답안에 조건을 밝혀야 한다.

구조와 중위 순회

이진 탐색 트리는 노드마다 키와 최대 두 개의 자식 포인터를 가진다.

예를 들어 키 30, 20, 40, 25, 35를 넣으면 루트는 30이 된다.

중위 순회는 왼쪽, 노드, 오른쪽 순으로 방문하므로 키가 오름차순으로 나온다.

그래서 BST의 전체 키 출력에는 중위 순회가 기본이다.

탐색과 삽입

찾는 값 x는 루트 노드부터 비교한다. 비교 결과에 따라 한 방향만 골라 내려간다.

x가 작으면 왼쪽, 크면 오른쪽으로 이동하고, 같으면 그 노드를 반환한다.

자식이 NULL이면 탐색은 실패다. 이 탐색으로 빈 자리를 찾아 삽입한다.

같은 키가 이미 있으면 삽입하지 않는다. 중복 불허 정책의 기준이다.

삽입 순서와 높이

같은 키를 넣어도 삽입 순서에 따라 트리 모양과 높이가 달라진다.

30, 20, 40, 25, 35 순서는 높이 3이다. 35를 찾으려면 30, 40, 35로 3회 비교한다.

20, 25, 30, 35, 40 순서로 넣으면 높이 4가 되어 탐색 비교가 최대 5회까지 늘어난다.

정렬된 순서로 넣으면 한쪽으로 기울어 최악 O(n)의 편향 트리가 된다.

일반 BST와 자가 균형

시험에서 자주 묻는 비교는 일반 BST와 자가 균형 BST의 차이다.

일반 BST는 삽입 순서에 따라 한쪽으로 기울 수 있어 최악이 O(n)이다.

자가 균형 트리는 삽입과 삭제 때 균형 연산으로 높이를 유지해 탐색이 항상 O(log n)이다.

대표적인 예는 AVL 트리와 레드-블랙 트리다.

정답은 일반 이진 탐색 트리다. 자가 균형 트리는 회전 같은 추가 로직이 필요하다.

정리

이진 탐색 트리는 왼쪽 값이 작고 오른쪽 값이 큰 이진 트리다.

중위 순회는 오름차순을 주고, 탐색과 삽입은 평균 O(log n)이다.

편향되면 최악 O(n)이 되므로 AVL 트리나 레드-블랙 트리로 높이를 보완한다.