과제
AVL.in
I 6
I 2
I 9
I 1
I 5
binary search tree를 만들자.
AVL.out
inorder preversal 출력
preorder preversal 출력 결과
하나씩 하나씩 그 다음에 avl 깨지는 부분 BN
써주기
AVL 트리 수정 없이
그냥 최초 깨지는 부분 계속
2-3-4 Tree
-every node has 2,3, or 4 children except leaves
-all leaves are at the bottom level of the tree
insertion(top-down)
1) whenever insert encounters a 3-key node,
the middle key is ejected and is placed in the parent node.
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 leaf 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.
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.
3) If the parent is the root and contains only one key,
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.
to make sure that a key can be removed from a leaf without leaving it empty