기본적인 내용은 건너뛰겠습니다.
2-3 트리를 포함한 2-3-4 트리 혹은 Multi-way 탐색 트리 까지 공통점이 있습니다.
한 노드에 들어갈 수 있는 자식 노드의 개수가 m개라고 하겠습니다.
1. 루트 노드는 적어도 2개의 자식 노드가 있어야 합니다.
2. 모든 leaf 노드는 같은 높이에 위치해야합니다. 즉, 항상 균형잡힌 형태를 유지해야합니다.
3. 루트 노드를 제외한 모든 노드는 $\lceil \frac{m}{2} \rceil$ 개의 자식 노드들이 있어야합니다.
이번에 소개할 내용은 2-3 트리이며, m이 3인 트리중 하나라고 할 수 있습니다.
위 공통점에 해당하는 내용을 잘 생각하고 읽어주세요.
아래 예시로 드는 모든 2-3 트리들의 그림은 다음과 같은 공통점이 있습니다.
박스가 하나인 경우 --> 2-node
박스가 두개인 경우 --> 3-node
검색
2-node인 경우
해당 노드의 원소보다 작다면 left 서브트리에 대해
크다면 middle 서브트리에 대해 재귀적으로 검색합니다.
3-node인 경우
해당 노드의 첫번째 값보다 작은 경우 left 서브트리,
첫번째 값보다는 크지만, 두번째 값보다는 작은 경우 middle 서브트리,
두번째 값보다 큰 경우 right 서브트리에 대해 재귀적으로 검색합니다.
물론 첫번째 값이나 두번째 값과 X가 같다면 해당 노드를 반환하여 검색을 완료합니다.
만약 leaf 노드를 만났으나, 찾고자 하는 값이 없다면 null을 반환하도록 하여 재귀 호출을 끝내도록 합니다.
추가
기본적인 추가의 경우
2-node로의 추가의 경우 단순히 3-node로 만들어주면 추가가 완료됩니다.
3-node를 초과하여 분할 해야하는 경우
3-node를 초과하여 추가되는 경우 분할이 필요합니다.
분할은 초과된 노드에서 중간값을 찾아 부모노드로 만들어주면 분할이 완료됩니다.
하지만 단순히 부모노드로 만들어준다면 트리가 불균형해지므로 작업이 필요합니다.
따라서 높이가 같은 서브트리 2개를 각각 A와 B라고 하겠습니다.
이 경우, 두 서브트리의 루트를 합하여 3-node로 만들어줍니다.
A 서브트리의 left 서브트리는 그대로 left가 되고 B 서브트리의 left 서브트리는 middle, middle 서브트리는 right 서브트리로 만들어주면서 3-node로 만들어줄 수 있습니다.
이제 병합이 연속적으로 일어나는 경우를 설명하겠습니다.
이때 middle 서브트리가 분할되어 다음과 같은 모양이 됩니다.
이 서브트리는 불균형 하므로 40을 부모노드와 먼저 합치도록 하겠습니다.
이때 부모노드와 합쳐진 결과는 다시 3-node를 초과하므로 분할 대상이 됩니다.
따라서 분할하게 되면 최종적인 모양은 다음과 같습니다.
삭제
기본적인 삭제의 경우
3-node에 삭제의 대상이 있다면 단순히 2-node로 만들어줍니다.
회전이 필요한 경우
삭제되는 노드의 형제 노드가 3-node인 경우 회전이 가능합니다.
회전이 가능한 형태를 찾아 회전시키는 예시를 하나 들어보겠습니다.
이때 형제 노드인 3-node에서 최소인 값이 부모노드로 회전되어 들어감을 확인해주세요.
병합이 필요한 경우
삭제되는 노드의 형제 노드가 2-node인 경우 병합이 필요합니다.
회전을 시키더라도 아무 의미가 없기 때문입니다.
위 두 형태를 잘 기억해주세요.
병합이 필요한 트리의 첫번째 예시를 하나 들어보겠습니다.
위 예시에서 파란색 삼각형을 잘 보면 위에서 설명한 병합의 첫번째 형태임을 알 수 있습니다.
다음은 두번째 예시입니다.
파란색 삼각형은 첫번째 형태와 같으며, 보라색 삼각형은 첫번째 형태의 y축 대칭인 구조입니다.
이는 두가지 구조로 병합이 가능하며, 어느 구조로 병합하던 상관 없습니다.
아래 주어진 트리에 대해 두 가지 예시를 들어보겠습니다.
아래는 첫번째 예시입니다.
루트 노드에서 15를 삭제한 경우입니다.
이 경우 루트 노드의 middle 서브트리에서 최솟값(혹은 left 서브트리에서 최댓값)을 찾아 삭제된 위치로 옮겨주어야 합니다.
만약 middle이 leaf이며 2-node인 경우였다면, 첫번째 병합의 형태임을 알 수 있습니다.
위 예시에서 굳이 회전임을 언급하지 않은 이유는 트리의 높이가 2보다 큰 경우에 대해 우선적으로 회전시키지 않기 때문입니다.
먼저 middle 서브트리에서 최솟값(또는 left 서브트리에서의 최댓값)을 찾아 삭제된 위치로 옮겨준 후, 재귀적으로 병합 또는 회전시켜 트리를 재구성해주어야 합니다.
이유는 루트 노드에서 left 서브트리에 있는 어떤 원소들보다 크며
middle 서브트리에 있는 어떤 원소들보다 작아야 하기 때문에
middle 서브트리에 있는 최솟값(또는 left 서브트리에서의 최댓값)이 삭제된 위치로 옮겨져야합니다.(left < 왼쪽 값 < middle < 오른쪽 값 < right)
아래는 두번째 예시입니다.
루트 노드에서 30을 삭제한 경우입니다.
이번에도 마찬가지로 middle 서브트리에서 값을 찾아야합니다.
삭제된 원소에 들어갈 값은 middle 서브트리에 있는 모든 원소중에서 가장 큰 값이 되어야합니다.
(마찬가지로 right 서브트리에서의 최솟값도 가능합니다.)
따라서 middle 서브트리의 최댓값인 25를 삭제된 위치로 옮겨줍니다.
트리의 불균형 해결
병합의 결과로 만들어진 트리가 불균형한 경우 해결하는 방법을 두가지 예시를 들어 설명하겠습니다.
먼저 첫번째 예시입니다.
먼저 불균형한 트리를 높이가 같은 두개의 서브트리 A, B로 나눕니다.
이때 B서브트리의 루트 노드가 2-node인 경우,
먼저 A와 B 서브트리의 루트 노드를 합친 후,
3-node를 루트 노드로 가지는 트리로 재구성 해주면 됩니다.
문제는 다음 예시입니다.
B 서브트리의 루트 노드가 3-node인 경우입니다.
이전 예시와 같이 A, B 서브트리로 나눈다고 했을 때, B 서브트리의 루트노드가 3-node인 경우 추가적인 작업이 필요합니다.
먼저 서브트리들의 루트노드끼리 합쳐 3-node를 초과하는 노드를 루트노드로 가지는 트리로 재구성 합니다.
이후 초과된 노드를 분할하여 트리를 재구성 해줍니다.
