10-12-2012, 01:36 PM
Multi-Way search Trees
trees.ppt (Size: 506 KB / Downloads: 24)
Updating
Insertion:
Find the appropriate leaf. If there is only one item, just add to leaf.
Insert(23); Insert(15)
If no room, move middle item to parent and split remaining two items among two children.
Insert(3);
Delete
If item is not in a leaf exchange with in-order successor.
If leaf has another item, remove item.
Examples: Remove(110);
(Insert(110); Remove(100); )
If leaf has only one item but sibling has two items: redistribute items. Remove(80);
Details
1. Swap(85, 90) //inorder successor
2. Remove(85) //empty node created
3. Merge with sibling
4. Drop item from parent// (50,90) empty Parent
5. Merge empty node with sibling, drop item from parent (95)
6. Parent empty, merge with sibling drop item. Parent (root) empty, remove root.
(2,4) Trees
Size Property: nodes may have 1,2,3 items.
Every node, except leaves has size+1 children.
Depth property: all leaves have the same depth.
Insertion: If during the search for the leaf you encounter a “full” node, split it.
Removal
As with BS trees, we may place the node to be removed in a leaf.
If the leaf v has another item, done.
If not, we have an UNDERFLOW.
If a sibling of v has 2 or 3 items, transfer an item.
If v has 2 or 3 siblings we perform a transfer
If v has only one sibling with a single item we drop an item from the parent to the sibling, remove v. This may create an underflow at the parent. We “percolate” up the underflow. It may reach the root in which case the root will be discarded and the tree will “shrink”.
Red Black Trees, Insertion
Find proper external node.
Insert and color node red.
No black depth violation but may violate the red-black parent-child relationship.
Let: z be the inserted node, v its parent and u its grandparent. If v is red then u must be black.