2-3 트리

컴퓨터 과학에서 2–3 트리는 모든 자식 노드(내부 노드)가 두 개의 자식(2-노드)과 하나의 데이터 요소 또는 세 개의 자식(3-노드)과 두 개의 데이터 요소를 가지는 트리 자료 구조이다. 2–3 트리는 3차 B 트리이다. 트리의 바깥쪽에 있는 노드(리프 노드)는 자식이 없고 하나 또는 두 개의 데이터 요소를 가진다., pp.145–147 2–3 트리는 1970년 존 홉크로프트가 발명했다.

2–3 트리는 균형이 맞춰져 있어야 하는데, 이는 각 리프가 같은 레벨에 있다는 것을 의미한다. 따라서 노드의 각 오른쪽, 중앙, 왼쪽 서브트리는 같거나 거의 같은 양의 데이터를 포함한다.

정의
내부 노드에 데이터 요소가 하나 있고 두 개의 자식이 있으면 이를 2-노드라고 한다.

내부 노드에 데이터 요소가 두 개 있고 세 개의 자식이 있으면 이를 3-노드라고 한다.

데이터 요소가 세 개인 4-노드는 트리를 조작하는 동안 일시적으로 생성될 수 있지만, 트리 내에 영구적으로 저장되지는 않는다.

가 2–3 트리인 경우는 다음 문장 중 하나만 참일 때이다:

 가 비어 있다. 즉, 에 노드가 없다.
 가 데이터 요소 를 가진 2-노드이다. 가 왼쪽 자식 와 오른쪽 자식 를 가진다면,
 와 는 같은 높이의 2–3 트리이다.
 는 의 각 요소보다 크다.
 는 의 각 데이터 요소보다 작다.
 가 데이터 요소 와 를 가진 3-노드이며,   이다. 가 왼쪽 자식 , 중간 자식 , 오른쪽 자식 을 가진다면,
 , , 은 같은 높이의 2–3 트리이다.
 는 의 각 데이터 요소보다 크고 의 각 데이터 요소보다 작다.
 는 의 각 데이터 요소보다 크고 의 각 데이터 요소보다 작다.

속성
 모든 내부 노드는 2-노드 또는 3-노드이다.
 모든 리프는 같은 레벨에 있다.
 모든 데이터는 정렬된 상태로 유지된다.

연산

탐색
2–3 트리에서 항목을 탐색하는 것은 이진 탐색 트리에서 항목을 탐색하는 것과 유사하다. 각 노드의 데이터 요소가 정렬되어 있으므로, 탐색 함수는 올바른 서브트리와 결국 항목을 포함하는 올바른 노드로 향하게 된다.

 를 2–3 트리로, 를 찾고자 하는 데이터 요소로 둔다. 가 비어 있으면 는 에 없고 탐색이 완료된다.
 를 의 루트로 둔다.
 가 리프라고 가정한다.
 만약 가 에 없으면 는 에 없다. 그렇지 않으면 는 에 있다. 더 이상의 단계는 필요 없으며 탐색이 완료된다.
 가 왼쪽 자식 와 오른쪽 자식 를 가진 2-노드라고 가정한다. 를 의 데이터 요소로 둔다. 세 가지 경우가 있다:
 만약 가 와 같으면, 에서 를 찾았으므로 탐색이 완료된다.
 만약 이면, 를 정의에 따라 2–3 트리인 로 설정하고 2단계로 돌아간다.
 만약 이면, 를 로 설정하고 2단계로 돌아간다.
 가 왼쪽 자식 , 중간 자식 , 오른쪽 자식 을 가진 3-노드라고 가정한다. 와 를 의 두 데이터 요소로 두며, 이다. 네 가지 경우가 있다:
 만약 가  또는 와 같으면, 는 에 있으므로 탐색이 완료된다.
 만약 이면, 를 로 설정하고 2단계로 돌아간다.
 만약 이면, 를 로 설정하고 2단계로 돌아간다.
 만약 이면, 를 로 설정하고 2단계로 돌아간다.

삽입
삽입은 트리의 균형 속성을 유지한다.

2-노드에 삽입할 때, 새 키는 적절한 순서로 2-노드에 추가된다.

3-노드에 삽입할 때는 3-노드의 위치에 따라 더 많은 작업이 필요할 수 있다. 트리가 3-노드로만 구성되어 있다면, 노드는 적절한 키와 자식을 가진 세 개의 2-노드로 분할된다.

framed|none|3가지 가능한 경우에 대한 2–3 트리에 숫자 삽입

대상 노드가 부모가 2-노드인 3-노드인 경우, 키는 3-노드에 삽입되어 임시 4-노드를 생성한다. 그림에서 키 10은 6과 9를 가진 2-노드에 삽입된다. 중간 키는 9이며, 부모 2-노드로 승격된다. 이렇게 되면 6과 10의 3-노드가 남게 되며, 이는 부모 3-노드의 자식으로 유지되는 두 개의 2-노드로 분할된다.

대상 노드가 3-노드이고 부모도 3-노드인 경우, 임시 4-노드가 생성된 다음 위와 같이 분할된다. 이 과정은 루트까지 트리 위로 계속된다. 루트를 분할해야 하는 경우, 단일 3-노드의 과정이 따른다: 임시 4-노드 루트는 세 개의 2-노드로 분할되며, 그중 하나가 루트로 간주된다. 이 연산은 트리의 높이를 하나 증가시킨다.

삭제
비-리프 노드에서 키를 삭제하는 것은 즉각적인 선행자 또는 후속자로 대체한 다음 리프 노드에서 선행자 또는 후속자를 삭제함으로써 수행할 수 있다. 리프 노드에서 키를 삭제하는 것은 리프가 3-노드인 경우 쉽다. 그렇지 않은 경우, 임시 1-노드를 생성해야 할 수 있으며, 이는 트리를 재구성하여 흡수되거나, 삽입의 경우 임시 4-노드처럼 흡수되기 전에 반복적으로 위로 이동해야 할 수 있다. 또는 하향식과 상향식을 모두 사용하는 알고리즘을 사용할 수 있는데, 이는 내려가는 길에 임시 4-노드를 생성하고 다시 올라오면서 파괴하는 방식이다. 삭제 방법은 참조에서 더 자세히 설명한다."2-3 Trees", Lyn Turbak, handout #26, course notes, CS230 Data Structures, Wellesley College, December 2, 2004. Accessed Mar. 11, 2024.
병렬 연산
2–3 트리는 레드-블랙 트리와 구조가 유사하므로, 레드-블랙 트리를 위한 병렬 알고리즘도 2–3 트리에 적용할 수 있다.

 같이 보기 
 2–3–4 트리
 2–3 힙
 AA 트리
 B 트리
 (a,b)-트리
 핑거 트리

 각주 

분류:B 트리
분류:분할 상환 자료 구조