자료구조 - (2,4) Tree 정리

(2,4) Tree 란?

BST(Binary Search Tree)와 비슷하게 In-Order 의 순서로 값이 정렬되는데, 각 노드들의 Entry가 1개~3개인 Multi-Way Tree 의 한 종류이다.
각 Entry에 INF Entry를 더해 총 2개~4개가 되어 (2,4)라고 불린다.

각 Entry는 자식 노드를 하나 가지는데 자신의 값 이하의 노드와 연결된다.

Insertion

BST처럼 왼쪽, 오른쪽 값들을 비교해가면서 자기 값의 자리를 찾아간다.
찾은 자리에 공간이 남는다면 (Entry가 2개 이하라면) 그 자리에 들어가면 되지만
오버플로우가 발생할 수도 있다.

추가 후에 Entry가 4개가 되어 오버플로우가 발생하면,
왼쪽부터 두 개의 Entry, 오른쪽부터 한 개의 Entry로 쪼개고, 남는 중간 하나의 Entry는 부모 노드로 올려준다.
그 Entry의 왼쪽, 오른쪽이 먼저 쪼갠 두 개의 노드가 된다.

부모 노드로 Entry를 올려주게되면 부모 노드에서도 오버플로우가 발생할 수 있는데, 계속 전파하면된다.
만약 root 노드까지 오버플로우가 발생해 더 이상 올려줄 부모 노드가 없게 되면, 새로운 root노드를 만들어 올려준다.

Deletion

BST에서처럼 자식 노드가 없다면 그대로 삭제
자식 노드가 하나라면 자식 노드의 부모를 자신의 부모로 바꿔주고 삭제
자식 노드가 여러 개라면 In-Order 순서로 자신 다음 혹은 자신 바로 전 순서의 값과 바꾼 뒤 삭제
위 방식을 그대로 사용한다.
하지만 삭제 시에 노드의 Entry가 0개가 되는 언더플로우가 발생할 수 있다.

언더플로우 발생 시

1. 가까운 형제 노드(깊이가 같은 노드) 의 Entry가 2개 이상인 경우
(Entry를 줘도 언더플로우x)
 - 형제 노드의 부모 Entry 값을 자신에게 가져오고, 형제 노드의 Entry는 부모 노드로 올린다.

2. 가까운 형제 노드(깊이가 같은 노드) 의 Entry가 1개인 경우(Entry를 주면 언더플로우)
 - 부모 Entry를 자신에게 가져오고, 형제 노드와 합쳐준다.
이 때, 부모 노드의 Entry를 가져왔으므로 부모 노드에서도 언더플로우가 발생할 수 있다.
Insertion과 마찬가지로 언더플로우를 위쪽으로 전파해가는데, root노드에서 언더플로우가 발생 시 root노드를 지우고 새롭게 합쳐진 노드가 새로운 root노드가 된다.