[자료구조] 멀티웨이 탐색트리(2)

2-3 트리(2-3tree)

• 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리
• 2-노드 (2개의 자식 노드; 차수가 2)와 3-노드만(3개의 자식 노드; 차수가 3)으로 구성되는 특수한 형태의 B트리
• 2-노드 혹은 3-노드라는 제약이 내부 노드에만 해당함 → 모든 잎 노드는 같은 레벨에 있어야 한다는 제약만 존재

2-3트리(2-3tree) 의 조건

• 각 내부 노드는 2-노드이거나 3-노드이다.
• 2- 노드는 1개의 키 값을 3-노드는 2개의 키 값을 갖는다.
• lchild, mchild를 각각 2-노드 의 왼쪽 자식 및 중간 자식 이라 하고, lkey가 이 2-노드의 키 값이라 하자. 그러면 루트가 lchild인 모든 2-3 서브 트리 키 값은 lkey 보다 작고, 루트가 mchild인 모든 2-3 서브 트리 키 값은 lkey 보다 크다.
• lchild, mchild 및 rchild 를 각 3-노드 의 왼쪽, 중간 및 오른쪽 자식이라 하고, lkey 및 rkey 를 이 노드의 두 키값이라 하면, 다음이 성립

→ lkey < rkey

→ 루트가 lchild 인 모든 2-3 서브 트리 키 값은 lkey 보다 작다.

→ 루트가 mchild인 모든 2-3 서브 트리 키 값은 rkey 보다 작고, lkey 보다 크다.

→ 루트가 rchild 인 모든 2-3 서브 트리 데이터는 rkey 보다 크다.

• 모든 잎 노드는 같은 레벨에 있다.

2-3 트리의 삭제

• 2-3 트리의 삭제에서 잎 노드가 아닌 노드의 키를 삭제하면 그 곳을 다른 키로 대체해야 함
• 일반적으로 삭제한 키의 왼쪽 서브 트리에서 가장 큰 키 값이나 오른쪽 서브 트리에서 가장 작은 키 값을 선택하여 대체함

2-3-4 트리의 정의

• 2-3 트리를 확장하여 4개의 자식을 가진 4-노드 를 허용하는 탐색 트리
• 2-3-4 트리는 2-3트리보다 삽입과 삭제가 용이함
• 2-3-4 트리에서는 2-노드와 3-노드에 대한 트리 재구성 확률이 2-3 트리에서 보다 작기 때문에 삽입 및 삭제 연산을 수행하는데 효율적임.

2-3-4 트리의 조건

• 각각의 내부 노드는 2-노드, 3-노드 및 4-노드이다. 이때 2-노드는 1개의 키 값, 3-노드는 2개의 키 값, 4-노드는 3개의 키 값을 갖는다.
• lchild , mchild 는 각각 2-노드의 왼쪽 자식 노드 및 좌 중간 자식 노드라 하고, lkey 를 키 값이라 하자. 그러면 루트가 lchild인 모든 2-3-4 서브 트리 키 값은 lkey 보다 작고, 루트가 mchild 인 모든 2-3-4 서브 트리 키 값은 lkey 보다 크다.
• lchild , mchild 및 rchild 를 각각 3-노드 왼쪽 자식 노드, 좌중간 자식 노드 및 우중간 자식 노드라 하고 lkey, mkey 를 이 노드의 키 값이라 하자. 그러면 다음이 성립한다

→ lkey < mkey

→ 루트가 lchild 인 모든 2-3-4 서브 트리 키 값은 lkey 보다 작다.

→ 루트가 lmchild 인 모든 2-3-4 서브 트리 키 값은 lkey보다 크고 mkey 보다 작다.

→ 루트가 rmchild 인 모든 2-3-4 서브 트리 키 값은 mkey 보다 크다.

• lchild, lmchild ,rmchild 및 rchild 를 각 4-노드의 왼쪽, 좌중간, 우중간 및 오른쪽 자식이라고 하고, lkey, mkey 및 ,rkey 를 이 노드의 키 값이라 하면 다음이 성립된다.

→ lkey < mkey < rkey

→ 루트가 lchild 인 모든 2-3-4 서브 트리 키 값은 lkey 보다 작다.

→ 루트가 lmchild 인 모든 2-3-4 서브 트리 키 값은 mkey 보다 작고 lkey 보다 크다.

→ 루트가 rchild 인 모든 2-3-4 서브 트리 키 값은 rkey 보다 크다.

2-3-4 트리의 삽입 연산

• 2-3-4 트리에서는 2-노드와 3-노드에 대한 트리 재구성의 확률이 2-3 트리에서 보다 작기 때문에 삽입/삭제 연산이 효율적임
• 삽입 연산의 문제가 되는 4-노드는 그 위치에 따라 세 가지 경우로 구분하여 분리

→ 4-노드가 루트인 경우

→ 4-노드의 부모가 2-노드인 경우

→ 4-노드의 부모가 3-노드인 경우

2-3-4 트리의 삭제 연산

• 잎 노드에 있는 키 값은 단순히 삭제하면 됨

레드 블랙 트리

레드 블랙 트리의 정의

• 효율적인 기억장소 사용을 위하여 2-3-4 트리를 이진 트리로 나타낸 탐색 트리
• 레드 간선과 블랙 간선의 서브 트리 포인터를 가짐
• 레드 간선은 2-3-4 트리의 한 노드 내에 있던 노드의 관계 이고, 블랙 간선은 2-3-4 트리의 부모-자식 관계임
• 레드 블랙 트리의 탐색 방법은 보통의 이진 탐색 트리의 탐색 알고리즘과 동일

3-노드에 대응하는 레드 블랙 트리

• 구분을 위해 레드 간선은 점선으로 나타내고 블랙 간선은 실선으로 나타냄

레드 블랙 트리에서 삽입 연산을 위한 노드 분리

• 4-노드가 루트 노드인 경우 레드 블랙 트리의 노드 분리
• 점선(레드간선) → 실선(블랙간선)