Test Flashcards
(22 cards)
What is the purpose of rotations in an AVL tree?
To maintain height balance after inserting an item.
What does a rotation in a BST maintain?
The BST ordering property.
What is a simple right rotation?
A local rearrangement that balances an unbalanced AVL tree.
In an AVL tree, what does a balance factor of 2 indicate?
The tree is unbalanced and needs a rotation.
Which node becomes the new root after a right rotation at node 86?
Node 75.
What happens to node 86 after a right rotation at node 86?
It becomes the right child of node 75.
In a right rotation, what does B’s former right child C become?
D’s left child.
What is the initial state of an AVL tree that requires a left rotation?
An unbalanced tree with a balance factor of -2.
What does the AVLTreeUpdateHeight algorithm do?
Updates a node’s height value based on its child subtree heights.
What is the precondition for the AVLTreeGetBalance function?
The node argument must be non-null.
True or False: AVLTreeGetBalance() has a precondition that the node’s children are both non-null.
False.
What does the AVLTreeSetChild algorithm do?
Sets a node as the parent’s left or right child and updates the child’s parent pointer.
What is a right rotation algorithm defined on?
A subtree root (node D) that must have a left child (node B).
What is the role of AVLTreeRotateRight function?
Performs a right rotation on a specified node in an AVL tree.
What is the result of a right rotation at node D?
Node B becomes the new root of the subtree.
What should be done if an AVL tree node has a balance factor of 2 or -2?
Rebalance the node via rotations.
True or False: AVLTreeRebalance rebalances all ancestors from the node up to the root.
True.
What is the effect of AVLTreeRebalance if a node’s balance factor is 1, 0, or -1?
It takes no action.
What does the AVLTreeRebalance algorithm do if the balance factor is -2?
It may perform a double rotation case and then a left rotation.
What is the outcome of a left rotation at a node?
It is the symmetrical operation to a right rotation.
Fill in the blank: In a right rotation, the left child of node D becomes the new ______.
root.
What happens to the balance factors of all nodes after a successful rotation?
They are updated to reflect the new structure.
