edubun English
홈›프로그래밍›자료 구조

이진 탐색 트리

키 1,023개짜리 균형 잡힌 이진 탐색 트리는 어느 키든 비교 10번 안에 찾지만, 정렬된 순서로 넣어 만들면 같은 키에 1,023번이 걸릴 수 있습니다.

모양에 담긴 이진 탐색

정렬된 배열에서 이진 탐색을 하면 약 log₂ n번 확인으로 키를 찾지만, 정렬된 배열에 넣으려면 값을 옮겨야 합니다. 해시 테이블은 빨리 넣지만 순서를 잊어서 가장 작은 키나 40 다음 키를 쉽게 알려 주지 못합니다. 이진 탐색 트리(BST)는 둘 다를 노립니다. 연결 리스트처럼 노드로 이루어지지만, 노드마다 left와 right 두 포인터가 있습니다. 맨 위 노드가 뿌리(root)이고, 자식이 없는 노드가 잎(leaf)입니다.

규칙 하나가 이것을 탐색 트리로 만듭니다. 어느 노드에서든 왼쪽 서브트리의 키는 모두 더 작고, 오른쪽 서브트리의 키는 모두 더 큽니다. 키를 찾을 때는 뿌리에서 출발해 비교합니다. 같으면 찾은 것이고, 작으면 왼쪽, 크면 오른쪽으로 갑니다. 비교 한 번마다 서브트리 하나를 통째로 버리는데, 이진 탐색이 목록 절반을 버리는 것과 같습니다. 50, 30, 70, 20, 40, 60, 80으로 된 트리에서 60을 찾으면 50, 70, 60과 비교하므로 비교 3번입니다.

넣기도 같은 길을 따라갑니다. 필요한 쪽 포인터가 비어 있을 때까지 왼쪽이나 오른쪽으로 가서 그 자리에 새 노드를 붙입니다. 45를 넣으면 50(왼쪽으로), 30(오른쪽으로), 40(오른쪽으로)과 비교하는데, 40에는 오른쪽 자식이 없으므로 45가 그 자리에 들어갑니다. 잎이 아닌 노드를 지울 때는 생각이 하나 더 필요합니다. MIT 노트는 그 항목을 순서상 바로 앞이나 뒤의 키와 바꾼 뒤 그 자리에서 지웁니다. 실험실의 세는 규칙은 길 위의 노드마다 비교 한 번입니다.

불러오는 중

끌어서 돌리고, 휠이나 두 손가락으로 확대하세요.

이진 탐색 트리입니다. 키를 고르고 넣거나 찾아 보세요. 지나간 길에 색이 들고 숫자는 비교 횟수를 보여 줍니다. 처음 트리를 「정렬된 입력」으로 바꾸면 같은 키 일곱 개가 긴 사슬이 됩니다.

높이가 전부를 정합니다

탐색에 비교가 몇 번까지 걸릴까요? 층마다 많아야 한 번이므로 비용은 트리의 높이에 달려 있습니다. 높이는 뿌리에서 잎까지 가장 긴 길에 있는 간선의 수입니다. MIT 노트는 이를 트리 연산이 O(h) 시간에 돈다고 적습니다. 50, 30, 70, 20, 40, 60, 80 트리는 높이가 2이므로 어떤 탐색도 비교 3번을 넘지 않습니다. 노드 1,023개짜리 완전히 균형 잡힌 트리는 높이가 9이고 많아야 10번이면 됩니다.

그런데 모양은 넣는 순서에 달려 있습니다. 10, 20, 30, 40, 50, 60, 70을 정렬된 순서로 넣으면 키마다 앞의 모든 키보다 커서 새 노드가 매번 마지막 노드의 오른쪽에 붙습니다. 트리는 높이 6인 사슬이 되고, 70을 찾는 데 비교 7번이 걸립니다. 포인터가 더 붙은 연결 리스트인 셈입니다. 정렬된 키 1,023개라면 가장 나쁜 탐색이 10번이 아니라 1,023번입니다.

균형 트리는 넣거나 지울 때마다 스스로 모양을 고쳐서 이 문제를 풉니다. 처음 나온 방법은 1962년 게오르기 아델손벨스키와 예브게니 란디스의 AVL 트리로, MIT 7강에서 다룹니다. AVL 트리는 모든 노드에서 두 서브트리의 높이 차이를 1 이하로 유지하고, 어긋나면 회전이라는 작은 국소 조작으로 바로잡습니다. 그래서 높이가 O(log n)으로 유지되고, 키가 어떤 순서로 오든 찾기, 넣기, 지우기가 O(log n)입니다.

저절로 나오는 정렬 순서

BST는 키가 있는지 없는지보다 많은 것을 기억합니다. 왼쪽 서브트리, 노드, 오른쪽 서브트리 순서로 재귀적으로 방문하면 키가 정렬된 순서로 나옵니다. 이 중위 순회(MIT는 traversal order라고 부릅니다)로 BST는 「가장 작은 키」, 「가장 큰 키」, 「40 다음 키」에 답합니다. MIT 집합 인터페이스의 순서 연산으로, 해시 테이블은 이것을 빨리 하지 못합니다.

뿌리와 잎뿌리는 맨 위 노드, 잎은 자식이 없는 노드.
BST 성질모든 노드에서 왼쪽 서브트리 키는 작고 오른쪽은 큼.
높이뿌리에서 잎까지 가장 긴 길의 간선 수. 탐색은 많아야 높이 + 1번 비교.
AVL 트리균형 BST(1962). 서브트리 높이 차이 1 이하, 회전으로 바로잡음.
중위 순회왼쪽, 노드, 오른쪽 순서. 키를 정렬된 순서로 나열.
  1. 이진 탐색 트리의 성질은 어느 것일까요?
    • 모든 노드에 자식이 정확히 둘이다
    • 모든 노드에서 왼쪽 서브트리 키는 작고 오른쪽은 크다
    • 키가 넣은 순서대로 저장된다
    • 뿌리가 가장 작은 키다
  2. 50, 30, 70, 20, 40, 60, 80으로 만든 트리에서 60을 찾으면 비교가 몇 번일까요?
  3. 같은 트리에서 없는 키 45를 찾으면 비교가 몇 번일까요?
  4. 그 트리에 45를 넣으면 어디에 들어갈까요?
    • 50의 왼쪽 자식
    • 40의 오른쪽 자식
    • 60의 왼쪽 자식
    • 30의 오른쪽 자식
  5. 50, 30, 70, 20, 40, 60, 80 트리의 높이는?
  6. 10, 20, 30, 40, 50, 60, 70을 이 순서로 넣었습니다. 70을 찾으면 비교가 몇 번일까요?
  7. 노드 1,023개짜리 완전히 균형 잡힌 BST(높이 9)에서 탐색 비교는 최대 몇 번일까요?
  8. 50, 30, 70, 20, 40 트리를 중위 순회하는 순서대로 키를 놓으세요.
  9. 처음 나온 균형 트리 방법을 제안한 사람과 해는?
    • 아델손벨스키와 란디스, 1962년
    • 룬, 1953년
    • 바우어와 자멜존, 1957년
    • 커누스, 1998년
  10. BST는 빨리 답하지만 일반 해시 테이블은 그렇지 못한 질문은?
    • 40이 들어 있나?
    • 40 다음 키는 무엇인가?
    • 칸이 몇 개인가?
    • 40 mod 7은?
핵심 정리
  • BST의 모든 노드에서 작은 키는 왼쪽, 큰 키는 오른쪽에 있습니다.
  • 찾기와 넣기는 길 하나를 따라가며 비교는 많아야 높이 + 1번입니다.
  • 정렬된 입력은 사슬을 만들고(키 7개, 높이 6), AVL(1962) 같은 균형 트리는 높이를 O(log n)으로 지킵니다.
  • 중위 순회는 키를 정렬된 순서로 나열합니다.
이 과정의 출처 (5)
  • MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon), lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append), 4 Hashing (chaining, pigeonhole collisions, chain length n/m), 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
  • MDN Web Docs, Array.prototype.shift (shifts all values left by 1), Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
  • ECMAScript 2025 Language Specification (tc39.es/ecma262), 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements"), Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
  • D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
  • "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).

확인한 날: 2026-10-18