초안:2-3 트리 문서 원본 보기

{{초안}}
[[컴퓨터 과학]]에서 '''2–3 트리'''(2–3 tree)는 [[자료 구조]]에서의 [[트리 구조]]의 일종으로, 1970년에 [[존 홉크로프트]]가 발명했다. 기존의 [[이진 트리]]가 하나의 부모 노드에 자식 노드가 2개인 형태라면, 이 트리는 하나의 노드에 값이 2개까지 들어갈 수 있고, 자식 노드를 3개까지 둘 수 있는 것이 특징이다. 2–3 트리는 [[B 트리]]의 order 3에 해당된다.<ref>{{서적 인용| title=The Art of Computer Programming |volume=3| chapter=6.2.4 |quote=The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3. |first1=Donald M |last1=Knuth |edition=2 |isbn=9780201896855 |publisher=Addison Wesley|year=1998}}</ref> [[리프 노드]]에는 자식 노드가 존재하지 않고, 데이터가 1개 또는 2개가 있다.

== 정의 ==
2–3 트리에서 하나의 데이터 요소에 자식 노드가 2개 있다면, 2-노드, 2개의 데이터 요소에 자식 노드가 3개가 있으면, 3-노드로 부른다.

3개의 데이터 요소가 존재하는 4-노드의 경우에는 트리를 만드는 동안에 일시적으로 존재할 수 있지만, 영구적이지 않으며, 최종적으로는 분리된 형태를 띈다.
<gallery>
2-3-4_tree_2-node.svg|2-노드
2-3-4-tree_3-node.svg|3-노드
</gallery>

== 속성 ==
* 모든 내부 노드는 2노드 또는 3노드다.
* 모든 이파리 노드는 같은 레벨에 존재한다.
* 모든 데이터는 정렬된 순서로 유지된다.

== 과정 ==
=== 탐색 ===
2-3 트리에서 항목을 탐색하는 것은 [[이진 탐색 트리]]에서 항목을 탐색하는 알고리즘과 유사하다. 각 노드의 데이터 요소는 순서가 지정되어 있으므로 탐색 기능은 올바른 하위 트리로 이동하고 최종적으로 항목을 포함하는 올바른 노드로 이동한다.
# {{mvar|T}}를 2-3 트리라고 하고 {{mvar|d}}를 찾아야 하는 데이터 요소로 했을 때, 만약 {{mvar|T}}가 비어 있다면, {{mvar|d}}는 {{mvar|T}}에 없는 것으로 작업이 완료된다.
# {{mvar|t}}를 {{mvar|T}}의 근이라고 가정한다.
# {{mvar|t}}가 이파리 노드라고 가정한다.
#* 만약 {{mvar|d}}가 {{mvar|t}}에 존재하지 않는다면, {{mvar|d}}는 {{mvar|T}}에 존재하지 않는다. 그렇지 않으면, {{mvar|d}}는 {{mvar|T}}에 존재한다. 이후로 더 이상의 단계가 필요하지 않으며 작업이 완료된다.
# {{mvar|t}}가 왼쪽 자식 {{mvar|p}}와 오른쪽 자식 {{mvar|q}}가 있는 2-노드라고 가정을 하자. {{mvar|a}}가 {{mvar|t}}의 데이터 요소일 때. 3가지의 경우가 있다.
#* If {{mvar|d}} is equal to {{mvar|a}}, then we've found {{mvar|d}} in {{mvar|T}} and we're done.
#* If <math>d < a</math>, then set {{mvar|T}} to {{mvar|p}}, which by definition is a 2–3 tree, and go back to step 2.
#* If <math>d > a</math>, then set {{mvar|T}} to {{mvar|q}} and go back to step 2.
# Suppose {{mvar|t}} is a 3-node with left child {{mvar|p}}, middle child {{mvar|q}}, and right child {{mvar|r}}. Let {{mvar|a}} and {{mvar|b}} be the two data elements of {{mvar|t}}, where <math>a < b</math>. There are four cases:
#* If {{mvar|d}} is equal to {{mvar|a}} or {{mvar|b}}, then {{mvar|d}} is in {{mvar|T}} and we're done.
#* If <math>d < a</math>, then set {{mvar|T}} to {{mvar|p}} and go back to step 2.
#* If <math>a < d < b</math>, then set {{mvar|T}} to {{mvar|q}} and go back to step 2.
#* If <math>d > b</math>, then set {{mvar|T}} to {{mvar|r}} and go back to step 2.

=== 삽입 ===
삽입은 트리의 균형 잡힌 속성을 유지한다.<ref name="A4">{{서적 인용|section=3.3 |title=Algorithms|edition=4|first1=Robert |last1=Sedgewick |first2=Kevin |last2=Wayne |publisher=Addison Wesley |isbn=9780321573513}}</ref>

2-노드에 데이터를 삽입하려면 새로운 키가 순서에 맞게 2-노드에 추가된다.

3-노드에 삽입하려면 3-노드의 위치에 따라 더 많은 작업이 필요할 수 있다. 트리가 3-노드로만 구성되었을 경우에 해당 노드는 적절한 키와 자식이 있는 3개의 2-노드로 분할된다.
[[파일:2-3 insertion.svg|framed|none]]
대상 노드가 3-노드이고 부모가 2-노드인 경우에는 키를 3-노드에 삽입하여 임시로 4-노드를 생성한다. 그림에서 10은 6과 9가 있는 2-노드에 삽입된다. 중간 키는 9이며, 상위 2-노드로 승격된다. 이렇게 하면 6과 10의 3-노드가 남고, 부모 3-노드의 자식으로 유지되는 2개의 2-노드로 분할된다.

대상 노드가 3-노드이고 상위 노드가 3-노드인 경우 임시 4-노드를 생성한 후 위와 같이 분할한다. 이 [[프로세스|과정]]은 트리에서 루트까지 계속된다. 루트를 분할해야 할 경우에는 단일 3-노드 프로세스를 따른다. 임시 4-노드 루트가 3개의 2-노드로 분할되고 그 중 하나가 루트로 간주된다. 이러한 작업은 트리의 높이를 1씩 증가시킨다.

=== 병렬 과정 ===
{{참고|레드-블랙 트리#병렬 알고리즘}}
2-3 트리는 레드-블랙 트리와 구조가 유사하기 때문에 레드-블랙 트리의 [[병렬 알고리즘]]은 2-3 트리에도 똑같이 적용될 수 있다.

== 각주 ==
{{각주}}

{{초안 분류|
[[분류:트리 구조]]
}}