一棵二叉查找树 （BST）是一棵二叉树，其中每个结点都含有一个Comparable 的键（以及相关联的值）且每个结点的键都大于其左子树中 的任意结点的键而小于右子树的任意结点的键

3.2.1　基本实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class BST<Key extends Comparable<Key>, Value>
{
    private Node root; // 二叉查找树的根结点
    private class Node
    {
        private Key key; // 键
        private Value val; // 值
        private Node left, right; // 指向子树的链接
        private int N; // 以该结点为根的子树中的结点总数
        public Node(Key key, Value val, int N) { this.key = key; this.val = val; this.N = N; }
    }
    public int size() { return size(root); }
    private int size(Node x)
    {
        if (x == null) return 0;
        else return x.N;
    }
    public Value get(Key key) { return get(root, key); }
    private Value get(Node x, Key key)
    { // 在以x为根结点的子树中查找并返回key所对应的值；
        // 如果找不到则返回null
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) return get(x.left, key);
        else if (cmp > 0) return get(x.right, key);
        else return x.val;
    }
    public void put(Key key, Value val)
    { // 查找key，找到则更新它的值，否则为它创建一个新的结点
        root = put(root, key, val);
    }
    private Node put(Node x, Key key, Value val)
    {
        // 如果key存在于以x为根结点的子树中则更新它的值；
        // 否则将以key和val为键值对的新结点插入到该子树中
        if (x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.left = put(x.left, key, val);
        else if (cmp > 0) x.right = put(x.right, key, val);
        else x.val = val;
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
}

3.3　平衡查找树

3.3.1　2-3 查找树

  • 2-结点，含有一个键（及其对应的值）和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
  • 3- 结点，含有两个键（及其对应的值）和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的 2-3 树中的键都大于该结点。

3.3.1.1　查找

3.3.1.2　向 2-结点中插入新键

3.3.1.3　向一棵只含有一个3-结点的树中插入新键

3.3.1.4　向一个父结点为2-结点的3-结点中插入新键

3.3.1.5　向一个父结点为3-结点的3-结点中插入新键

3.3.1.6　分解根结点

3.3.1.7　局部变换

3.3.1.8　全局性质

3.3.2　红黑二叉查找树

2-3树数据结构，用标准的二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示 2-3树

3.3.2.1　替换3-结点

  • 红链接：将两个2-结点连接起来构成一个3-结点
  • 黑链接：2-3树中的普通链接

3.3.2.2　一种等价的定义

  • 红链接均为左链接
  • 没有任何一个结点同时和两条红链接相连
  • 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同

3.3.2.3　一一对应

3.3.2.4　颜色表示

3.3.2.5　旋转

3.3.2.6　在旋转后重置父结点的链接

3.3.2.7　向单个2-结点中插入新键

3.3.2.8　向树底部的2-结点插入新键

3.3.2.9　向一棵双键树（即一个3-结点）中插入新键

3.3.2.10　颜色转换

3.3.2.11　根结点总是黑色

3.3.2.12　向树底部的3-结点插入新键

3.3.2.13　将红链接在树中向上传递

3.3.3　实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class RedBlackBST<Key extends Comparable<Key>, Value>
{
    private Node root;
    private class Node // 含有color变量的Node对象（请见3.3.2.4节）
    private boolean isRed(Node h)
    private Node rotateLeft(Node h)
    private Node rotateRight(Node h)
    private void flipColors(Node h)
    private int size()
    public void put(Key key, Value val)
    { // 查找key，找到则更新其值，否则为它新建一个结点
        root = put(root, key, val);
        root.color = BLACK;
    }
    private Node put(Node h, Key key, Value val)
    {
        if (h == null) // 标准的插入操作，和父结点用红链接相连
        return new Node(key, val, 1, 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;
        if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);
        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }
}