2-3 트리

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

2–3 트리
종류	트리
발명일	1970
발명자	존 홉크로프트
점근표기법으로 된 시간복잡도
알고리즘 평균 최악의 경우 공간 ${\displaystyle O(n)}$ 탐색 ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ 삽입 ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ 삭제 ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

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

정의

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

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

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

• 
  2-노드
• 
  3-노드

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

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

속성

• 모든 내부 노드는 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의 데이터 요소로 둔다. 세 가지 경우가 있다:
   • 만약 d가 a와 같으면, T에서 d를 찾았으므로 탐색이 완료된다.
   • 만약 ${\displaystyle d<a}$이면, T를 정의에 따라 2–3 트리인 p로 설정하고 2단계로 돌아간다.
   • 만약 ${\displaystyle d>a}$이면, T를 q로 설정하고 2단계로 돌아간다.
5. t가 왼쪽 자식 p, 중간 자식 q, 오른쪽 자식 r을 가진 3-노드라고 가정한다. a와 b를 t의 두 데이터 요소로 두며, ${\displaystyle a<b}$이다. 네 가지 경우가 있다:
   • 만약 d가 a 또는 b와 같으면, d는 T에 있으므로 탐색이 완료된다.
   • 만약 ${\displaystyle d<a}$이면, T를 p로 설정하고 2단계로 돌아간다.
   • 만약 ${\displaystyle a<d<b}$이면, T를 q로 설정하고 2단계로 돌아간다.
   • 만약 ${\displaystyle d>b}$이면, T를 r로 설정하고 2단계로 돌아간다.

삽입

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

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

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

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-노드를 생성하고 다시 올라오면서 파괴하는 방식이다. 삭제 방법은 참조에서 더 자세히 설명한다.^[5][6]

병렬 연산

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

같이 보기

• 2–3–4 트리
• 2–3 힙
• AA 트리
• B 트리
• (a,b)-트리
• 핑거 트리