4.4. Quiz

This section provides exercises for better understanding in balanced binary search trees.

Interpretation

• Explain how the remove() method works in the AbstractBalancedBinarySearchTree class:

  • Explain what gets assigned to lowest in L71.

  • Explain how the balance() methods in AVLTree and RedBlackTree keep the trees balanced (or fails to keep them balanced) after a removal.

• Write a report including your explanation and save it as quiz4.pdf.

Implementation

• Create the BalacnedBinarySearchTreeQuiz class under the tree.balanced package that inherits theAbstractBalancedBinarySearchTree class.

• Override the balance() method that first checks the following conditions:

  • node is the only child &

  • node’s parent is the right child of node's grand parent &

  • node’s uncle has only one child.

• If all of the above conditions are satisfied, balance() makes multiple rotations such that the left subtree is always full before any node gets added to the right subtree.

• For the example below, after adding the keys (in red) to the trees 1, 2, 3, and 4, they all need to be transformed into the tree 5 by the balance() method.

• The transform must be performed only by rotations; other setter methods such as setLeftChild() or setRightChild() are not allowed in this assignment.