[자료구조] (2,4) Trees 2-3-4트리

• multi-way search tree
  • binarySearch Tree의 relationial특성은 같지만 구조적 특성은 다르다
  • binary ≠ multi-way
• 각 내부노드는 최소 2개 child 가져야함

(2,4) Trees(2-3-4tree)

• 다음 속성을 만족하는 multi-way 트리
• 모든 내부 노드가 child를 2,3,4개만 갖는 트리
• 깊이 속성 (Depth Property): 모든 외부 노드는 같은 깊이에 있음
• Searching in a (2,4) tree with n items takes O(log n) time

삽입(Insertion)

1. 키 k를 탐색하여 도달한 잎 노드의 부모 노드 v에 새로운 항목 (k, o)를 삽입합니다.
2. 삽입 전후에도 깊이 속성을 유지합니다. 즉, 모든 외부 노드는 같은 깊이에 있어야 합니다.
3. 하지만 삽입으로 인해 오버플로우가 발생할 수 있습니다. 이 경우, 노드 v는 5-노드가 될 수 있습니다.

오버플로우와 Split

오버플로우가 발생하면 분할 작업을 수행하여 처리합니다

• 분할 대상 노드 v
  • v의 자식 노드를 v1,v2,v3,v4,v5로 가정합니다.
  • v의 키를 k1,k2,k3,k4로 가정합니다.
• 노드 v의 대체
  • v는 노드 v'와 v"로 대체됩니다.
  • v'는 3-노드로, 키 k1,k2와 자식 v1,v2,v3을 가집니다.
  • v"은 2-노드로, 키 k4와 자식 v4,v5를 가집니다.
• 부모 노드에 키 삽입
  • 키 k3은 v의 부모 노드 u에 삽입됩니다.
  • 이 과정에서 새로운 루트가 생성될 수 있습니다.

삭제(Deletion)

1. 노드의 리프 자식에 대한 삭제
   • 삭제 작업을 리프 노드에 있는 경우로 축소합니다.
2. 노드의 리프가 아닌 자식에 대한 삭제
   • 그렇지 않은 경우, 삭제 대상을 그 노드의 inorder successor로 대체합니다. (또는 inorder predecessor로 대체할 수도 있습니다.)
   • 이후 inorder predecessor를 삭제합니다.

언더플로우와 Fusion

Case 1: v의 인접한 형제 노드가 2-노드인 경우

• 퓨전 작업 (Fusion operation): v를 인접한 형제 노드 w와 병합하고, 부모 노드 u로부터 병합된 노드 v'로 항목을 이동시킵니다.
• 퓨전 후에는 언더플로우가 부모 노드 u로 전파될 수 있습니다.

Case 2: v의 인접한 형제 노드 w가 3-노드 또는 4-노드인 경우

• 전송 작업 (Transfer operation):
  1. w의 자식 중 하나를 v로 이동합니다.
  2. u의 항목 중 하나를 v로 이동합니다.
  3. w의 항목 중 하나를 u로 이동합니다.
• 전송 후에는 언더플로우가 발생하지 않습니다.

  트리의 높이	O(logn)
  insertion	O(logn)
  remove	O(logn)