Why do we need balanced trees? Because a "Skewed" Binary Search Tree is just a slow Linked List ($O(n)$). Self-balancing trees use Rotations to stay bushy and short, ensuring $O(\log n)$ performance.

Think of a Mobile (Dangling Art):

1. If you hang too many heavy pieces on one side, the whole thing tilts.
2. To keep it Level, you have to move the strings around.
3. In a tree, "moving the strings" is called a Rotation.
4. Every time you add a node, the tree checks if it's "heavy" on one side. If it is, it performs a quick dance (Rotation) to stay perfectly balanced.

---

1. AVL Trees (Strict Balance)

• Rule: For every node, the height difference between left and right subtrees must be $\le 1$.
• When to use: If you are doing Search-Heavy work. It is more strictly balanced than Red-Black trees.

2. Red-Black Trees (Casual Balance)

• Rule: Uses "Colors" (Red/Black) and 5 specific rules about how colors can be arranged.
• When to use: If you are doing frequent Inserts and Deletes. It's easier to re-balance because it's less strict than AVL.
• Fun Fact: Java's TreeMap and C++'s std::map are usually implemented as Red-Black Trees.

---

You are rarely asked to code a full AVL tree (it's too long), but you MUST understand the Rotation logic.

javascript Standard
/**
 * Left Rotation Concept
 */
function rotateLeft(x) {
  let y = x.right;
  let T2 = y.left;

  // Perform rotation
  y.left = x;
  x.right = T2;

  // Return new root
  return y;
}

---

Theory Questions

• Why are AVL trees better than standard BSTs?
• Compare AVL vs Red-Black Trees. (Answer: AVL is more balanced/faster searches, RB is faster for updates).
• What are the four types of rotation in an AVL tree? (Answer: Left-Left, Left-Right, Right-Right, Right-Left).

Top Tip

For coding interviews, you don't need to memorize the Red-Black tree rules. Just know that they are self-balancing and provide $O(\log n)$ worst-case performance. If you need a sorted map in an interview, just assume the built-in one is a balanced tree. 🪚