AVL Trees Flashcards
In terms of balance factor, when would you do a double rotation?
When parent and child are heavy in opposite directions, thus have opposite signed balance factors.
A right left rotation is required when the child is left heavy (bf < 0) and parent is right heavy (bf > 0)
A left right rotation is required when the child is right heavy (bf > 0) and the parent is left heavy (bf < 0)
Left-right imbalance – N is left-heavy and N’s left child C is right-heavy Right-left imbalance – N is right-heavy and N’s right child C is left-heavy
A node that is left heavy has a positive or negative balance factor?
negative. balanceFactor(N) < 0
Rotations are always done with respect to x nodes
3
When we say that a node is left heavy, what does that tell us about the height of the subtrees rooted at that node
Balance factor is less than 0 and the left subtree of the node has greater height than the right
A node that is right heavy has a positive or negative balance factor?
positive. balanceFactor(N) > 0
A right rotation moves nodes in a _______ direction, with the center moving ________ and nodes to its left moving ________.
clockwise, downwards, upwards
The shape of a non-balancing BST depends to a great degree on the…
order of which values/keys are added into the tree
What is the balance factor of a BST node and how do you calculate it?
The balance factor of a BST node tells us how balanced the subtree at that node is.
The balance factor of a subtree rooted at some node N is calculated by:
balanceFactor(N) = height(N.right) - height(N.left)
Time complexity of AVL insert and remove operations?
O(logn) This is because every time an insertion and removal occurs, the tree is rebalanced to keep the tree height within constant factor of logn. The maximum number of times the O(1) rebalance function can be called is h, the height of the tree when upwards traversal starts at the very bottom of the tree.
A _______ is a simple operation that restructures an isolated region of the tree by performing a limited number of pointer updates that result in one node moving ______ in the tree and another node moving ______
rotation, upwards, downwards
A tree is balanced when all nodes have _____ approximately _____ or less
when we talk about balance in the context of BSTs, we’re referring to trees in which all nodes have depth approximately log n or less.
Whats the purpose of a double rotation?
A double rotation aligns imbalances on the same side to create a left-left imbalance or a right-right imbalance.
When would you do a double rotation as opposed to just one?
When you insert a node to the left and then right, or when you insert a node to the right and then left. LR-Insert causes LR-imbalance
When is a BST considered height balanced?
A BST is height balanced if, at every node in the tree, the subtree heights of the node’s left and right subtrees differ by at most 1.
Time complexity of the rebalance function alone?
O(1) because at most there will be 2 rotations per node.
