알고리즘 레포트 234트리,레드블랙트리 조사

알고리즘 레포트 234트리,레드블랙트리 조사

[알고리즘 레포트] 234트리,레드블랙트리 조사.docx

본문 ▣ 개요: Tree를 이용하는 binary search는 complete binary 트리의 경우 O(nlog n) 이라는 실용적인 탐색시간을 보장한다. 하지만 실제 세계에서는 데이터의 입력이 항상 complete binary tree를 만드는 것을 보장해 주지는 않는다. 따라서 최악의 경우에는 O(n*n)이라는 사태가 발생할 수도 있는 것이다. 이런 worst case를 막기 위해서 data를 insertion하는 방법에 있어서 많은 방법들이 등장하였지만, 좀 더 근본적인 부분에서 해결을 하기 위해 자료구조 자체에 대한 연구가 이루어졌고, 그에 대한 결과물 중의 하나가 바로 2-3-4트리이다. 2-3-4 트리란 각 노드의 차수가 4 이하인 트리를 말한다. 즉 각 노드는 2~4개의 서브 트리를 가지게 된다는 뜻이다. 2-3-4 트리와 비슷한 형태를 지닌 2-3트리와 마찬가지로 데이터를 삽입해야 하는 어떤 단말 노드가 4개의 노드를 가지는 경우, 빈 공간이 없으므로 데이터를 하나 위로 올려 보내고 단말 노드의 데이터를 반으로 분할해주는 split연산을 수행하게 된다. 그리고 이 때 후진분할(backward)가 일어나는 것을 막기 원한다면 삽입할 곳을 찾아오면서 4-노드가 있으면 미리 분할해 놓는 과정이 필요하다. 즉 루트가 아닌 4-노드의 부모 노드는 4-노드가 아님을 보장하여서 단말 노드의 분할시에 데이터를 위로 올려보내도 후진 분할이 일어나지 않게 하는 것이다. 이 2-3-4트리는 트리의 높이가 낮고, 최악의 경우에도 complete binary tree의 형태를 유지하기 때문에 worst case에 있어서도 O(nlog n)의 성능을 보장해준다. 키워드 트리, 블랙, 레포트, 조사, 알고리즘, 레드블랙트리