التوازن (مفهوم فقط)

Written Explanation

The same values, two shapes

Insert 1, 2, 3, 4, 5 into an empty BST, in that order. Each new value is larger than everything before it, so it always goes to the right of the last node:

1
 \
  2
   \
    3
     \
      4
       \
        5

This is a chain, sometimes called a degenerate tree. It still obeys the BST rule, and in-order traversal still gives 1 to 5. But it has height 4: five nodes, one per level. Now insert the same values in the order 3, 2, 4, 1, 5:

      3
     / \
    2   4
   /     \
  1       5

Height 2. Same values, same rule, a very different shape. The number of steps to find 5 is 5 in the chain and 3 in the bushy tree.

Why the chain is slow

Search and insert move one level down per step, so their cost is bounded by the height. For a tree of n nodes:

A chain is no better than scanning a linked list. Worse, building a chain of n values costs about n(n-1)/2 comparisons in total, because the k-th insert walks past all k-1 nodes already there. The OpenDSA textbook makes the same point: sorted insertion gives height n - 1 and a total cost that grows with the square of n.

The reverse order (5, 4, 3, 2, 1) gives a chain going left. Any strictly increasing or decreasing sequence is a worst case, and nearly sorted input is almost as bad.

Measuring it

We insert 1,000 values twice, once in sorted order and once shuffled with a fixed seed (new Random(42)), and compare the height and the number of nodes visited when searching for 1000:

n=1000 sorted   : height 999, steps to find 1000: 1000
n=1000 shuffled : height 26, steps to find 1000: 8

(Compiled and run with JDK 21. The shuffled numbers depend on the seed and the exact shuffle, so another run with another seed would show somewhat different numbers.) The sorted tree needs a thousand steps. The shuffled tree is not perfect either: a perfectly balanced tree of 1,000 nodes would have height 9, and ours has 26. But it is far from 999. A plain BST works well on data that arrives in random order and badly on data that arrives in order. You usually do not control arrival order, so a structure that does not depend on it is valuable.

The cure: keep the tree balanced

A balanced tree keeps its height close to log2 n whatever the insertion order. Self-balancing trees do this automatically. After an insert or a delete, the tree checks whether some part has become too tall on one side, and if so repairs it with one or more rotations.

A rotation is a small local rearrangement. Take the chain 1, 2, 3 (root 1, right child 2, whose right child is 3). A left rotation at the root makes 2 the new root, with 1 on its left and 3 on its right:

1                2
 \              / \
  2     ->     1   3
   \
    3

Height drops from 2 to 1. And the rotation keeps the BST rule: the in-order output is still 1, 2, 3. A rotation changes the shape only, never the order, so searches stay correct. The code is four lines:

static Node rotateLeft(Node x) {
    Node y = x.right;     // y becomes the new root of this subtree
    x.right = y.left;     // y's old left subtree moves under x
    y.left = x;
    return y;             // the caller stores y where x used to be
}

A self-balancing tree decides when to rotate by following a rule. Two famous families:

• AVL trees keep the heights of the two subtrees of every node within one of each other.
• Red-black trees color nodes red or black and follow color rules that keep the longest path at most about twice the shortest.

Both guarantee a height of order log n, so search, insert, and delete are O(log n) in the worst case. The price is a little extra work per insert and more code. You do not need the exact rules, only the idea: the tree repairs itself so that no input order can make it tall.

What Java gives you

The JDK already contains this. The Oracle documentation says TreeMap is a red-black tree implementation of NavigableMap, with guaranteed log(n) time for containsKey, get, put, and remove, and entries kept sorted by key. TreeSet is the set version, backed by a TreeMap. In practice you write new TreeMap<>(), insert in any order, and never think about rotations. That is why this lesson is concept-only: your own BST from Lesson 2 teaches how the idea works, while TreeMap is what you use in an application.