=============================================================================
CSC 263 Tutorial 4 Winter 2019
=============================================================================
In this tutorial, will learn about AVL-Delete using various examples.
1. Consider the following AVL tree, what happens if we insert a node 5 into the
tree? Which node is the lowest ancestor to become unbalanced? What type of
rotations need to be performed to rebalance the tree? Perform the AVL-INSERT
carefully step by step.
3
/ \
2 7
/ / \
1 4 8
\
6
2. Consider the following AVL-tree, what happens if we delete the node 8 from
the tree? What type of rotations are needed to rebalance the tree? What's the
height of the tree before deletion? What's the height of the tree after
deletion?
6
/ \
4 7
/ \ \
2 5 8
/ \
1 3
3. Consider the following AVL-tree, what happens if we delete the node 2 from
the tree? What type of rotations are needed to rebalance the tree? What's the
height of the tree before deletion? What's the height of the tree after
deletion?
3
/ \
2 7
/ / \
1 5 8
/ \
4 6
4. Come up with an example AVL-tree for which deleting a node from the tree
causes two levels of double-rotations.
5. Draw a picture of the structure of the AVL tree for which deleting a node
would cause O(log n) rotations, where n is the number of nodes in the tree.
6. Suppose in the AVL-INSERT operation, the tree looks like the following right
after inserting the new node and before rebalancing.
1
\
2
\
3
\
4
Since node 2 is the lowest ancestor that is unbalanced, we do a left
rotation around 2, which gives us the following tree
1
\
3
/ \
2 4
This tree is still not AVL, which contradicts with what we said in the lecture
that AVL-INSERT requires only one level of rotation. What went wrong?