13-2. 2-3-4 트리

02. 2-3-4 트리

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,lmchild는 각각 2-노드의 왼쪽 자식 노드 및 좌중간 자식 노드이라 하고,lkey를 키값이라 하자.그러면 루트가 lchild인 모든 2-3-4 서브트리 키값은 lkey보다 작고,루트가 mchild인 모든 2-3-4서브트리 키값은 lkey보다 크다.

 

③ lchild,lmchild 및 rmchild를 각각 3-노드의 왼쪽 자식 노드,좌중간 자식 노드 및 우중간 자식 노드라 하고 lkey,mkey를 이 노드의 키값이라 하자.그러면 다음이 성립한다.

   a. lkey < mkey

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

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

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

 

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

   a. lkey < mkey < rkey

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

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

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

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

 

⑤ 모든 잎 노드들은 같은 레벨에 있다.

조건을 만족하는 2-3-4트리의 예

 

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

- 2-3-4트리에서는 2-노드와 3-노드에 대한 트리 재구성의 확률이 2-3트리에서 보다 작기 때문에 삽입/삭제 연산이 효율적임

 

- 삽입 연산 시 문제가 되는 4-노드 는 그 위치에 따라 세 가지 경우로 구분하여 분리함

① 4-노드가 루트인 경우

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

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

 

 

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

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