Chapter 29 - AVL Trees Flashcards
If a tree is perfectly balanced – i.e., a complete binary tree – its height is log n. Can we maintain a perfectly balanced tree?
Yes, but doing so will be costly. The compromise is to maintain a well-balanced tree – that is, the height of every node’s two subtree are about the same.
What is an AVL tree?
An AVL tree is a well balanced binary search tree.
For AVL trees, what does “AVL” stand for?
AVL trees were invented in 1962 by two Russion computer scientists, Adelson-Velsky and Landis – hence the name AVL.
What is the difference between the heights of every node’s subtrees in an AVL tree?
The difference in height is either 0 or 1. Therefore the maximum height of an AVL tree is O(logn)
What is the balance factor of a node in an AVL tree?
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 considered left-heavy if its balance factor is -1, and right-heavy if its balance factor is +1.
What does it mean to rebalance an AVL tree?
After inserting or deleting an element from an AVL tree, if the tree becomes unbalanced, perform a rotation operation to rebalance the tree.
Describe the LL rotation.
An LL imbalance occurs at a node A, such that A has a balance factor of -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.
Describe the RR rotation.
An RR imbalance occurs at a node A, such that A has a balance factor of +2 and a right child B with a balance factor of +1 or 0. This type of imbalance can be fixed by performing a single left rotation at A.
Describe the LR rotation.
An LR imbalance occurs at a node A, such that A has a balance factor of -2 and a left child B with a balance factor of +1. Assume B’s right child is C. This type of imbalance can be fixed by performing a double rotation at A (first a single left rotation at B and then a single right rotation at A).
Describe the RL rotation.
An RL imbalance occurs at a node A, such that A has a balance factor of +2 and a right child B with a balance factor of -1. Assume B’s left child is C. This type of imbalance can be fixed by performing a double rotation at A (first a single right rotation at B and then a single left rotation at A).
“In order to balance the tree, you need to know each node’s height.” Where can the height of each node be stored?
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.
Whens is the updateHeight method invoked? When is the balancFactor method invoked? When is the balancePath method invoked?
updateHeight(AVLTreeNode) 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.
In the insert and delete methods, once you have performed a rotation to balance a node in the tree, is it possible that there are still unbalanced nodes?
No
Can you traverse the elements in a AVL tree using a do-while loop?
Sure you can, by using the pointers of the nodes.
What is the time complexity of the search method in AVLTree?
O(log n)
