2-3-4 트리

🟩 다음 성질을 만족하는 균형 탐색 트리

2-노드 👉 1개의 키와 2개의 자식을 갖는 노드

3-노드 👉 2개의 키와 3개의 자식을 갖는 노드

4-노드 👉 3개의 키와 4개의 자식을 갖는 노드

 

각 노드의 한 키와 왼쪽 서브트리에 있는 모든 키 값은 그 키 값보다 작다.

각 노드의 한 키와 오른쪽 서브트리에 있는 모든 키 값은 그 키 값보다 크다.

 

🌟 노드의 구조

 

🟩 탐색

 

🟩 삽입

탐색 과정에서 4-노드를 만나면 항상 노드 분할을 우선 수행

 

🌟 노드 분할

노드 분할의 유형

부모가 2-노드인 4-노드인 경우 👉 중간 키를 부모로 보내어 3-노드에 연결된 2개의 2-노드로 변환

부모가 3-노드인 4-노드인 경우 👉 4-노드에 연결된 2개의 2-노드로 변환

루트가 4-노드인 경우 👉 3개의 2-노드로 변환 & 루트의 분할은 트리의 높이를 하나 증가시킴

 

 

EX) 50 55 30 10 45 15 20 25 35 40

 

🟩 시간복잡도

균형 탐색 트리 👉 O(logn)

 

🟩 삽입/삭제가 일어나도 경사 트리가 되지 않음

루트 노드가 분할되는 경우에 한해서 모든 노드의 레벨이 동일하게 1씩 증가

 

🟩 특징

2-3-4 트리를 그대로 구현하면 노드 구조가 복잡해서 이진 탐색 트리보다 더 느려질 가능성이 많음

모든 리프 노드의 레벨은 동일