각 노드에 대해 왼쪽 서브트리의 값은 모두 그 노드보다 작고, 오른쪽 서브트리의 값은 모두 크도록 값을 배치한 이진 트리. 탐색·삽입·삭제는 트리의 높이에 비례하는 수고로 끝나며, 중위 순회로 따라가면 값이 오름차순으로 늘어선다.
일본어 명칭: 二分探索木
이진 탐색 트리(Binary Search Tree)은(는) 자료 구조와 알고리즘 등 1개 분야의 연습 문제 4개에 나와요.
분야: 자료 구조와 알고리즘
탐색은 루트에서 시작하여, 찾는 값이 노드보다 작으면 왼쪽, 크면 오른쪽 자식으로 나아가는 것을 일치하거나 자식이 없어질 때까지 반복합니다. 삽입은 탐색하여 자식이 없어진 위치에 새 노드를 붙입니다. 삭제는 자식이 0개나 1개이면 그 노드를 제거하고 자식을 다시 잇고, 자식이 2개이면 오른쪽 서브트리의 최솟값(또는 왼쪽 서브트리의 최댓값)으로 바꿔 놓은 다음 그 노드를 삭제합니다. 어느 조작이든 루트에서 리프까지의 단 수(트리의 높이)에 비례하는 수고입니다.
n개의 노드를 가진 이진 탐색 트리의 높이는 균형이 잡혀 있으면 약 log₂ n이지만, 1, 2, 3, …처럼 정렬된 순서로 삽입하면 한쪽으로만 뻗은 한 줄이 되어 높이는 n−1이 됩니다. 이렇게 되면 탐색은 연결 리스트와 같은 O(n)입니다. AVL 트리나 레드-블랙 트리는 삽입이나 삭제 때마다 회전이라는 조작으로 모양을 정돈하여 높이를 O(log n)으로 유지하는 균형 이진 탐색 트리로, 많은 프로그래밍 언어의 순서 있는 딕셔너리나 집합에 쓰이고 있습니다.
트리의 모든 노드를 방문하는 방법에는 노드를 먼저 방문하는 전위 순회, 왼쪽 서브트리·노드·오른쪽 서브트리 순의 중위 순회, 자식을 먼저 방문하는 후위 순회가 있으며, 단마다 방문하는 너비 우선(레벨 순서) 순회도 있습니다. 이진 탐색 트리를 중위 순회로 따라가면 값이 오름차순으로 늘어서므로, 정렬된 목록을 얻을 수 있습니다. 수식을 나타내는 트리를 후위 순회로 따라가면 역폴란드 표기법이 됩니다.
정답: A. 오름차순(작은 순서)으로 늘어선다
이진 탐색 트리에서는 어느 노드에 대해서든 왼쪽 서브트리의 값은 모두 그 노드보다 작고, 오른쪽 서브트리의 값은 모두 큽니다. 그래서 왼쪽 서브트리, 노드, 오른쪽 서브트리의 순서로 따라가면 작은 값부터 차례로 방문하게 되어 결과는 오름차순이 됩니다. 루트에서 가까운 순서로 늘어서는 것은 단마다 왼쪽부터 방문하는 너비 우선(레벨 순서) 순회입니다. 삽입한 순서는 트리의 모양에는 남지만, 순회 순서와는 일치하지 않습니다.
정답: B. 20, 40, 30, 60, 80, 70, 50
루트는 50이고, 왼쪽 자식은 30(그 자식이 20과 40), 오른쪽 자식은 70(그 자식이 60과 80)이 됩니다. 후위 순회에서는 왼쪽 서브트리의 20, 40, 30, 오른쪽 서브트리의 60, 80, 70을 방문한 다음, 마지막으로 루트 50을 방문합니다. 50, 30, 20, 40, 70, 60, 80은 노드를 먼저 방문하는 전위 순회, 20, 30, 40, …은 중위 순회의 결과입니다. 후위 순회는 자식을 먼저 처리해야 하는 트리의 삭제나, 수식 트리로부터 후위 표기법을 만들 때 쓰입니다.
이진 탐색 트리는 '왼쪽은 작고 오른쪽은 크다'라는 조건으로, 임의의 값의 탐색이나 순서대로의 열거를 할 수 있습니다. 이진 힙은 '부모가 자식보다 크다(또는 작다)'라는 조건뿐이어서 최댓값(최솟값)을 바로 꺼낼 수 있지만, 임의의 값의 탐색에는 적합하지 않습니다.
메모리 위에서 쓴다면 균형 이진 탐색 트리, 디스크나 SSD처럼 블록 단위로 읽는 기억 장치에서는 한 노드에 많은 키를 갖게 하여 트리를 낮춘 B 트리(B+ 트리)가 쓰입니다.
이진 탐색 트리에서는 어느 노드에 대해서든 왼쪽 서브트리의 값은 모두 그 노드보다 작고, 오른쪽 서브트리의 값은 모두 큽니다.
이진 탐색 트리를 중위 순회(왼쪽 서브트리, 그 노드, 오른쪽 서브트리 순으로 방문한다)로 따라갔을 때, …균형 잡힌 트리라면 단의 수는 약 log₂ 1000 ≈ 10이므로, AVL 트리나 레드-블랙 트리처럼 삽입이나 삭제 때마다 모양을 정돈하는 균형 이진 탐색 트리를 사용하면 최악에도 O(log n)을 유지할 수 있습니다.
빈 이진 탐색 트리에 1, 2, 3, …, 1000의 순서로 값을 삽입했다(균형을 잡는 조작은 하지 않는다…이진 탐색 트리에서는 1억 건이면 적어도 27단 정도가 되며, 단마다 다른 블록을 읽으면 느려집니다.
데이터베이스나 파일 시스템의 인덱스에 이진 탐색 트리가 아니라 B 트리(B+ 트리 포함)가 자주 쓰이는 주…연결 리스트(Linked List) 깊이 우선 탐색(Depth-First Search) 너비 우선 탐색(Breadth-First Search) 다익스트라 알고리즘(Dijkstra's Algorithm) 동적 계획법(Dynamic Programming) 스택(Stack) 시간 복잡도(Time Complexity) 안정 정렬(Stable Sort) 이진 탐색(Binary Search) 이진 힙(Binary Heap)