11 - AVL Trees

When performing trinode restructuring in an AVL tree, which node should be labeled "Z"?

• the first node at which the height-balance property is violated
• the first node that would be visited in an inorder traversal
• the child of the node where the height-balance property is violated
• the traller grandchild of the node at which the height-balance property is violated

The goal of trinode restructuring is to ___.

• balance the subtree
• move "a" to be the root
• move "c" to be the root
• move "y" to be the root

In an AVL tree, for every internal node p, the heights of the children of the node p ______.

• differ by at most 1
• differ by at most 2
• must be equal
• must be different

Is the following tree an AVL tree?

• no

• yes

Is the following tree an AVL tree?

• yes

• no

Assume we deleted the left child of 10 (now replaced with a sentinel node in the tree below). What node should be labeled "Z"?

• 10

• 12

• 15

• 20

Assume we deleted the left child of 10 (now replaced with a sentinel node in the tree below). What node should be labeled "Y"?

• 15

• 10

• 12

• 20

Assume we deleted the left child of 10 (now replaced with a sentinel node in the tree below). What node should be labeled "X"?

• 20

• 10

• 12

• sentinel

What is the worst-case height of an AVL tree?

• O(log n)
• O(n)
• O(n logn)
• O(1)