2-3-4 트리

컴퓨터 과학에서 2–3–4 트리 (또는 2–4 트리)는 사전을 구현하는 데 사용할 수 있는 자가 균형 자료 구조이다. 이 숫자는 자식 노드가 있는 모든 노드 (내부 노드)가 두 개, 세 개 또는 네 개의 자식 노드를 갖는 트리를 의미한다.

• 2-노드는 하나의 데이터 요소를 가지며, 내부 노드인 경우 두 개의 자식 노드를 가진다.
• 3-노드는 두 개의 데이터 요소를 가지며, 내부 노드인 경우 세 개의 자식 노드를 가진다.
• 4-노드는 세 개의 데이터 요소를 가지며, 내부 노드인 경우 네 개의 자식 노드를 가진다.

• 
  2-노드
• 
  3-노드
• 
  4-노드

2–3–4 트리
종류	트리
점근표기법으로 된 시간복잡도
알고리즘 평균 최악의 경우 공간 O(n) O(n) 탐색 O(log n) O(log n) 삽입 O(log n) O(log n) 삭제 O(log n) O(log n)

2–3–4 트리는 차수 4의 B 트리이다.^[1] 일반적인 B 트리와 마찬가지로, O(log n) 시간 내에 검색, 삽입 및 삭제를 수행할 수 있다. 2–3–4 트리의 한 가지 특징은 모든 외부 노드가 동일한 깊이에 있다는 것이다.

2–3–4 트리는 레드 링크(즉, 빨간색 자식에 대한 링크)를 3-노드 및 4-노드의 내부 링크로 해석함으로써 레드-블랙 트리와 밀접하게 관련되어 있지만, 이 대응 관계는 일대일이 아니다.^[2] 왼쪽 기울어진 레드-블랙 트리는 단일 빨간색 오른쪽 자식을 가진 노드를 금지함으로써 레드-블랙 트리를 제한하며, 이는 왼쪽 기울어진 레드-블랙 트리와 2–3–4 트리 사이에 일대일 대응을 이룬다.

속성

• 모든 노드(리프 또는 내부)는 2-노드, 3-노드 또는 4-노드이며, 각각 하나, 두 개 또는 세 개의 데이터 요소를 저장한다.
• 모든 리프는 동일한 깊이(가장 아래 레벨)에 있다.
• 모든 데이터는 정렬된 순서로 유지된다.

삽입

값을 삽입하려면 2–3–4 트리의 루트에서 시작한다.

1. 현재 노드가 4-노드인 경우:
   • 중간 값을 제거하고 저장하여 3-노드를 만든다.
   • 남은 3-노드를 두 개의 2-노드로 분할한다(이제 사라진 중간 값은 다음 단계에서 처리된다).
   • 이 노드가 루트 노드인 경우(따라서 부모가 없는 경우):
     • 중간 값이 새 루트 2-노드가 되고 트리의 높이가 1 증가한다. 루트로 올라간다.
   • 그렇지 않으면 중간 값을 부모 노드로 올린다. 부모 노드로 올라간다.
2. 삽입할 값을 포함하는 자식을 찾는다.
3. 해당 자식이 리프인 경우, 값을 자식 노드에 삽입하고 완료한다.
   • 그렇지 않으면 자식으로 내려가 1단계부터 반복한다.^[3][4]

예시

2–3–4 트리에 "25" 값을 삽입하려면:

• 루트 (10, 20)에서 시작하여 가장 오른쪽 자식 (22, 24, 29)으로 내려간다. (해당 간격 (20, ∞)에 25가 포함되어 있다.)
• 노드 (22, 24, 29)는 4-노드이므로 중간 요소 24가 부모 노드로 올라간다.

• 남은 3-노드 (22, 29)는 두 개의 2-노드 (22)와 (29)로 분할된다. 새 부모 (10, 20, 24)로 다시 올라간다.
• 가장 오른쪽 자식 (29)으로 내려간다. (해당 간격 (24, ∞)에 25가 포함되어 있다.)

• 노드 (29)는 가장 왼쪽 자식이 없다. (간격 (24, 29)에 대한 자식이 비어 있다.) 여기서 멈추고 이 노드에 값 25를 삽입한다.

삭제

요소를 삭제하는 가장 간단한 방법은 요소를 그대로 두고 "삭제됨"으로 표시하여 이전 알고리즘이 삭제된 요소를 무시하도록 조정하는 것이다. 삭제된 요소는 나중에 삽입을 수행할 때 덮어쓰기하여 재사용할 수 있다. 그러나 이 방법의 단점은 트리의 크기가 줄어들지 않는다는 것이다. 트리의 요소 중 상당 부분이 삭제되면 트리는 현재 저장된 요소의 크기보다 훨씬 커지고 다른 작업의 성능이 삭제된 요소의 영향을 받아 불리해진다.

이것이 바람직하지 않은 경우, 2–3–4 트리에서 값을 제거하기 위해 다음 알고리즘을 따를 수 있다.

1. 삭제할 요소를 찾는다.
   • 요소가 리프 노드에 없으면 해당 위치를 기억하고, 요소의 후속 항목을 포함할 리프에 도달할 때까지 계속 검색한다. 후속 항목은 제거할 항목보다 작은 가장 큰 키 또는 제거할 항목보다 큰 가장 작은 키일 수 있다. 리프 노드가 2-노드가 아니도록 위에서 아래로 트리를 조정하는 것이 가장 간단하다. 그렇게 하면 스왑 후 빈 리프 노드가 생기지 않는다.
   • 요소가 2-노드 리프에 있으면 아래 조정을 수행한다.

제거하려는 리프로 가는 도중에 2-노드(루트 노드 제외)가 발견되면 다음 조정을 수행한다.

1. 이 노드 양쪽의 형제 노드가 3-노드 또는 4-노드인 경우(따라서 1개 이상의 키를 가짐) 해당 형제 노드와 회전을 수행한다.
   • 이 노드에 가장 가까운 다른 형제 노드의 키가 두 노드를 바라보는 부모 키로 올라간다.
   • 부모 키는 이 노드로 내려와 3-노드를 형성한다.
   • 원래 회전된 형제 키와 함께 있던 자식은 이제 이 노드의 추가 자식이 된다.
2. 부모가 2-노드이고 형제 노드도 2-노드인 경우, 세 요소를 모두 결합하여 새 4-노드를 형성하고 트리를 줄인다. (이 규칙은 부모 2-노드가 루트인 경우에만 트리거될 수 있다. 경로상의 다른 모든 2-노드는 2-노드가 아니도록 수정되었을 것이기 때문이다. 이것이 여기서 "트리를 줄인다"는 것이 균형을 유지하는 이유이다. 이것은 또한 합병 작업의 중요한 가정이다.)
3. 부모가 3-노드 또는 4-노드이고 모든 인접 형제 노드가 2-노드인 경우, 부모 및 인접 형제 노드와 합병 작업을 수행한다.
   • 인접 형제 노드와 두 형제 노드를 바라보는 부모 키가 합쳐져 4-노드를 형성한다.
   • 형제 노드의 자식을 이 노드로 전송한다.

찾는 값에 도달하면 리프 노드에 1개 이상의 키가 있음을 확인했으므로 이제 제거된 항목의 위치에 문제없이 배치할 수 있다.

2–3–4 트리에서 삭제는 전송 및 합병이 상수 시간(O(1))으로 실행된다고 가정할 때 O(log n)이다.^[3][5]

병렬 연산

2–3–4 트리는 레드-블랙 트리와 구조가 유사하므로, 레드-블랙 트리에 대한 병렬 알고리즘도 2–3–4 트리에 적용될 수 있다.

같이 보기

• 2–3 트리
• 레드-블랙 트리
• B 트리
• 큐힙