|
This leads to the relativly rear re-balancing of the tree, on contrary with AVL? trees. |
|
This leads to the relativly rear re-balancing of the tree, on contrary with AVL tree. |
|
If some inner node is in illegale state then one of two possible scenarios is true: * Its "brother" (the son of the same parent node) can transfer one of its sons to it and return it into a legal state. In that case, after updating separation values in parent and two sons the operation ends. * Its brother is on the lower bound too. In that case both these nodes are merged into one (with a number of sons on a upper bound) and the action is transferred to parent node, since now it lost one of its sons. The action proceeds while either some node stays in legall state after delete or the root has one son, in which case its deleted. Inserts: If no inner node is in illegale state as a result of insert then finish If some node has more than upper bound sons then split it into two nodes, each one with lower bound sons. And proceed the action recursivly in parent node. The action stops when either a node is in legal state or root is split into two nodes and new root is inserted. Searches: Search is performed by following separation values to the tree leaves. Notes: * The root of the tree is a special node which can have from 2 to upper bound sons. * Tarjan? has proved that amortized number of splits/merges is 2. |
![[Home]](wikipedia.png)