2-3 트리, 2-3-4 트리

2-3 트리, 2-3-4 트리

각 노드가 2~3개(2-3 트리) 또는 2~4개(2-3-4 트리)의 자식을 가질 수 있는 완벽 균형 탐색 트리로, 모든 리프가 같은 깊이에 위치

목적: 완벽 균형 유지, O(log n) 보장, B-Tree 기초, Red-Black 트리 등가

특징: 다중 키 노드, 완벽 균형, 상향식/하향식 균형

2-3 트리

• •2-노드: 1개 키, 2개 자식
• •3-노드: 2개 키, 3개 자식
• •모든 리프 동일 깊이
• •삽입: 리프에 삽입 → 오버플로우 시 분할 후 부모로 키 올림

2-3-4 트리

• •2-노드, 3-노드, 4-노드(3개 키, 4개 자식)
• •삽입: 하향식 분할(4-노드 미리 분할) 또는 상향식 분할
• •Red-Black 트리와 1:1 대응

Red-Black 변환

• •2-노드 → 검정 노드
• •3-노드 → 검정 + 빨강 자식
• •4-노드 → 검정 + 2개 빨강 자식

시간 복잡도: 검색·삽입·삭제 모두 O(log n)

공간 복잡도: O(n)

장점: 완벽 균형, O(log n) 보장, 개념적 명확성

단점: 구현 복잡도, 이진 트리 대비 노드 오버헤드

적용사례: 알고리즘 교육, Red-Black 트리 이해, B-Tree 기초

비교: 2-3(단순) vs 2-3-4(Red-Black등가) vs B-Tree(디스크최적화)

연관: Red-Black 트리, B-Tree, AVL, 균형 트리