cs126 AVL tree

What is an AVL tree?

• Adel’son-Vel’skii and Landis tree

• A binary search tree with a balance property

• For each node, the height of the left and right subtrees differ by at most 1

What is the height of an AVL tree with n nodes?

O(log n)

Name the (2) imbalances that can be created by an insertion to AVL tree.

1. Left-left / Right-right (requires single rotation)

2. Left-right / Right-left (requires double rotation)

Name the (4) cases of insertion to an AVL tree that require rotation(s).

1. Insertion into left subtree of left child

2. Insertion into right subtree of right child

3. Insertion into right subtree of left child

4. Insertion into left subtree of right child

Describe how a left rotation is performed about the node n.

• Let m be the child node of n

• The right pointer of n is set to left child of m 

• The left pointer of m is set to n

Describe how a right rotation is performed about the node n.

• Let m be the child node of n

• The left pointer of n is set to right child of m 

• The right pointer of m is set to n

What is rebalancing?

The action of performing a single or double rotation on an AVL tree after an insertion / deletion.

What is trinode restructuring?

Restructuring that involves a node, its parent, and its grandparent.

Describe how a node is deleted from an AVL tree.

1. Delete the node (as you would with a BST)

2. Trace the path from the new leaf to the root

   1. For each node n encountered, check if the heights of the left(n) and right(n) differ by 1 or less

   2. If yes, proceed to parent(n)

   3. If no, perform an appropriate rotation at n

What is the worst-case time cost of (1) trinode restructuring of an AVL tree node?

O(1)

What is the worst-case number of trinode restructurings required to restore height-balance after a deletion?

O(logn)

What is the space cost of an AVL tree?

O(n)

What is the time cost of searching / inserting /deleting for an AVL tree?

O(logn)