2-3 트리

컴퓨터 과학에서 2–3 트리(2–3 tree)는 자료 구조에서의 트리 구조의 일종으로, 1970년에 존 홉크로프트가 발명했다. 기존의 이진 트리가 하나의 부모 노드에 자식 노드가 2개인 형태라면, 이 트리는 하나의 노드에 값이 2개까지 들어갈 수 있고, 자식 노드를 3개까지 둘 수 있는 것이 특징이다. 2–3 트리는 B 트리의 order 3에 해당된다. 리프 노드에는 자식 노드가 존재하지 않고, 데이터가 1개 또는 2개가 있다.

정의

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

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

• 

  2-노드

• 

  3-노드

속성

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

과정

탐색

2-3 트리에서 항목을 탐색하는 것은 이진 탐색 트리에서 항목을 탐색하는 알고리즘과 유사하다. 각 노드의 데이터 요소는 순서가 지정되어 있으므로 탐색 기능은 올바른 하위 트리로 이동하고 최종적으로 항목을 포함하는 올바른 노드로 이동한다.

1. T를 2-3 트리라고 하고 d를 찾아야 하는 데이터 요소로 했을 때, 만약 T가 비어 있다면, d는 T에 없는 것으로 작업이 완료된다.
2. t를 T의 근이라고 가정한다.
3. t가 이파리 노드라고 가정한다.
   • 만약 d가 t에 존재하지 않는다면, d는 T에 존재하지 않는다. 그렇지 않으면, d는 T에 존재한다. 이후로 더 이상의 단계가 필요하지 않으며 작업이 완료된다.
4. t가 왼쪽 자식 p와 오른쪽 자식 q가 있는 2-노드라고 가정을 하자. a가 t의 데이터 요소일 때. 3가지의 경우가 있다.
   • If d is equal to a, then we've found d in T and we're done.
   • If $d<a$, then set T to p, which by definition is a 2–3 tree, and go back to step 2.
   • If $d>a$, then set T to q and go back to step 2.
5. Suppose t is a 3-node with left child p, middle child q, and right child r. Let a and b be the two data elements of t, where $a<b$. There are four cases:
   • If d is equal to a or b, then d is in T and we're done.
   • If $d<a$, then set T to p and go back to step 2.
   • If $a<d<b$, then set T to q and go back to step 2.
   • If $d>b$, then set T to r and go back to step 2.

삽입

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

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

3-노드에 삽입하려면 3-노드의 위치에 따라 더 많은 작업이 필요할 수 있다. 트리가 3-노드로만 구성되었을 경우에 해당 노드는 적절한 키와 자식이 있는 3개의 2-노드로 분할된다.

대상 노드가 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 트리에도 똑같이 적용될 수 있다.

각주

This article "2-3 트리" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:2-3 트리. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---

 Facebook Page

🐤 Twitter Follow us on Twitter !

Read or create/edit this page in another language

• 2-3 트리 in English