7/23/02 Amir Kamil Topic: AVL Trees, B-Trees Announcement: AVL Trees: - AVL trees are balanced BSTs, so every node has subtrees with a height difference of at most one. - Insertion: a) Insert into an AVL tree as you would a normal BST. b) Find the first unbalanced ancestor of the inserted element, perform a restructuring operation on it. Restructure algorithm: Let node z be the unbalanced node to restructure. Let node y be the child of z with greater height. Let node x be the child of y with greater height. x is a grandchild of z. Now x, y, and z have four other children. (z has the child other than y, y has the child other than x, x has two children.) Order x, y, and z as a, b, c as in an inorder traversal. Order the four children t0, t1, t2, t3 as in an inorder traversal. Replace z with b. Let a be b's left child, and let t0 and t1 be a's children. Let c be b's right child, and let t2 and t3 be c's childre. Ex: ---18--- / \ 12 28 / \ / \ 6 14 21 30 / \ 19 26 Insert 23 into above tree. First, insert as you would into a BST: ---18--- / \ 12 28 / \ / \ 6 14 21 30 / \ 19 26 / 23 Now first unbalanced ancestor of 23 is 28, so z = 28. Highest child of 28 is 21, so y = 21. Highest child of 21 is 26, so x = 26. Now the inorder ordering of x, y, z is 21, 26, 28, so a = 21, b = 26, c = 28. The four children are 19, 23, (empty), 30, in order, so T0 = 19, T1 = 23, T2 = (empty), T3 = 30. 28 <- z, c / \ y, a -> 21 30 <- T3 / \ T0 -> 19 26 <- x, b / \ T1 -> 23 o <- T2 Now replace z with b, with children a and c. 26 <- b / \ a -> 21 28 <- c Let the children of a be T0, T1, and of c be T2, T3. 26 <- b / \ a -> 21 28 <- c / \ / \ 19 23 o 30 Resulting tree: ---18--- / \ 12 26 / \ / \ 6 14 21 28 / \ \ 19 23 30 - Deletion: Remove from the AVL tree as if it were a normal BST. Let n = the removed node. While the tree is not balanced: Find the first ancestor of n that is unbalanced, call it z. Restructure z. n = z. As you can see from the above algorithm, it may take more than one restructuring to restore balance after a removal. Otherwise the algorithm is the same as insertion. B-Trees: - Properties: The tree has an "order" m. All nodes except the root node have at least ceiling(m/2) and at most m children The root node has at most m children. Each node has up to m-1 keys, with one child on either side of each key. Keys are ordered. Within a node, they are in increasing order. Every key in the child to the left of a key is less than that key, every key in the child to the right of a key is greater that that key. All external nodes are empty. - We will use 2-3-4 (order 4) trees as examples. Ex: (16)---- / \ (8 14) (21) / | \ / \ (3 6) (11) (15) (18) (24) | | | | | | | | | | | o o o o o o o o o o o - Insertion: Insert the item in the appropriate spot in the last non-empty level. If the node in which the item is inserted overflows (has more than 3 keys or 4 children), perform the split operation: Let v be the overflowed node, k1, k2, k3, k4 be its keys. Create new nodes v' and v'', v' with keys k1 and k2, v'' with key k4. v' gets the first 3 children of v, and v'' gets the other 2. Move k3 to v's parent, and make v' and v'' the nodes to the left and right of k3, respectively. Repeat split on parent node if necessary. Ex: Insert 5 in the above tree. (16)---- / \ (8 14) (21) / | \ / \ (3 5 6) (11) (15) (18) (24) | | | | | | | | | | | | o o o o o o o o o o o o No overflow, so we're done. Now let's insert 4 into the above tree. (16)---- / \ (8 14) (21) / | \ / \ (3 4 5 6) (11) (15) (18) (24) | | | | | | | | | | | | | o o o o o o o o o o o o o The node overflowed, so we need to do a split. We split the node into two nodes (3 4) and (6) and move 5 up to the node's parent. (16)---- / \ (5 8 14) (21) | \ / \ (3 4) (6) (11) (15) (18) (24) | | | | | | | | | | | | | o o o o o o o o o o o o o Now we set 4's left child to be (3 4) and its right child to be (6). (16)---- / \ (5 8 14) (21) / | | \ / \ (3 4) (6) (11) (15) (18) (24) | | | | | | | | | | | | | o o o o o o o o o o o o o Since the parent node didn't overflow, we're done. - Deletion: First, we swap the item we want to replace with the rightmost item in the left child of the item to be deleted. Now the item we want to delete is in the last non-empty level. We remove the item and its (empty) left child. If the node containing the item underflows (has no keys or only one child), we restructure as follows: If either the sibling immediately to the left or immediately to the right has 2 or 3 keys, we perform a transfer operation: We move a child from the sibling to the underflowed node. We move a key from the sibling to the parent node. We move a key from the parent node to the underflowed node. Otherwise, we perform a fusion operation. We merge the underflowed node with a sibling. We move a key from the parent node to the new combined node. We restructure the parent node if it underflows. Ex: (transfer operation) Remove 8 from the above tree. First we swap 8 with the rightmost item in its left child, 6. (16)---- / \ (5 6 14) (21) / | | \ / \ (3 4) (8) (11) (15) (18) (24) | | | | | | | | | | | | | o o o o o o o o o o o o o Then we remove 8 and its left child. (16)---- / \ (5 6 14) (21) / | | \ / \ (3 4) ( ) (11) (15) (18) (24) | | | | | | | | | | | | o o o o o o o o o o o o Now we move a child from the empty node's sibling to the empty node. (16)---- / \ (5 6 14) (21) / | | \ / \ (3 4) ( ) (11) (15) (18) (24) | | | | | | | | | | | | o o o o o o o o o o o o We move 4 up from the sibling to the parent, and move 5 down from the parent to the empty node. (16)---- / \ (4 6 14) (21) / | | \ / \ (3) (5) (11) (15) (18) (24) | | | | | | | | | | | | o o o o o o o o o o o o Now we're done. Ex: (fusion operation) Remove 15 from the above tree. Now 15 is already at the bottom, so we remove it and its left child. (16)---- / \ (4 6 14) (21) / | | \ / \ (3) (5) (11) ( ) (18) (24) | | | | | | | | | | | o o o o o o o o o o o We merge the empty node with a sibling, (11). (16)---- / \ (4 6 14) (21) / | | / \ (3) (5) (11 ) (18) (24) | | | | | | | | | | | o o o o o o o o o o o We move a key down from the parent to the combined node. (16)---- / \ (4 6 ) (21) / | | / \ (3) (5) (11 14) (18) (24) | | | | | | | | | | | o o o o o o o o o o o Since the parent node didn't underflow, we're done.