2-4 Tree?

• balanced binary search tree의 일종

• 각 노드는 최소 1개에서 최대 3개의 데이터 요소를 가질 수 있음.

  → 2개에서 4개의 자식 노드를 갖게 됨.

• 균형을 자동으로 유지해 어떤 연산을 수행해도 트리의 높이가 최소화 됨 → 성능 보장

2-4 Tree의 특성

• 모든 리프 노드는 같은 레벨에 위치함.

  → 항상 균형을 유지하는 상태

• 노드는 최소 1개에서 최대 3개의 데이터 요소를 가질 수 있음.

  → 2개에서 4개의 자식을 가질 수 있게 됨.

• 정렬된 상태로 유지됨.

• 삽입이나 삭제 연산 시 노드의 분할이나 병합을 통해 트리의 균형을 유지함,

Time Complexity

• 탐색 시, $O(logn)$의 시간 복잡도를 가짐.

Insertion

Overflow 발생 시 → Devide

Insert 순서

1st. 데이터가 들어갈 위치 확인

2nd. Insert

3rd. Overflow → devide

Insert - Algorithm