[자료구조] - 2-3 Tree

 

 

 

2-3 Tree

2-3트리는 검색 트리이지만 BST는 아닙니다.

차수가 3인 노드가 존재할 수 있으므로, Binary가 아니기 때문입니다.

2-3 Tree는 트리의 높이가 균형을 이루며 내부노드의 차수가 2 또는 3인 균형 탐색트리입니다.

 

 

 

 

 

2-3 Tree 조건

2-3 Tree에는 Internal Node와 External Node의 개념이 존재합니다.

Internal Node(내부노드)는 Key가 들어있는 내부 노드이며, 
External Node(외부노드)는 데이터가 들어있지 않은 노드로써 Internal Node의 Leaf Node의 자식으로 존재하는 가상의 노드입니다.

 

2-3 Tree에서 각각의 내부 노드는 2-Node 이거나 3-Node 입니다.

중복된 Key는 허용하지 않습니다.

2-Node는 1개의 Key를 가지며, 2개의 자식 노드를 가집니다.
3-Node는 2개의 Key를 가지며, 3개의 자식 노드를 가집니다.

leftChild와 middleChild를 각각 2-node의 왼쪽 자식 및 중간 자식이라 하겠습니다.

leftKey를 해당 노드의 key라 하겠습니다.

루트가 leftChild인 모든 서브트리의 키 값은 leftKey보다 작고,
루트가 middleChild인 모든 서브트리의 key 값은 leftKey보다 큽니다.

leftChild와 middleChild, rightChild를 각각 3-node의 왼쪽, 중간 및 오른쪽 자식이라 하겠습니다.

leftKey, rightKey를 해당 노드의 key라 하겠습니다.

rightKey는 leftKey보다 큽니다.

루트가 leftChild인 모든 서브트리의 키 값은 leftKey보다 작고,
루트가 middleChild인 모든 서브트리의 key 값은 leftKey보다 크며 rightKey보다 작습니다.
루트가 rightChild인 모든 서브트리의 key 값은 rightKey보다 큽니다.

 

 

 

모든 외부 노드는 같은 레벨에 있으며,
트리의 높이가 h일 때 외부 노드는 h+1에 존재합니다.

 

 

 

예시

Root가 2-Node인 2-3 Tree

Root가 3-Node인 2-3 Tree

 

Leaf Node인 External Node에는 데이터가 들어있지 않습니다.

 

 

 

 

 

앞으로의 설명에 등장하는 Leaf Node는 External Node가 아닌 Internal Node의 Leaf Node를 의미합니다.

 

 

 

 

 

 

 

검색

검색은 너무나 쉽습니다.

찾으려는 값을 Root 노드의 leftKey, rightKey와 비교합니다. 

leftKey보다 작은 경우 - leftSubtree를 탐색합니다.

leftKey보다 크고, rightKey보다 작은 경우 - middleSubtree를 탐색합니다.

rightKey보다 큰 경우 - rightSubtree를 탐색합니다.

 

 

 

 

 

 

 

 

 

 

추가

우선 노드를 추가할 때, 기본적인 규칙은 다음과 같습니다.

반드시 Leaf Node에 데이터를 삽입합니다.

부모노드에 빈 공간이 있다고 해서 부모 노드에 삽입하지 않습니다. 반드시 데이터는 Leaf Node에 삽입합니다.

1. 값이 추가될 위치를 찾습니다. 

2. 추가될 Leaf Node가 용량을 초과하지 않았다면 오름차순으로 데이터를 삽입합니다.
만약 용량을 초과하였다면 Split(분할)을 수행하여야 합니다.

 

 

 

Split(분할)

Split은 다음과 같은 과정입니다.

추가될 데이터를 포함하여 중앙값을 결정합니다.

중앙값을 부모 노드에 추가시키며 중앙값보다 작은 값들은 왼쪽 서브트리, 중앙값보다 큰 값들은 오른쪽 서브트리가 됩니다.

부모 노드가 없다면 새로 생성하며,
부모 노드에서도 용량이 가득찼다면 똑같이 Split 하는 과정을 반복합니다.

 

 

예시를 통해 설명하도록 하겠습니다.

 

 

 

우선 초기 상태입니다.

 

70 삽입

우선 기본 규칙에 따라 반드시 리프 노드에 삽입하여야 합니다.

Leaf Node가 2-Node인 경우 데이터를 그대로 삽입하여 3-Node로 만듭니다.

삽입하였을 때 Left Key가 Right Key보다 크다면 위치를 바꾸어줍니다.

 

 

 

30 삽입

마찬가지로 Leaf Node에 삽입합니다.

삽입할 때 노드가 가득 차 삽입할 수 없는 경우 Split을 수행합니다.

우선 해당 노드의 중간값을 찾습니다.
해당 중간값을 부모 노드로 하는 서브트리를 만들어줍니다.

높이를 맞추기 위해 새롭게 만든 서브 트리의 루트를 이들의 부모 노드와 합칩니다.

이때 부모 노드가 2-Node인 경우 바로 삽입이 가능하나,
3-Node인 경우 부모 노드에서 중간값을 찾고 서브트리를 만드는 위의 과정을 반복합니다.

 

 

 

 

 

 

60 삽입

마찬가지로 Leaf Node에 삽입합니다.

 

 

 

 

 

 

 

 

 

 

 

 

삭제

우선 삭제의 경우 Rotation(회전)과 Merge(병합)의 개념이 사용되므로 이부터 알아보도록 하겠습니다.

 

Rotation (회전)

원소가 삭제되는 노드를 기준으로,
삭제되는 노드의 형제노드의 원소 하나를 부모 노드로,
부모 노드의 원소 하나를 자신의 노드로 가져와 회전시키는 것을 의미합니다.

삭제되는 노드의 형제 노드중 3-Node가 있는 경우 회전(Rotation)이 가능합니다.

 

 

 

 

 

 

 

 

Merge (병합)

원소가 삭제되는 노드를 기준으로,
삭제되는 노드의 직후 형제노드(혹은 직전 형제노드)와 자신 사이에 포함되는 부모 원소를 합치는 것을 의미합니다.

merge 이후 노드의 용량이 초과되었다면 Split을 수행합니다.

삭제되는 노드의 형제 노드중 3-Node가 없는 경우 병합(Merge)이 필요합니다.

 

 

 

 

 

 

 

이후 설명할 모든 상황에서, 다음과 같은 알고리즘을 사용한다고 하겠습니다.

Non Leaf Node의 삭제 시, 삭제되는 Key의 Left Subtree의 최댓값으로 비어있는 부분을 채워주도록 하겠습니다.

RightSubtree의 최솟값을 가져오는 경우 이후 존재하는 값들을 왼쪽으로 한칸씩 당겨주어야 하지만, 
LeftSubtree의 최댓값을 가져오는 경우 바로 가져올 수 있기 때문에 효율적입니다.

 

Rotation은 최좌측 서브트리를 제외하고는 반드시 왼쪽 형제노드를 확인하여 가능할 때만 발생한다고 하겠습니다.

최좌측 서브트리는 항상 왼쪽 형제노드가 없으므로 이 경우에만 특별하게 오른쪽 형제노드를 확인합니다.

이 또한 마찬가지로 오른쪽 형제노드에서 Rotation을 하는 경우 값들을 한칸씩 당겨주어야 하기 때문에 비효율적이므로 위와같은 방법을 사용합니다.

 

Rotation은 최좌측 서브트리를 제외하고는 반드시 왼쪽 형제노드를 우선적으로 확인도록 하겠습니다.

 

 

 

 

 

 

 

 

 

삭제의 4가지 상황

• 3-Node인 Leaf Node의 삭제
• 2-Node인 Leaf Node의 삭제
• 3-Node인 Non Leaf Node의 삭제
• 2-Node인 Non Leaf Node의 삭제

 

트리에서의 Non Leaf Node의 삭제는 모두 Leaf Node의 삭제 형태로 바꿔주어 생각할 수 있습니다.

 

 

 

 

 

3-Node인 Leaf Node의 삭제

가장 간단한 케이스입니다.

바로 삭제해준 후, 남아있는 key가 rightKey인 경우 위치를 옮겨줍니다.

 

 

아래는 예시입니다.

70 삭제

 

 

 

90 삭제

 

 

 

 

 

 

 

 

2-Node인 Leaf Node의 삭제

해당 경우 두가지 상황이 발생할 수 있습니다.

• 형제 노드중 3-Node가 있는 경우
• 형제 노드중 3-Node가 없는 경우

 

삭제되는 노드의 형제 노드중 3-Node가 있는 경우 회전(Rotation)이 가능합니다.
삭제되는 노드의 형제 노드중 3-Node가 없는 경우 병합(Merge)이 필요합니다.

 

 

Rotaion이 가능하다면 Rotation을,
Rotation이 불가능하다면 Merge를 수행합니다.

 

앞으로의 예시에서는 최좌측만 오른쪽을 보고, 나머지는 왼쪽 형제를 본 뒤, rotation이 불가능하다면 merge 하겠습니다.

 

 

 

 

 

 

 

 

1. 삭제되는 2-Node의 형제 노드중 3-Node가 있는 경우

Leaf Node에서 값을 제거한 뒤, 회전(Rotation)시킵니다.

 

 

 

 

 

저희는 최좌측 노드를 제외하고는 바로 왼쪽 형제만 볼 것이기에, 왼쪽 형제가 3-Node가 아니라면 merge 합니다.

이건 형제 노드중 3Node가 있으나 바로 왼쪽에 존재하지 않아 merge 하였습니다.

 

 

 

 

 

 

 

 

 

 

2. 삭제되는 2-Node의 형제 노드중 3-Node가 없는 경우

Leaf Node에서 값을 제거한 뒤, 회전(Rotation)이 불가능하므로 병합(merge)시킵니다.

삭제되는 노드의 직후 형제노드와 현재 노드 사이에 포함되는 부모 원소를 합침

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3-Node인 Non Leaf Node의 삭제

Leaf Node의 삭제 형태로 바꾸어 해결합니다.

2번째 줄에서, merge 이후 empty 노드의 형제 노드 중 3-Node가 있으므로 Rotation

 

 

 

 

 

 

2-Node인 Non Leaf Node의 삭제

마찬가지로 Leaf Node의 삭제 형태로 바꾸어 해결합니다.

2번째 줄에서, merge 이후 empty 노드의 형제 노드 중 3-Node가 있으므로 Rotation이 가능하지만, 왼쪽 노드만 확인하기로 했으므로 merge

 

 

 

 

 

혹은 왼쪽만 본다는 조건이 없다면 다음도 가능합니다.

empty 노드의 형제 노드 중 3-Node가 있으므로 Rotation하는 예시

 

삭제던 삽입이던 여러가지 형태로 나타날 수 있습니다.