2-3-4 tree

-every node has 2, 3, or 4 childeren except leaves

모든 노드는 2~4개의 자식을 가진다 leaves제외.

- all leaves are at the bottom level of the tree

모든 leaves는 tree의 가장 bottom level에 있다.

EX)    

Insertion(top-down)

1)    Whenever insert encounter a 3-key node, the middle key is ejected and is placed in the parent node

insert가 3-key노드를 만날때마다 중간 키가 꺼내져서 parent노드로 간다

2)    If the root is a 3-key node, a new node is created

(To make sure there’s room for the new key in the left node.)

root가 3-key node일때 새 노드가 만들어진다

 Deletion(top-down)

1)    When remove encounters a 1-key node (except the root) it tries to steal a key from an adjacent sibling

만난 1-key node(root제외)를 제거할때 인접한 형제로부터 key를 가져온다.

2)    If no adjacent sibling has more than one key, the 1-key node steals a key from its parent The sibling is also absorbed

어떠한 인접한 형제노드도 key를 하나이상 가지고 있지 않다면 1-key node는 이것의 부모로부터 키를 하나 가져온다. 그리고 형제노드는 흡수된다

3)    If the parent is the root and contains only one key, and the sibling contains only one key, then the current and the sibling contains only one key, then the current 1-key node, its 1-key sibling, and the 1-key root are fused into one 3-key node that serves as the new root

만약 부모노드가 root이고 오직 하나의 키만 가지고 있으면서 형제노드가 오직 하나의 키만 가지고 있다면, 그래서 현재노드와 형제노드가 오직 하나의 키만가지고 잇으면 현재의 1-key node와 이것의 1-key 형제노드 그리고 1-key root는 3-key node의 root로 융합된다.

To make sure that a key can be removed from a leaf without leaving it empty.

키는 leaf로 부터 제거될 수 있어야 하며 빈채로 놔둘 수 없음을 명심!

(제거는 항상 leaf에서만 가능 즉, 삭제할 노드를 leaf로 밀어줘야함)

수업시간에 썼던 필긴데 이해가 잘 가지 않는다!

그래서 펌!

http://coyagi.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-234-%ED%8A%B8%EB%A6%AC

http://thesoul214.tistory.com/103

http://dol9.tistory.com/134

여기가 더 잘되있는듯