平衡查找树

发表于   |   分类于

2-3 树

Allow 1 or 2 keys per node.

  • 2-node: one key, two children.
  • 3-node: two keys, three children.

Symmetric order. Inorder traversal yields keys in ascending order.

Perfect balance. Every path from root to null link has same length.

Global properties in a 2-3 tree

Invariants. Maintains symmetric order and perfect balance.

2-3 树性能

红黑树

使用红黑树代表2-3树

An equivalent definition

A BST such that:

  • No node has two red links connected to it.
  • Every path from root to null link has the same number of black links(perfect black balance).
  • Red links lean left.

红黑树和2-3树的一一对应关系

Search implementation for red-black BSTs

Observation. Search is the same as for elementary BST (ignore color).

1
2
3
4
5
6
7
8
9
10
11
12
public Val get(Key key)
{
    Node x = root;
    while (x != null)
    {
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x = x.left;
        else if (cmp > 0) x = x.right;
        else              return x.val;
    }
    return null;
}

Red-black BST representation

Each node is pointed to by precisely one link(from its parent) => can encode color of links in nodes.

1
2
3
4
5
6
7
8
9
10
private static final boolean RED = true;
private static final boolean BLACK = false;

private class Node
{
    Key key;
    Value val;
    Node left, right;
    boolean color; // color of parent link
}

Elementary red-black BST operations

Left rotation.

Orient a (temporarily) right-leaning red link to lean left.

1
2
3
4
5
6
7
8
9
10
private Node rotateLeft(Node h)
{
    assert isRed(h.right);
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    return x
}

Right rotation.

Orient a left-leaning red link to (temporarily) lean right.

1
2
3
4
5
6
7
8
9
10
private Node rotateRight(Node h)
{
    assert isRed(h.left);
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    return x;
}

Color flip.

Recolor to split a (temporary) 4-node.

1
2
3
4
5
6
7
8
9
private void flipColors(Node h)
{
    assert !isRed(h);
    assert isRed(h.left);
    assert isRed(h.right);
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}


向红黑树插入一个新节点

Warmup 1: Insert into a tree with exactly 1 node.

Case 1: Insert into a 2-node at the bottom.

  • Do standard BST insert; color new link red.
  • If new red link is right link, rotate left.

Warmup 2: Insert into a tree with exactly 2 node.

Case 2: Insert into a 3-node at the bottom.

  • Do standard BST insert; color new link red.
  • Rotate to balance the 4-node (if needed).
  • Flip colors to pass red link up one level.
  • Rotate to make lean left (if needed).
  • Repeat case 1 or case 2 up the tree (if needed).


Same code for all cases.

  • Right child red, left child black: rotate left.
  • Left child, left-left grandchild red: rotate right.
  • Both child red: flip colors.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private Node put(Node h, Key key, Value val)
{
    // insert at bottom (and color it red)
    if (h == null) return new Node(key, val, RED);
    
    int cmp = key.compareTo(h.key);
    if      (cmp < 0) h.left = put(h.left, key, val);
    else if (cmp > 0) h.right = put(h.right, key, val);
    else              h.val = val
    
    // lean left
    if (isRed(h.right) && !isRed(h.left))    h = rotateLeft(h);
    
    // balance 4-node
    if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
    
    // split 4-node
    if (isRed(h.left) && isRed(h.right))     flipColors(h)
    
    return h;
}

性能分析