Ch 7: Balanced Trees II Flashcards
what is an AVL tree?
a BST with a height balance property and specific operations to rebalance the tree when a node is inserted or removed
when is a tree height-balanced?
for any node, the height of the node’s left and right subtrees differ by only 0 or 1
what is a balance factor?
left subtree minus the right subtree height (which is 0,1, or -1 in an AVL tree)
what is the average AVL height?
O(logn)
does an AVL ensure minimum height?
no but the height is no more than 1.5 the minimum of a binary tree height
what is runtime complexity for determining the balance factor and why?
O(1) because each node contains its height
what does a balance factor of 2 or -2 indicate?
rotation
what are the 4 imbalance cases of insertion?
- left-left case
- left-right case
- right-right case
- right-left case
what are the 4 ways to rebalance an imbalance case of insertion?
- left-left: 2,1 case
2: left-right: 2,-1 case - right-right: -2,-1 case
- right-left, -2, 1 case
explain the 4 cases for rebalancing.
- 2,1: right rotation on root
- 2,-1: left rotation on internal node, then right rotation on root
- -2,-1: left rotation on root
4: -2, 1: right rotation on internal node, then left rotation on root
what is the insertion algorithm?
BST insertion then all ancestors from parent to root are rebalanced, if any node has balance factor of 2 then rotation occurs
do all nodes have to be rebalanced after insertion? if no which nodes?
no, only nodes from parents up to root may need to be updated
what is the run time of insertion?
O(logn)
what is the run time of rotations
O(1)
what is the removal algorithm?
BST removal, all ancestors from parent node to root are rebalanced, if any node has a balance factor of 2 then rotation occurs
