Chapter 2. Two-Three Trees(2-3 Trees) Search (5)

1. 2-3 Trees 특징

Definition
Internal node: 2-node or 3-node
2-node: one element with two children
3-node: two element with three children
모든 리프 노드들은 동일한 레벨
Properties
n: number of elements, h: height of 2-3 trees
2h– 1 <= n <= 3h– 1
log3(n + 1) <= h <= log2(n + 1)

2. 2-3 Trees examples

1. 2-3 Trees Basic

2. 2-3 Trees Insertion

• 2노드인 경우 : 삽입할 값과 기존의 값의 대소관계를 비교하여 배치합니다.

• 3노드인 경우 : 삽입할 값과 기존의 값 중 중간 값은 위로 올리고, 남은 두 값을 각각의 노드로 만듭니다.

• 중간 값을 위로 올렸을 때 parent노드가 3노드라면, 다시 중간 값을 올리고 남은 두 값을 각각의 노드로 반복해서 만듭니다.

3. 2-3 Trees Deletion

Leaf node가 아닌 키 값 삭제: leaf node 삭제로 변경
Inorder predecessor와 변경, or
Inorder successor와 변경

Leaf node의 삭제 방법
3-node: 단순 삭제, Node 내에서 키 값 이동 필요
2-node: Node들간의 키 값 이동 필요
Rotation
Combine