알고리즘 - 2-3-4 트리

2-3-4 트리 (2-3-4 Tree)

이진 탐색 트리(1개의 키, 2개의 링크)에서 발생하는 최악의 상황을 방지하기 위해 다음과 같이 자료구조를 변경

- 트리에 있는 하나의 노드가 하나 이상의 키를 가질 수 있음

- 3-노드(2개의 키, 3개의 링크)와 4-노드(3개의 키, 4개의 링크)를 허용

- 트리의 균형에 대해 신경 쓰지 않아도 완벽한 균형 트리가 만들어 짐

 

 

 

 

 

 

분할 과정

1. 루트가 4-노드인 경우

- 세 개의 2-노드로 변환

- 루트의 분할은 트리의 높이를 하나 증가시킴

2. 부모가 2-노드인 4-노드의 경우

- 중간 키를 부모로 보내여 3-노드에 연결된 두 개의 2-노드로 변환

3. 부모가 3-노드인 4-노드의 경우

- 4-노드에 연결된 두 개의 2-노드로 변환

4. 4-노드가 2-3-4 트리의 루트인 경우

- 노드가 루트인 경우의 분할(Ti는 서브트리)

 

 

5. 4-노드가 2-노드의 자식인 경우의 분할

- 4-노드가 2-노드의 왼쪽 자식인 경우

 

 

-  4-노드가 2-노드의 왼쪽 중간 자식인 경우

 

 

6. 4-노드가 3-노드의 자식인 경우

- 4-노드가 3-노드의 왼쪽 자식인 경우

 

 

-  4-노드가 3-노드의 왼쪽 중간 자식인 경우

 

- 4-노드가 3-노드의 오른쪽 자식인 경우

 

 

 

 

 

 

구축 과정

- 키 삽입 ( 2, 1, 8, 9, 7, 3, 6, 4, 5 )

 

- 키 삽입 ( 2, 1, 8, 9, 7, 3, 6, 4, 5 )

 

 

성능 특성

- N-노드로 이루어진 2-3-4 트리의 탐색은 logN + 1 개 이상 노드를 방문하지 않음

- N-노드로 이루어진 2-3-4 트리의 삽입은 최악의 경우 logN + 1 개의 노드를 분할하며, 평균적으로는 하나 이하의 노드를 분할함

>> 2-3-4 트리에서 4-노드의 개수가 적음

- 일반적으로 높이가 h인 2-3-4 트리는 2h+1-1과 4h+1-1 사이의 키를 포함

- N 개의 키를 포함하는 2-3-4 트리의 높이는 [log4(N+1)]-1과 [log2(N+1)]-1 사이