AVL trees. An AVL tree is a BST where the height of every node and that of its sibling dif...

AVL trees. An AVL tree is a BST where the height of every node and that of its sibling differ by at most 1. (The oldest balanced tree algorithms are based on using rotations to maintain height balance in AVL trees.) Show that coloring red links that go from nodes of even height to nodes of odd height in an AVL tree gives a (perfectly balanced) 2-3-4 tree, where red links are not necessarily left-leaning. Extra credit: Develop an implementation of the symbol-table API that uses this as the underlying data structure. One approach is to keep a height field in each node, using rotations after the recursive calls to adjust the height as necessary; another is to use the red-black representation and use methods like moveRedLeft() and moveRedRight() in exercise3.3.39 and exercise3.3.40.

Exercise 3.3.39:

Delete the minimum. Implement the de1eteMin() operation for red-black BSTs by maintaining the correspondence with the transformations given in the text for moving down the left spine of the tree while maintaining the invariant that the current node is not a 2-node.

Solution:

private Node moveRedLeft(Node h){ // Assuming that h is red and both h.left and h.left.left// are black, make h.left or one of its children red.flipColors(h);if (isRed(h.right.left)){h.right = rotateRight(h.right);h = rotateLeft(h);}return h;}public void deleteMin(){if (!isRed(root.left) && !isRed(root.right)) root.color = RED;root = deleteMin(root); if (HsEmptyO) root.color = BLACK;}private Node deleteMin(Node h){if (h.left == null)return null;if (!isRed(h.left) && !isRed(h.left.left))h = moveRedLeft(h);h.left = deleteMin(h.left);return balance(h);}

This code assumes a ba1ance() method that is identical to the last five lines of the recursive put() method in algorithm3.4 except that the left rotation occurs whenever the right child is red (even if the left child is also red).

private Node ba1ance(Node h){if (isRed(h.right)) h = rotateLeft(h);if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);if (isRed(h.left) && isRed(h.right)) flipColors(h);h.N = size(h.left) + size(h.right) + 1;return h;}

The code also uses the following flipColors() implementation that complements the three colors.

private void flipColors(Node h){h.color = !h.color;h.left.color = !h.left.color;h.right.color = !h.right.color;return h;}

This generalizes the flipColors() method given in the text for insertion, which flips the color of the parent from BLACK to RED and the color of the two children from RED to BLACK. For deletion, we need to flip the color of the parent from RED to BLACK and the color of the two children from BLACK to RED.

Exercise 3.3.40:

Delete the maximum. Implement the de1eteMax() operation for red-black BSTs. Note that the transformations involved differ slightly from those in the previous exercise because red links are left-leaning.

Solution:

private Node moveRedRight(Node h){ // Assuming that h is red and both h.right and h.right.left// are black, make h.right or one of its children red.flipColors(h)if (isRed(h.left.left))h = rotateRight(h);return h;}public void deleteMax(){if (!isRed(root.left) && !isRed(root.right))root.color = RED;root = deleteMax(root);if (HsEmptyO) root.color = BLACK;}private Node deleteMax(Node h){if (isRed(h.left))h = rotateRight(h);if (h.right == null)return null;if (!isRed(h.right) && !isRed(h.right.left))h = moveRedRight(h);h.right = deleteMax(h.right);return balance(h);}