CSC 230 (5) - Balanced Binary Trees

What is a Balanced Binary Tree?

A tree that maintains height balance to ensure efficient operations.

Why is a balanced tree always a valid BST?

Because it inherently maintains the ordering property of a BST (left < parent < right).

Why are balanced trees important?

They keep tree height small, ensuring search, insert, and delete operations remain efficient.

How is tree height calculated?

The number of edges (or levels) on the longest path from the root to a leaf.

What is a node’s balance factor?

Height(left subtree) − Height(right subtree).

What are the only valid balance factor values in an AVL Tree?

-1, 0, or 1

What is the AVL Tree rule for balance?

The heights of any node’s left and right subtrees differ by at most 1.

When is an AVL Tree considered unbalanced?

When a node’s balance factor is greater than 1 or less than −1.

What is a Red-Black Tree?

A self-balancing BST where each node is colored red or black and follows specific balancing rules.

Red-Black Tree Rule 1 (Red/Black Property)?

Every node is colored either red or black.

Red-Black Tree Rule 2 (Root Property)?

The root node is always black.

Red-Black Tree Rule 3 (Leaf Property)?

Every null leaf (NIL) is black.

Red-Black Tree Rule 4 (Red Property)?

If a node is red, then both of its children must be black.

Red-Black Tree Rule 5 (Depth Property)?

For each node, every path from that node to a descendant leaf contains the same number of black nodes.

Which STL containers are implemented using Red-Black Trees?

std::map and std::set.

In std::map and std::set, what are the tree elements?

The keys.

What is a tree rotation?

A local restructuring operation used to restore balance in a balanced BST.

What is a left rotation?

A rotation that moves the right child up and the pivot node down to the left.

What is a right rotation?

A rotation that moves the left child up and the pivot node down to the right.

What is the Left-Left (LL) case in AVL trees?

Left subtree of the left child is heavy → perform a right rotation on the pivot.

What is the Right-Right (RR) case in AVL trees?

Right subtree of the right child is heavy → perform a left rotation on the pivot.

What is the Left-Right (LR) case in AVL trees?

Left rotate the pivot’s left child, then right rotate the pivot.

What is the Right-Left (RL) case in AVL trees?

Right rotate the pivot’s right child, then left rotate the pivot.

What are the steps of the AVL insertion algorithm?

1. Insert the node using the standard BST insertion algorithm

2. Traverse back up to the root and rebalance using rotations

What are the steps of the AVL removal algorithm?

1. Remove the node using the standard BST removal algorithm

2. Rebalance ancestors from the parent of the removed node up to the root

How is a node rebalanced during AVL removal?

Compute the balance factor and perform rotations if the factor is greater than 1 or less than −1.

Key difference between AVL and Red-Black Trees?

AVL trees enforce strict balance (−1, 0, 1), while Red-Black trees enforce balance through coloring rules.

Now, do problem set 09 and quiz 10 and quiz 11