2-3-4 Tree 추가 삭제 구현 (2-3-4 Tree Insert Delete)

AVL Tree, 2-3 Tree 에 이어서, 이번에는 2-3-4 Tree 에 대한 이야기를 하려고 합니다. 2-3-4 Tree 도 이전 트리들과 같이 균형 잡는 트리 입니다. 트리에 값을 삽입(추가)하거나 삭제 할 때, 트리 구조를 변형 시키면서 트리의 균형이 유지되도록 합니다. 2-3-4 트리는 다음과 같은 속성을 갖습니다.

딱 이렇게만 써놓고 이제 2-3-4 트리 구현하세요. 라고 하면 막막하죠... 그래서 몇 가지 규칙을 정리해 보았습니다.

kiss

2-3 트리나 AVL 트리를 구현할 때, 삽입 또는 삭제가 발생하면 균형을 잡기 위해서 스택을 이용했었습니다. 부모 노드를 거슬러 올라가면서 트리의 균형이 유지될 수 있도록 하기 위해서였는데요. 2-3-4 트리에서는 스택을 사용하지 않고 균형을 잡게 됩니다. 앞 서 이야기 했던 삽입/삭제시 방문하는 노드들을 분할/합병 시키기 때문에 항상 부모 노드에서는 분할이나 합병을 끝낼 수 있게 되기 때문입니다.

2-3-4 Tree / Insert
2-3-4 Tree 삽입

0x20 을 삽입할 때, 처음 만나는 부모 노드가 { 0x40, 0x80, 0x120 } 세 개의 키를 가지고 있는 꽉찬 노드이기 때문에 분할되어 0x80 을 부모 노드로 하고, 좌/우 자식 노드가 각각 0x40 과 0x120 이 됩니다. 이 후 삽입 과정이 계속 진행 됩니다.

2-3-4 Tree / Delete
2-3-4 Tree 삭제

삭제를 할 때에는 Leaf node 에서 값을 삭제 시키기 위해 삭제할 키의 오른 쪽 자식 서브 트리에서 가장 작은 값 또는 왼쪽 자식 서브 트리에서 가장 큰 값을 찾아 삭제할 키와 교체 한 후 Leaf node 에서 삭제를 진행하게 됩니다. 이 방법은 이진 트리나 2-3 트리와 같습니다. 또한 대체한 키가 있던 Leaf node 에 키가 하나 뿐이었다면, 형제 노드에서 빌려오게 됩니다. 예를 들어, 0x100 을 삭제할 때, 형제 노드인 { 0x50, 0x60 } 에서 0x60 을 부모 노드로 밀어 올리고, 부모 노드에서 0x90 을 0x100 이 있는 노드에 넣은 후, 0x100 을 삭제하여 트리의 균형이 유지 되도록 합니다. 0x90 을 삭제하는 경우, 양 쪽 형제 노드 모두 키가 하나 뿐이기 때문에 키를 가져올 수 없는 상황입니다. 이 경우, 부모 노드에서 키를 가지고 내려오고, 형제 노드에 있는 키와 합치는 방식으로 균형을 유지하게 됩니다. 여기까지는 2-3 트리와 매우 비슷합니다. 제일 처음 0x80 을 삭제하는 경우가 2-3-4 트리가 2-3 트리와 다른 점을 보여주고 있습니다. 0x80 을 삭제하기 위해 Leaf node 에서 0x90 과 값을 바꾼 후 0x80 을 삭제합니다. 하지만, 값을 찾아가는 과정에서 만나는 노드들이 병합되기 때문에, 0x80 을 삭제해도 균형이 유지되지만, { 0x40, 0x90, 0x120 } 세 개의 값으로 부모 노드가 병합된 것을 볼 수 있습니다.

2-3-4 트리를 구현하면서 2-3 트리를 구현할 때와 같이 tree_dump 함수를 수정했습니다. 해당 함수의 val_size 변수의 값을 수정하면 출력할 키의 길이를 지정할 수 있습니다. space 는 하나의 노드 안에 키 간 간격이고, span 은 같은 깊이에 있는 노드들 간의 간격을 의미합니다. 또한, tree_validate 함수에서 노드 안의 키 값들이 정렬되어 있는지도 확인하도록 했습니다.

전체 코드는 github 에서 확인할 수 있습니다.

cheeky

그럼, 즐거운 취미 생활 하세요~

 

Link: https://nicesj.com/article/calendar/3251

RSS Feed Since 2003, A story was began.
This page is optimized for the web crawlers, for examples, bingbot, googlebot, daum, naver and so on.
Please, visit the site again using the general user clients, for examples, chrome, firefox, ie and so on.

Previous Next