[자료 구조/알고리즘] 이진 탐색 트리
이진 트리(binary tree)란 각 노드(node)에 최대 두 개의 자식(하위) 노드가 있는(모든 노드의 차수가 2 이하인) 트리 자료 구조이다. 이진 탐색 트리(binary search tree)란 다음 두 특성을 갖는, 정렬된(ordered, sorted) 이진 트리를 말한다.
- 모든 노드는 자신의 왼쪽 브랜치에 존재하는 모든 노드의 숫자보다 큰 숫자를 갖는다. 따라서 이진 트리 상에서 최소 노드는 최상단에 있는 노드의 왼쪽 브랜치에서 가장 끝에 있는 노드가 된다.
- 모든 노드는 자신의 오른쪽 브랜치에 존재하는 모든 노드의 숫자보다 작은 숫자를 갖는다. 따라서 이진 트리 상에서 최대 노드는 최상단에 있는 노드의 오른쪽 브랜치에서 가장 끝에 있는 노드가 된다.
이진 탐색 트리는 데이터를 빠르게 조회, 삽입, 제거할 수 있는 이진 탐색(binary search)을 가능하게 한다. 이진 탐색 트리에서 탐색을 위한 노드 비교 시 트리의 약 절반의 노드를 건너뛰도록 노드들이 배치되어 있기 때문에 데이터 조회 성능은 이진 로그 O(log n)에 비례한다.
이진 탐색 트리에서 작업의 시간 복잡도는 트리의 높이에 선형적이다. 트리가 직선에 가까운 형태로 구성되어 있다면(트리의 높이가 크다면) 선형 탐색과 마찬가지로 탐색 효율이 매우 나빠지게 된다. 이러한 트리를 균형이 깨진(unbalanced) 이진 탐색 트리라고 한다. 최악의 경우 균형이 깨진 이진 탐색 트리의 조회 성능은 O(n)이 된다. 노드를 임의의 순서로 삽입할 경우 트리의 높이가 커지고 이에 따라 시간 복잡도가 증가할 수 있으므로 이를 제한하기 위해 자가 균형 이진 탐색 트리(self-balancing binary search tree)를 사용할 수 있다. 자가 균형 이진 탐색 트리는 트리에 노드를 삽입하거나 삭제할 때 자동으로 높이를 작게 유지한다. 자가 균형 이진 탐색 트리의 예로는 AVL 트리, 레드-블랙 트리(red-black tree) 등이 있다.
노드 삽입
트리에 새로운 노드를 삽입하기 위해 트리의 최상단 노드와 먼저 비교한다. 신규 노드가 최상단 노드보다 작다면 왼쪽 브랜치의 자식 노드로, 크다면 오른쪽 브랜치의 자식 노드로 내려간다. 비교 대상 노드의 자식 노드가 없다면 새로운 노드로 삽입한다.
노드 삭제
노드 삭제는 다음 경우로 구분할 수 있다. 자식 노드가 존재하는 노드를 삭제하는 경우 이진 탐색 트리의 특성을 유지해야 한다.
- 자식 노드가 없는 경우: 해당 노드를 삭제한다.
- 자식 노드가 하나인 경우: 삭제 대상 노드의 위치로 자식 노드를 이동시킨다.
- 자식 노드가 두 개인 경우: 삭제하려는 노드는 왼쪽 브랜치에 존재하는 모든 하위 노드들 중 가장 큰 숫자를 갖는 노드이다. 따라서 삭제 대상 노드의 위치로 하위의 왼쪽 브랜치 상의 최대 노드(또는 오른쪽 브랜치 상의 최소 노드)를 위치시킨다. 이동 대상 노드가 자식 노드를 갖는 경우(왼쪽 자식 노드 또는 오른쪽 자식 노드) 동일한 처리를 재귀적으로 수행한다.
레드-블랙 트리
레드-블랙 트리(red-black tree)란 자가 균형 이진 탐색 트리로서, 연관 배열, 셋 등의 자료 구조를 구현하는데 사용된다. 레드-블랙 트리에서 노드는 블랙 또는 레드의 색깔을 가지며 모든 리프 노드들은 값을 갖지 않는다. 값이 없는 리프 노드를 널 리프(null leaf)라고 한디.
레드-블랙 트리의 데이터의 삽입과 삭제, 탐색 시 시간 복잡도는 O(log n)이며 최악의 경우에도 일정한 실행 시간을 보장하므로 일반적인 이진 탐색 트리 보다 효율적이다.
힙
힙(heap) 자료 구조는 이진 트리 중 하나로서 우선순위 큐(priority queue) 자료 구조, 다익스트라(Dijkstra) 알고리즘, 힙 정렬(heap sort) 알고리즘 등의 구현에 사용된다. 힙은 완전 이진 트리(complete binary tree)에 속한다. 완전 이진 트리란 트리의 마지막 레벨을 제외하고 모든 레벨에 노드가 존재하며, 마지막 레벨의 모든 노드는 가장 왼쪽 부터
완전 이진 트리란 마지막 레벨을 제외한 모든 레벨의 노드가 완전히 채워진 상태이면서 마지막 레벨의 모든 노드가 가능한 한 왼쪽에 있는(부모 노드의 왼쪽 자식 노드인) 이진 트리이다. 따라서 완전 이진 트리 구성 시 노드는 부모 노드의 왼쪽에서 오른쪽 순으로 채워진다. 완전 이진 트리의 레벨 k에 대해 루트 레벨부터 레벨 k까지 가능한 최대 노드 수는 2k개이다. 완전 이진 트리는 항상 균형(balanced) 트리이다.
힙에는 최소 힙과 최대 힙 두 가지가 있다.
- 최소 힙 (min-heap): 트리의 루트 노드가 가장 작은 값을 가지는 힙이다. 모든 노드에 대해 모든 자식 노드의 값이 해당 노드의 값보다 크다.
- 최대 힙 (max-heap): 트리의 루트 노드가 가장 큰 값을 가지는 힙이다. 모든 노드에 대해 모든 자식 노드의 값이 해당 노드의 값보다 작다.
힙 자체는 정렬되지 않은 자료 구조이며 모든 데이터를 정렬된 순서대로 가져오기 위해서는 트리의 루트를 n번 제거해야 한다. 힙 자료 구조를 사용한 정렬 알고리즘을 힙 정렬(heap sort)이라고 한다.
Comments