2-3-4 tree

2-3-4 트리란

이진트리가 한쪽으로 쏠리는 경우가 발생할수있는데 이를 해결하기위해 고안한 자료구조이다.

 

2-3-4 트리의 특징으로는

이진트리의 경우 하나의 노드는 하나의 데이터와 두개의 자식노드를 가질수 있는데 반해

2-3-4 트리의 경우, 세개의 데이터와 네개의 자식노드를 가질수있다.

 

2-3-4 트리라는 명칭은 가질수 있는 자식노드의 수때문에 나온것같다.

 

그렇다면 왜 1개 자식노드를 가지는 노드는 없을까?

삽입, 삭제과정에서 발생하는 연산을 보면 이해가 된다.

split할때 자식이 두개인 노드생성, merge할땐 부모노드가 가진 자식노드 갯수가 3이상이므로(두개 이상의 데이타를가짐)

1개 자식노드를 가지는 노드는 있을수가 없다. (아....정말 설득력 없네요....)

 

마지막으로 데이타를 추가할때 이진트리는 아래로 트리가 커가지만 2-3-4 트리는 위로 커간다. (split)

데이타를 삭제할때 이진트리는 아래에서 줄어들지만 2-3-4트리는 위에서 줄어든다 (merge)

 

이젠 데이터 삽입, 삭제연산에 대해 알아보자.

들어가기에 앞서 알아야할 것이 있는데,  2 node 란 1개 데이터 2개 자식노드, 3 node란 2개 데이터 3개 자식노드,

4 node란? ????~~~~~~ 이다 ㅎㅎㅎ

 

우선 삽입 연산이다.

삽입연산에서는 이것만 기억하면 된다. 삽입 연산중 만나는 4 node에 대해서 split해주면 된다.

총 두개의 그림 삽입

1부터 10까지 차례대로 삽입

다음은 삭제 연산이다.

 

삭제 연산에서 가장 중요한것은 2-3-4 트리의 삭제연산은 leafnode에서만 이루어진다는 점이다.

한가지 의문점이 든다.  삭제하려는 데이터가 internal node 에 위치한다면?

그럴때는 leafnode의 데이타중에 삭제하려는 데이터와 가장 가까운 노드를 찾아 서로 교환하면 된다.

삭제하려는 데이타의 바로 앞 자식노드 이동후 그 자식노드와 연결된 leafnode중에서 가장 큰 데이타와 교환한후,

leafnode에 위치한 데이타를 삭제해주면된다.

삭제 연산중 split 같이 균형을 맞추기위해 하는게 있다. 바로 merge와 redistribute이다.

삽입 연산과는 반대로 삭제 연산 중 만나는 2  node에 대해서 두 연산중 하나를 실행한다.

두개의 연산중 하나를 선택하는 기준은 형제노드의 갯수인데, 형제노드가 2 node면 merge, 3, 4 node면 redistribute를 수행한다. 

그림에서 형제노드 선택은 해당 노드 오른쪽으로 했다. 가장끝이라면 왼쪽 노드를 선택하면 되죠...허허

merge는 부모노드 한개, 형제노드 한개 데이타를 합쳐서 해당 노드를 데이타 3개를 만든다.

예외적으로 root의 경우 형제 노드가 존재하지 않으므로 두개(데이타가 한개일때 merge할지 redistribute할지 정하므로)의

자식노드의 데이터가 한개일 경우 merge를 실행한다. 

 

데이타 삽입의 경우 split을 통해 상위노드로 데이타로 추가되고, 반복되다가 root 노드가 4node가 되면 split 되고 높이가 1 증가된다.

데이타 삭제의 경우 redistribute를 통해 상위 노드의 데이타가 줄어들고, redistribute, merge를 반복되다가

root 노드가 2 node가 되면 높이가 1 감소되는것이다.

 

높이를 유지하는 이유는 노드 추가시 밑에서 증가하는게 아니라 위에서 증가하고, [root에서 split이 발생할때]

노드 삭제시 밑에서 줄어드는게 아니라, 위에서 줄어든다. [root에서 merge가 발생할때]

이거 생각한 사람 좀 짱인듯....

다른 self balancing 자료구조도 이와 비슷한 방식으로 하지 않았을까...라는 생각을 하며 red-black tree를 공부하자

 

개념 참조 : http://tultul.net/board/list.php?a=050000000000000000000003&w=