2-3-4 트리

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

2–3–4 트리는 차수 4의 B 트리이다.. Section 6.2.4: Multiway Trees, pp. 481–491. Also, pp. 476–477 of section 6.2.3 (Balanced Trees) discusses 2–3 trees. 일반적인 B 트리와 마찬가지로, O(log n) 시간 내에 검색, 삽입 및 삭제를 수행할 수 있다. 2–3–4 트리의 한 가지 특징은 모든 외부 노드가 동일한 깊이에 있다는 것이다.

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

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

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

 예시 
2–3–4 트리에 "25" 값을 삽입하려면:
308x308px
 루트 (10, 20)에서 시작하여 가장 오른쪽 자식 (22, 24, 29)으로 내려간다. (해당 간격 (20, ∞)에 25가 포함되어 있다.)
 노드 (22, 24, 29)는 4-노드이므로 중간 요소 24가 부모 노드로 올라간다.
274x274px
 남은 3-노드 (22, 29)는 두 개의 2-노드 (22)와 (29)로 분할된다. 새 부모 (10, 20, 24)로 다시 올라간다.
 가장 오른쪽 자식 (29)으로 내려간다. (해당 간격 (24, ∞)에 25가 포함되어 있다.)
300x300px
 노드 (29)는 가장 왼쪽 자식이 없다. (간격 (24, 29)에 대한 자식이 비어 있다.) 여기서 멈추고 이 노드에 값 25를 삽입한다.
349x349px

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

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

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

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

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

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

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

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

 같이 보기 

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

 각주 

 외부 링크 

 Algorithms In Action, 2–3–4 트리 애니메이션 포함
 왼쪽 기울어진 레드-블랙 트리 – 로버트 세지윅, 프린스턴 대학교, 2008
 Open Data Structures – 섹션 9.1 – 2–4 트리 , 팻 모린
 2–3–4 트리: 시각적 소개, 2017

분류:B 트리