개념
이진 탐색 트리(Binary search tree)는 맵의 엔트리를 저장하기에 훌륭한 자료구조이다. 이진 탐색 트리는 트리의 일종으로 한 엔트리 (k, v)에 대해 다음과 같은 특성을 같는다.
- k보다 작거나 같은 값을 갖는 노드는 v의 왼쪽 서브 트리에 저장된다.
- k보다 크거나 같은 값을 갖는 노드는 v의 오른쪽 서브 트리에 저장된다.
이진 탐색 트리는 비어 있는 외부 노드를 어떻게 표현하더라도 순서화된 맵을 표현한다. 즉, 이진 탐색 트리는 부모-자식 간의 관계를 사용하여 그 키의 순서를 계층적으로 표현할 수 있다. 특히 이진 탐색 트리를 중위 순회(Inorder traversal)하면 맵의 키들을 오름차순으로 방문할 수 있다.
추상 데이터 타입(ADT)
- find(k): 근(root) 노드에서 탐색을 시작한다. k와 키 값을 비교하여 k가 작으면 왼쪽 서브트리를 계속 탐색하고, 같으면 탐색을 종료하고 해당 노드의 iterator를 반환한다. k가 크면 오른쪽 서브트리를 탐색한다. 만약 외부 노드에 도달하게 되면 탐색은 실패하고 NULL을 반환한다.
- insert(k, e): 원소 e와 키값 k를 갖는 항목을 삽입한다.
- remove(k): 키값 k가 존재하면 이 값을 가지는 항목을 삭제한다. 그러한 항목이 없으면 에러를 발생한다.
AVL 트리(AVL 트리)
이진 탐색 트리는 맵을 효과적으로 탐색하는 자료구조이다. 그러나 최악의 경우에 이진 탐색 트리의 탐색 시간은 선형 리스트와 같다. AVL 트리는 모든 맵의 연산에 대해 로그 시간에 도달하는 자료구조이다. AVL 트리는 높이-균형 특성(height-balance property)를 갖는다. 높이-균형 특성에 의해 AVL 트리의 모든 내부 노드 v에 대해 v의 자식 노드들의 높이 차는 1이다. 따라서 AVL의 서브트리도 AVL 트리이다.
스플레이 트리(Splay Tree)
스플레이 트리(Splay Tree)는 이진 탐색 트리의 균형을 유지하기 위해 명시적인 규칙을 사용하지는 않는다. 대신 연산을 할 때마다 스플레이를 한다. 스플레이 트리는 탐색을 할 때 키가 발견되면 그 노드를 스플레이한다. 발견되지 않으면 실패한 외부 노드와 부모 노드를 스플레이한다. 삽입을 할 때 새로 삽입한 노드를 스플레이한다. 삭제를 할 때 삭제된 내부 노드의 부모 노드를 스플레이한다.
다분기 탐색 트리(Multi-Way Search Tree)
다분기 탐색 트리(Multi-Way Search Tree)는 내부 노드가 두 개 이상의 자식을 가지는 트리이다. v를 순서화된 트리의 노드라고 하자. v가 d개의 자식들을 갖는다면 v를 d-노드(d-node)라고 할 때, 다분기 탐색 트리는 다음과 같은 특성을 갖는다.
- 트리의 각 내부 노드는 최소한 두 개의 자식을 갖는다. 즉 d≥2인 경우 각 내부 노드는 d-노드이다.
- 자식 v1, ..., vd를 갖는 트리의 각 내부 d-노드 v는 d-1개의 정렬된 항목(k1, x1), ..., (kd-1, xd-1)를 저장한다.
- 관습적으로 k0=-∞와 kd=+∞로 정의한다. vi(i=1, ..., d)를 루트로 하는 v의 서브트리의 노드에 저장된 각 항목 (k, x)에 대해 부등식 ki-1≤k≤ki를 갖는다.
(2, 4) 트리((2,4) Tree)
각 노드에 저장된 보조적인 자료구조를 작게 유지하고 주 다분기 트리를 균형적으로 유지하는 다분기 탐색 트리를 (2, 4) 트리라고 한다. (2, 4) 트리의 특성은 다음과 같다.
- 크기 속성(Size Property): 모든 노드는 많아야 네 개의 자식을 가진다.
- 깊이 속성(Depth Property): 모든 외부 노드는 동일한 깊이를 가진다.
적색-흑색 트리(Red-Black Tree)
AVL 트리와 (2, 4) 트리가 훌륭한 특성을 많이 가진다 하더라도 재구성 연산에 많은 시간이 소요된다. 반면에 적색-흑색 트리(Red-Black Tree)는 단지 균형을 유지하기 위해 갱신 후 발생되는 구조적 변화가 O(1)에 그친다. 적색-흑색 트리의 특성은 다음과 같다.
- 루트 속성(Root Property): 루트는 흑색이다.
- 외부 속성(External Property): 모든 외부 노드는 흑색이다.
- 내부 속성(Internal Property): 적색 노드의 자식은 흑색이다.
- 깊이 속성(Depth Property): 모든 외부 노드는 흑색 조상의 개수에서 1을 뺀 수로 정의되는 동일한 흑색 깊이(black depth)를 가진다.
댓글