Chapter 45 AVL Trees and Splay Trees
1. AVL trees are well-balanced. In an AVL tree, the difference
between the heights of two subtrees for every node is 0 or 1.
The balance factor of a node is the height of its right subtree
minus the height of its left subtree. A node is said to be
balanced if its balance factor is -1, 0, or 1. A node is said to
be left-heavy if its balance factor is -1. A node is said to be
right-heavy if its balance factor is +1.
2. If a node is not balanced after an insertion or deletion operation, you need to
rebalance it. The process of rebalancing a node is called a rotation. There are four
possible rotations: LL, LR, RR, and RL.
An LL imbalance occurs at a node A such that A has a balance
factor -2 and a left child B with a balance factor -1 or 0.
This type of imbalance can be fixed by performing a single
right rotation at A.
3. In the BinaryTree class, the createNewNode() method creates a TreeNode object.
This method is defined protected in BinaryTree. It is overridden in the AVLTree
class to create an AVLTreeNode.
4. updateHeight(AVLTreeNode<E>) is invoked to update the height of a node. It is
invoked to rebalance the tree. balanceFactor is invoked to check the balance factor of
a node. It is invoked when a path is rebalanced. balancePath is invoked along the path
where a new node is inserted or a node is deleted.
5. AVLTreeNode inherits from TreeNode. The height is a new data field defined in
AVLTreeNode. The data fields in TreeNode are left and right, pointing to the left and
right subtree.
6. No.
7.
评论1