[자료구조] 2-3-4 Tree, B Tree, Red-Black Tree

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

2-3-4 Tree

• 2-3 트리의 확장판이다. Node key 값의 공간이 커진다.
• 모든 leaf가 같은 거리에 있다.
• 2-3-4 트리에 N개의 key가 있을 때 Height는 O(logN)이다.
• 해당 트리는 2-3 트리와 달리 새로운 key값이 들어오지 않아도 key 값이 3개인 상태에서 split이 가능하다.
• 트리에서는 새로운 키 값이 추가될 때 [노드내부 작업 - 링크 따라가기 - 새로운 노드 및 링크 생성]의 과정이 필요했다.
• 이 때 각 작업의 비용은 현재 작업이 어디에서 진행되고 있느냐에 따라 크게 달라진다. 저장장치 RAM에서는 모든 위치에 대한 접근 시간이 동일하지만, HDD같은 ROM에서는 그렇지 않다. ROM은 한 번에 여러 바이트를 읽어올 수 있고 시간은 오래걸린다는 특징이 있다. 즉, 만약 작업을 ROM에서 진행한다면 '링크 따라가기'에 오랜 시간이 걸릴 수 있다.
• 2-3-4 트리는 AVL과 비교했을 때 새로운 노드와 링크를 생성하는데 드는 비용은 적다.
• 결론 : 2-3-4 트리에서는 링크를 따라 '왔다 갔다'하는 작업을 최소화할 필요가 있다. => root로부터 내려가면서 바로바로 split을 진행해놓는다. => 추후 어떤 작업을 해도 parent는 split해줄 필요없이 한 자리가 남아있게된다.
• 메인메모리(RAM)에서는 큰 차이가 없을 수 있지만 HDD에서는 유용하다. Free Block List on File System 같이 하나하나에 많은 정보를 저장하는데, 이러한 자료를 관리하기 적절한 자료구조라고 할 수 있겠다.

B Tree

• key값을 담을 수 있는 block이 커질수록 하나의 노드에 많은 정보를 넣을 수 있다. HDD와 같은 ROM에서는 정보량에 따른 속도 차이가 거의 없으므로, 이를 최대화할 수 있다.
• 이러한 트리를 B 트리라고 한다.
• 노드의 갯수가 줄어들어 매우 유용하지만 핸들링해야 할 문제(몇개 이상부터 split할지 등)도 많아지므로 구조를 잘 설계해야 한다.

Red-Black Tree

• 2-3-4 트리와 매우 유사하지만 이를 다르게 표현한 것이라고 할 수 있다.
• 하나의 노드에 있는 key값들을 생각해보자. 해당 키값들은 Red-link로 연결되고, 다른 노드에 해당하는 key값들은 Black-link로 연결된다.
• 모든 root~leaf의 길목에는 같은 개수의 black-link가 존재한다. (2-3-4의 모든 leaf가 같은 거리에 있다)
• 모든 root~leaf의 길목에는 red-link가 연속으로 등장하지 않는다. (2-3-4의 key값중 중앙의 key값에서 각각 red-link로 연결)
• cf. 구글링을 해보니 보통 레드블랙 트리를 설명할 때 각 노드를 Red-Black으로 구분하지만 교수님께서는 link를 Red-Black으로 구별했다.
• 더 이상 자식이 없어 진행할 수 없는 노드(해당 트리에선 key와 거의 동일한 의미)까지 가면 해당 위치에서 보이는 Black-link의 개수는 동일하다.
• 연속으로 Red-link를 만나는 경우는 없다. (Red-link 다음은 Black-link이거나 No-link이다.)
• split은 연결되어있던 Red-link를 위쪽으로 옮겨주는 것으로 간단하게 가능하다. 2-3-4트리에서 노드를 추가로 생성했던 것과 비교했을 때 매우 효율적으로 보인다. 물론 조건이 깨질 경우 Rotation은 필요하다.
• Insert : red-link로 insert한 다음 rotation을 하거나, 애초에 내려가면서 split(red-link 위쪽으로 올리기, hold up)을 실행한다.