트리와 이진 탐색 트리 2

트리와 이진 탐색 트리에서 본 트리(tree) 용어와 순회(traversal)를 바탕으로, "왼쪽은 작고 오른쪽은 크다"는 규칙을 더한 이진 탐색 트리(binary search tree)를 이어서 다룬다. 이 규칙 덕분에 정렬 상태를 유지하면서 빅오 표기법(Big-O notation)으로 O(log n), 곧 데이터가 두 배가 되어도 비교가 한 번쯤만 느는 시간에 찾지만, 트리가 한쪽으로 치우치지 않았을 때만 그렇다. 그래서 스스로 높이를 맞추는 트리와, 디스크를 위해 키를 여러 개 담는 트리까지 본다.

이진 탐색 트리

이진 탐색 트리의 규칙은 "모든 노드(node)에서, 왼쪽 서브트리(subtree)의 모든 값은 그 노드보다 작고 오른쪽 서브트리의 모든 값은 그 노드보다 크다"이다. 바로 아래 자식만이 아니라 서브트리 전체에 적용된다는 점이 중요하다. 아래 트리가 이 규칙을 지킨다.

다이어그램 로딩…

• 탐색: 루트 노드(root node)에서 시작해 찾는 값이 작으면 왼쪽, 크면 오른쪽으로 내려간다. 한 번 비교할 때마다 한 층씩 내려가므로 비용은 트리 높이 h(루트에서 가장 깊은 노드까지 내려가는 간선 수)에 비례하는 O(h)다.
• 삽입: 탐색하듯 내려가다 빈자리(null)를 만나면 그 자리에 새 노드를 단다.
• 삭제: 지울 노드의 자식 수에 따라 세 경우로 나뉜다.
  • 자식이 없으면 그냥 떼어 낸다.
  • 자식이 하나면 그 자식을 지운 노드 자리로 올린다.
  • 자식이 둘이면 오른쪽 서브트리에서 가장 작은 노드, 즉 중위 순회(inorder traversal)에서 바로 다음에 오는 **후속자(inorder successor)**를 찾는다. 후속자의 값을 지울 노드에 복사한 뒤 후속자를 지운다. 후속자는 오른쪽 서브트리에서 가장 작은 노드라서 더 작은 값을 담을 왼쪽 자식이 있을 수 없고, 그래서 앞의 두 경우 중 하나로 쉽게 지워진다. 왼쪽 서브트리에서 가장 큰 노드인 선행자(inorder predecessor)를 써도 된다.

치우치면 O(n), 그래서 균형 트리

O(h)가 O(log n)이 되려면 트리가 고르게 퍼져 있어야 한다. 노드 n개가 고르게 퍼지면 높이는 약 log₂ n이다. 하지만 1, 2, 3, 4, 5처럼 정렬된 순서로 넣으면 매번 오른쪽에만 붙어 편향 이진 트리(skewed binary tree)가 되고, 높이가 n − 1이 되어 탐색이 O(n)으로 떨어진다. 연결 리스트(linked list)를 앞에서부터 훑는 것과 다를 바 없다.

균형 트리(balanced tree)는 삽입·삭제 때마다 스스로 모양을 고쳐 높이가 O(log n)을 넘지 않게 한다. 모양을 고치는 기본 동작은 회전(rotation)이다. 회전은 부모와 자식의 위아래를 맞바꾸고 서브트리 하나를 옮겨 다는 작업이다. 이때 중위 순회 순서, 즉 크기 순서는 그대로 유지되면서 한쪽 높이만 줄어든다.

다이어그램 로딩…

회전 뒤에도 중위 순회는 여전히 1, 2, 3이다. 크기 순서는 그대로이고 높이만 줄었다.

• AVL 트리(AVL tree): 모든 노드에서 왼쪽·오른쪽 서브트리의 높이 차이가 1 이하가 되도록 회전한다. 균형이 엄격해 탐색이 빠르지만, 삽입·삭제 때 회전이 잦다.
• 레드-블랙 트리(red-black tree): 노드에 빨강·검정 색을 칠하고 핵심 규칙 두 가지를 지킨다. 빨간 노드가 연달아 나오지 않고, 어느 노드에서든 그 아래 리프 노드(leaf node)까지 가는 모든 길에 검은 노드 수가 같다. 그 결과 가장 긴 경로가 가장 짧은 경로의 두 배를 넘지 않아 높이가 O(log n)이다. AVL 트리보다 덜 엄격해 삽입·삭제 때 고칠 일이 적다. Java의 TreeMap이 레드-블랙 트리이며, 찾기·넣기·지우기에 log(n) 시간을 보장한다고 Java 공식 API 문서에 적혀 있다.

B-Tree: 디스크를 위한 트리

이진 트리(binary tree)는 노드 하나에 비교 기준이 되는 값(키, key)을 하나만 담아서, 노드가 백만 개면 높이가 20 안팎이다. 메모리에서는 괜찮지만, 데이터가 디스크에 있으면 노드 하나를 읽을 때마다 디스크를 한 번 읽어야 한다. 디스크 읽기는 메모리 읽기보다 몇 자릿수 느리므로 20번은 너무 많다. B-Tree는 노드 하나에 키를 여러 개 담고 자식도 여러 개 두는 다분기 균형 트리다. 키와 노드 크기에 따라 다르지만 흔히 노드 하나에 키가 수백 개 들어가서, 수천만 건도 3~4단계면 닿을 만큼 트리가 낮다. 그만큼 디스크 읽기 횟수가 크게 준다. 데이터베이스 인덱스(index, 원하는 행을 전부 훑지 않고 빨리 찾도록 키를 정렬해 따로 저장해 둔 구조)가 이 구조를 쓰며, 자세한 것은 B-Tree 구조와 키 변경에서 다룬다.

면접 포인트

• "이진 탐색 트리의 시간 복잡도(time complexity)는?" → O(h). 균형이면 O(log n), 치우치면 O(n).
• "정렬된 데이터를 넣으면?" → 편향 트리가 되어 O(n). 그래서 AVL 트리·레드-블랙 트리 같은 균형 트리로 회전해 높이를 유지.
• "자식이 둘인 노드는 어떻게 삭제하나요?" → 중위 후속자(오른쪽 서브트리 최솟값)로 값을 바꾸고 후속자를 삭제.
• "AVL vs 레드-블랙" → AVL은 엄격한 균형(탐색 유리), 레드-블랙은 느슨한 균형(삽입·삭제 유리, TreeMap).
• "DB 인덱스는 왜 이진 트리가 아니라 B-Tree인가요?" → 노드당 키가 많아 높이가 낮고 디스크 읽기가 적다.