Fork me on GitHub

数据结构---查找树

发表于

二叉查找树

二叉树是一个空链接，或者是一个有左右两个链接的节点，每个链接都指向一颗子二叉树

二叉查找树(BST)是一颗二叉树，并且每个节点的值都大于等于其左子树中的所有节点的值，小于等于右子树的所有节点的值

二叉查找树有一个重要的性质就是它的中序遍历结果递增排序

二叉查找树的数据结构

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
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;
        return x.N;
    }
}

get()

  1. 如果树是空的，则查找未命中
  2. 如果被查找的键和根节点的键相等，查找命中
  3. 否则递归地在子树中查找：如果被查找的键较小就在左子树中查找，较大就在右子树中查找
1
2
3
4
5
6
7
8
9
10
public Value get(Key key) {
    return get(root, key);
}
private Value get(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x.val;
    else if (cmp < 0) return get(x.left, key);
    else return get(x.right, key);
}

put()

当插入的键不存在于树中，需要创建一个新节点，并且更新上层节点的链接使得该节点正确链接到树中

1
2
3
4
5
6
7
8
9
10
11
12
public void put(Key key, Value val) {
    root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val, 1);
    int cmp = key.compareTo(x.key);
    if (cmp == 0) x.val = val;
    else if (cmp < 0) x.left = put(x.left, key, val);
    else x.right = put(x.right, key, val);
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

分析

最好情况(完全二叉树):每条空链接和根节点的距离都是logN
最坏情况（单边）:树的高度为N

floor()

floor(key):小于等于key的最大值

  1. 如果键小于根节点的键，那么floor(key)一定在左子树中
  2. 如果键大于根节点的键，那么先判断右子树中是否存在floor(key)
  3. 存在就找到，不存在就判断根节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null) return null;
    return x.key;
}
private Node floor(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    if (cmp < 0) return floor(x.left, key);
    Node t = floor(x.right, key);
    if (t != null) {
        return t;
    } else {
        return x;
    }
}

rank()

  1. 如果键和根节点的值相等，返回左子树的节点数
  2. 如果小于，递归计算在左子树中的排名
  3. 如果大于，递归计算在右子树总的排名，并加上左子树的节点数和根节点
1
2
3
4
5
6
7
8
9
10
public int rank(Key key) {
    return rank(key, root);
}
private int rank(Key key, Node x) {
    if (x == null) return 0;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return size(x.left);
    else if (cmp < 0) return rank(key, x.left);
    else return 1 + size(x.left) + rank(key, x.right);
}

min()

1
2
3
4
5
private Node min(Node x) {
    if (x == null) return null;
    if (x.left == null) return x;
    return min(x.left);
}

deleteMin()

1
2
3
4
5
6
7
8
9
public void deleteMin() {
    root = deleteMin(root);
}
public Node deleteMin(Node x) {
    if (x.left == null) return x.right;
    x.left = deleteMin(x.left);
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

delete()

  1. 如果待删除的节点只有一个子树，那么只需要让指向待删除节点的链接指向唯一的子树即可
  2. 否则，让右子树的最小节点替换该节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void delete(Key key) {
    root = delete(root, key);
}
private Node delete(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0) x.left = delete(x.left, key);
    else if (cmp > 0) x.right = delete(x.right, key);
    else {
        if (x.right == null) return x.left;
        if (x.left == null) return x.right;
        Node t = x;
        x = min(t.right);
        x.right = deleteMin(t.right);
        x.left = t.left;
    }
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

keys()

利用二叉查找树中序遍历的结果为递增的特点

1
2
3
4
5
6
7
8
9
10
11
12
13
public Iterable<Key> keys(Key lo, Key hi) {
    Queue<Key> queue = new LinkedList<>();
    keys(root, queue, lo, hi);
    return queue;
}
private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
    if (x == null) return;
    int cmpLo = lo.compareTo(x.key);
    int cmpHi = hi.compareTo(x.key);
    if (cmpLo < 0) keys(x.left, queue, lo, hi);
    if (cmpLo <= 0 && cmpHi >= 0) queue.add(x.key);
    if (cmpHi > 0) keys(x.right, queue, lo, hi);
}

2-3查找树

2-3查找树中引入了2-节点和3-节点，目的是为了让树平衡，一颗完美平衡的2-3查找树的所有空链接到根节点的距离应该是相同的

插入操作

2-3查找树的插入操作与二叉查找树的插入操作有很大的区别，二叉查找树插入操作是先进行一次未命中的查找，然后再将节点插入对应的空连接上。
2-3查找树插入操作是将新节点插入到叶子节点上

  1. 插入到2-节点上，那么直接将新节点和原来节点组成3-节点
  2. 如果是插入到3-节点上，就会产生一个临时的4-节点 ，需要将4-节点分裂成3个2-节点，并将中间的2-节点移到上层节点中。如果上移操作产生临时4-节点则一直分裂上移，知道不存在临时4-节点

2-3查找树的查找和插入操作复杂度和插入顺序无关，在最坏情况下查找和插入操作访问的节点必然不超过logN个。

红黑二叉查找树

红黑树中使用红链接来实现3-节点。指向一个节点的链接颜色如果是红色，那么这个节点和上层节点表示的是一个3-节点，而黑色则是普通连接

  1. 红链接都是左链接
  2. 完美黑色平衡，即任意空链接到根节点的路径上的黑链接数量相同

数据结构

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
public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private Node root;
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        Key key;
        Value val;
        Node left, right;
        int N;
        boolean color;

        Node(Key key, Value val, int n, boolean color) {
            this.key = key;
            this.val = val;
            N = n;
            this.color = color;
        }
    }

    private boolean isRed(Node x) {
        if (x == null) return false;
        return x.color == RED;
    }
}

左旋转

上面提到红链接都是左链接，如果出现红链接为有链接的时候，就要进行左旋操作

1
2
3
4
5
6
7
8
9
10
public Node rotateLeft(Node h) {
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1 + size(h.left) + size(h.right);
    return x;
}

右旋转

进行右旋转是为了转换两个连续的左红连接

1
2
3
4
5
6
7
8
9
public Node rotateRight(Node h) {
    Node x = h.left;
    h.left = x.right;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1 + size(h.left) + size(h.right);
    return x;
}

颜色转化

一个4-节点在红黑树中表现为一个节点的左右节点都是红色的，分裂4-节点除了需要将子节点的颜色由红变黑外，同时需要将父节点的颜色由黑变红，从2-3树的角度看就是将中间节点移到上层节点。

1
2
3
4
5
void flipColors(Node h){
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}

插入操作

先将一个节点按照二叉查找树的方法插入到正确位置，然后再进行如下的颜色转换操作

  1. 如果右子节点是红色的而左子节点是黑色的，进行左旋转
  2. 如果左子节点是红色的，左子节点的左子节点也是红色的，进行右旋转
  3. 如果左右子节点都是红色的，进行颜色转化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void put(Key key, Value val) {
    root = put(root, key, val);
    root.color = BLACK;
}

private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val, 1, RED);
    int cmp = key.compareTo(x.key);
    if (cmp == 0) x.val = val;
    else if (cmp < 0) x.left = put(x.left, key, val);
    else x.right = put(x.right, key, val);

    if (isRed(x.right) && !isRed(x.left)) x = rotateLeft(x);
    if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
    if (isRed(x.left) && isRed(x.right)) flipColors(x);

    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

根节点一定为黑色，因为根节点没有上层节点，也就没有上层节点的左链接指向根节点。flipColors() 有可能会使得根节点的颜色变为红色，每当根节点由红色变成黑色时树的黑链接高度加 1

分析

一颗大小为 N 的红黑树的高度不会超过 2logN。最坏的情况下是它所对应的 2-3 树，构成最左边的路径节点全部都是 3- 节点而其余都是 2- 节点。

红黑树大多数的操作所需要的时间都是对数级别的。