2-3-4 트리

• 이진 탐색 트리는 1개의 키, 2개의 링크를 갖는데, 2-3-4 트리는 세가지를 더 만족한다.

  • 하나의 이상의 키를 가질 수 있음
  • 2-노드(1개의 키, 2개의 링크)
  • 3-노드(2개의 키, 3개의 링크)
  • 4-노드(3개의 키, 4개의 링크)

• 분할 과정

  • 4-노드: 세개의 2-노드로 변환, 높이 1 증가

  • 부모가 2-노드인 4-노드

    • 부모 노드를 3-노드로 만들고, 중간 키를 부모 노드로 보낸다.

    

  • 부모가 3-노드인 4-노드

    • 부모 노드를 4-노드로 만들고, 자식은 2-노드 두개로 만든다.

    

• 성능 특성

  N-노드로 이루어진 2-3-4 트리라고 하자.

  • 탐색: $\log N + 1$ 이상의 노드를 방문하지 않음
  • 삽입
    • 평균: 하나 이하의 노드 분할
    • 최악: $\log N+1$ 개 분할
    • 2-3-4 트리에서 4-노드의 개수가 적음
  • 일반적으로 높이가 h 인 2-3-4 트리의 키: $2^{h+1}-1 \le k \le 4^{h+1}-1$
  • N개의 키를 포함하는 2-3-4 트리의 높이 h: $\log_4{(N+1)}-1 \le h \le log_2{(N+1)}-1$