Ch3nyang's blog | 算法笔记 (1) -搜索树

二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一种二叉树，其中每个节点都有一个值。对于每个节点 x，其左子树中的所有节点的值都小于 x 的值，其右子树中的所有节点的值都大于等于 x 的值。

树的节点和树的定义如下：

Java

public class BSTree<T extends Comparable<T>> {
    public class BSTreeNode<T extends Comparable<T>> {
        T val;
        BSTreeNode<T> left;
        BSTreeNode<T> right;
        BSTreeNode(T val) {
            this.val = val;
        }
    }

    private BSTreeNode<T> root;
}

查找时，从根节点开始，如果要查找的值小于当前节点的值，则继续在左子树中查找；如果要查找的值大于当前节点的值，则继续在右子树中查找；如果要查找的值等于当前节点的值，则找到了。

Java

private BSTreeNode<T> search(BSTreeNode<T> x, T val) {
    if (x == null || x.val == val) {
        return x;
    }

    if (val.compareTo(x.val) < 0) {
        return search(x.left, val);
    } else {
        return search(x.right, val);
    }
}

public BSTreeNode<T> search(T val) {
    return search(root, val);
}

按照元素从小到大的顺序遍历二叉搜索树，可以使用中序遍历。中序遍历的顺序是：先遍历左子树，然后访问根节点，最后遍历右子树。

Java

private void inorder(BSTreeNode<T> x, List<T> list) {
    if (x == null) {
        return;
    }

    inorder(x.left, list);
    list.add(x.val);
    inorder(x.right, list);
}

public List<T> inorder() {
    List<T> list = new ArrayList<T>();
    inorder(root, list);
    return list;
}

插入时，从根节点开始，如果要插入的值小于当前节点的值，则继续在左子树中插入；如果要插入的值大于等于当前节点的值，则继续在右子树中插入。

Java

private BSTreeNode<T> insert(BSTreeNode<T> x, T val) {
    if (x == null) {
        return new BSTreeNode<T>(val);
    }

    if (val.compareTo(x.val) < 0) {
        x.left = insert(x.left, val);
    } else {
        x.right = insert(x.right, val);
    }

    return x;
}

public void insert(T val) {
    root = insert(root, val);
}

删除时，有三种情况：

要删除的节点没有子节点，直接删除；
要删除的节点只有一个子节点，用子节点替换要删除的节点；
要删除的节点有两个子节点，用其右子树中的最小节点（后继节点）替换要删除的节点。

我们首先实现后继节点的查找：

Java

private BSTreeNode<T> successor(BSTreeNode<T> x) {
    x = x.right;
    while (x.left != null) {
        x = x.left;
    }
    return x;
}

然后实现删除操作：

Java

private BSTreeNode<T> delete(BSTreeNode<T> x, T val) {
    if (x == null) {
        return null;
    }

    if (val.compareTo(x.val) < 0) {
        x.left = delete(x.left, val);
    } else if (val.compareTo(x.val) > 0) {
        x.right = delete(x.right, val);
    } else {
        if (x.left == null) {
            // 没有左子树，用右子树或者 null 替换
            return x.right;
        } else if (x.right == null) {
            // 没有右子树，用左子树替换
            return x.left;
        } else {
            // 有两个子节点，用后继节点替换
            BSTreeNode<T> succ = successor(x);
            x.val = succ.val;
            x.right = delete(x.right, succ.val);
        }
    }

    return x;
}

public void delete(T val) {
    root = delete(root, val);
}

二叉搜索树的查找、插入和删除操作的时间复杂度都是 \(O(h)\)，其中 \(h\) 是树的高度。

平衡树

平衡树（Balanced Tree）是一种特殊的二叉搜索树，其中每个节点的左子树和右子树的高度差均不超过 \(1\)。

树的节点和树的定义如下：

Java

public class AVLTree<T extends Comparable<T>> {
    public class AVLTreeNode<T extends Comparable<T>> {
        T val;
        AVLTreeNode<T> left;
        AVLTreeNode<T> right;
        int height;
        AVLTreeNode(T val) {
            this.val = val;
            this.height = 1;
        }
    }

    private AVLTreeNode<T> root;
}

平衡树的失衡情况有四种：

左子树的左子树失衡（LL） 右旋

LL Rotation

Java

private AVLTreeNode<T> rightRotate(AVLTreeNode<T> x) {
    AVLTreeNode<T> y = x.left;
    AVLTreeNode<T> B = y.right;

    y.right = x;
    x.left = B;

    x.height = Math.max(height(x.left), height(x.right)) + 1;
    y.height = Math.max(height(y.left), height(y.right)) + 1;

    return y;
}

右子树的右子树失衡（RR） 左旋

RR Rotation

Java

private AVLTreeNode<T> leftRotate(AVLTreeNode<T> x) {
    AVLTreeNode<T> y = x.right;
    AVLTreeNode<T> B = y.left;

    y.left = x;
    x.right = B;

    x.height = Math.max(height(x.left), height(x.right)) + 1;
    y.height = Math.max(height(y.left), height(y.right)) + 1;

    return y;
}

左子树的右子树失衡（LR） 左旋后右旋

LR Rotation

Java

private AVLTreeNode<T> leftRightRotate(AVLTreeNode<T> x) {
    x.left = leftRotate(x.left);
    return rightRotate(x);
}

右子树的左子树失衡（RL） 右旋后左旋

RL Rotation

Java

private AVLTreeNode<T> rightLeftRotate(AVLTreeNode<T> x) {
    x.right = rightRotate(x.right);
    return leftRotate(x);
}

平衡树的一个重点就是求左右子树的高度差，即平衡因子（Balance Factor）。平衡因子等于左子树的高度减去右子树的高度。在插入和删除操作中，需要在递归返回时更新节点的高度，并在需要的时候进行旋转操作。

Java

private int height(AVLTreeNode<T> x) {
    return x == null ? 0 : x.height;
}

private int balanceFactor(AVLTreeNode<T> x) {
    return x == null ? 0 : height(x.left) - height(x.right);
}

平衡树的遍历、插入和删除操作与二叉搜索树类似，只是在插入和删除操作中需要维护节点的高度，并在需要的时候进行旋转操作。插入操作如下：

Java

private AVLTreeNode<T> insert(AVLTreeNode<T> x, T val) {
    if (x == null) {
        return new AVLTreeNode<T>(val);
    }

    if (val.compareTo(x.val) < 0) {
        x.left = insert(x.left, val);
    } else {
        x.right = insert(x.right, val);
    }

    x.height = Math.max(height(x.left), height(x.right)) + 1;

    int bf = balanceFactor(x);
    if (bf > 1 && val.compareTo(x.left.val) < 0) {
        return rightRotate(x);
    } else if (bf < -1 && val.compareTo(x.right.val) > 0) {
        return leftRotate(x);
    } else if (bf > 1 && val.compareTo(x.left.val) > 0) {
        return leftRightRotate(x);
    } else if (bf < -1 && val.compareTo(x.right.val) < 0) {
        return rightLeftRotate(x);
    }

    return x;
}

public void insert(T val) {
    root = insert(root, val);
}

删除操作如下：

Java

private AVLTreeNode<T> delete(AVLTreeNode<T> x, T val) {
    if (x == null) {
        return null;
    }

    if (val.compareTo(x.val) < 0) {
        x.left = delete(x.left, val);
    } else if (val.compareTo(x.val) > 0) {
        x.right = delete(x.right, val);
    } else {
        if (x.left == null) {
            return x.right;
        } else if (x.right == null) {
            return x.left;
        } else {
            AVLTreeNode<T> succ = successor(x);
            x.val = succ.val;
            x.right = delete(x.right, succ.val);
        }
    }

    x.height = Math.max(height(x.left), height(x.right)) + 1;

    int bf = balanceFactor(x);
    if (bf > 1 && balanceFactor(x.left) >= 0) {
        return rightRotate(x);
    } else if (bf < -1 && balanceFactor(x.right) <= 0) {
        return leftRotate(x);
    } else if (bf > 1 && balanceFactor(x.left) < 0) {
        return leftRightRotate(x);
    } else if (bf < -1 && balanceFactor(x.right) > 0) {
        return rightLeftRotate(x);
    }

    return x;
}

public void delete(T val) {
    root = delete(root, val);
}

平衡树的查找、插入和删除操作的时间复杂度都是 \(O\left(\log n\right)\)，其中 \(n\) 是树的节点数。

与二叉搜索树相比，平衡树的高度更低，因此在最坏情况下的查找、插入和删除操作的时间复杂度更低。

红黑树

红黑树（Red-Black Tree）是一种特殊的二叉查找树，其中每个节点都有一个颜色，红色或者黑色。它所有的叶子节点都是 NIL 节点。红黑树满足以下性质：

每个节点要么是红色，要么是黑色；
根节点是黑色；
每个叶子节点（NIL 节点）是黑色；
如果一个节点是红色，则它必须有两个黑色子节点；
从任意节点到其每个叶子节点的路径上，黑色节点的数量相同。

以上约束保证了红黑树从根节点到叶子节点的路径不会多于最短可能路径的两倍。

树的节点和树的定义如下：

Java

public class RBTree<T extends Comparable<T>> {
    public static final boolean RED = false;
    public static final boolean BLACK = true;

    public class RBTreeNode<T extends Comparable<T>> {
        T val;
        RBTreeNode<T> left;
        RBTreeNode<T> right;
        RBTreeNode<T> parent;
        boolean color;
        RBTreeNode(T val, boolean color) {
            this.val = val;
            this.color = color;
        }
    }

    private RBTreeNode<T> root;
}

在插入时，每个新插入的节点必须是红色（这样不会违背性质 5），然后通过旋转和重新染色使其满足性质 4。

我们首先实现左右旋转：

Java

private RBTreeNode<T> leftRotate(RBTreeNode<T> x) {
    RBTreeNode<T> y = x.right;
    x.right = y.left;
    y.left.parent = x;
    y.left = x;
    x.parent = y;
    return y;
}

private RBTreeNode<T> rightRotate(RBTreeNode<T> x) {
    RBTreeNode<T> y = x.left;
    x.left = y.right;
    y.right.parent = x;
    y.right = x;
    x.parent = y;
    return y;
}

具体来讲，红黑树的不平衡分以下几种情况：

如果当前节点是根节点，直接将其染黑

Case 0

Java

private RBTreeNode<T> case0(RBTreeNode<T> x) {
    x.color = BLACK;
    return x;
}

如果当前节点的父节点 P 是红色，叔叔节点 U 也是红色，将父节点 P 和叔叔节点 U 染黑，祖父节点 G 染红，然后将祖父节点 G 作为当前节点继续处理
Java
```
private RBTreeNode<T> case1(RBTreeNode<T> g) {
    g.color = RED;
    g.left.color = BLACK;
    g.right.color = BLACK;
    return g;
}
```

如果当前节点的父节点 P 是红色，叔叔节点 U 是黑色，且当前节点是父节点 P 的右子节点，将父节点 P 左旋，转换为最后一种情况，然后将父节点 P 作为当前节点继续处理

Case 2-1

还有一种对称的情况

Case 2-2

Java

private RBTreeNode<T> case2(RBTreeNode<T> p, boolean isLeftOfG) {
    RBTreeNode<T> g = p.parent;
    if (isLeftOfG) {
        RBTreeNode<T> x = leftRotate(p);
        x.parent = g;
        g.left = x;
    } else {
        RBTreeNode<T> x = rightRotate(p);
        x.parent = g;
        g.right = x;
    }
    return case3(g, isLeftOfG);
}

如果当前节点的父节点 P 是红色，叔叔节点 U 是黑色，且当前节点是父节点 P 的左子节点，将父节点 P 染黑，祖父节点 G 染红，然后将祖父节点 G 右旋

Case 3-1

还有一种对称的情况

Case 3-2

Java

private RBTreeNode<T> case3(RBTreeNode<T> g, boolean isLeftOfG) {
    RBTreeNode<T> gg = g.parent;
    if (isLeftOfG) {
        g.color = RED;
        g.left.color = BLACK;
        RBTreeNode<T> p = rightRotate(g);
        p.parent = gg;
        if (gg != null) {
            if (isLeftChild(gg, g)) {
                gg.left = p;
            } else {
                gg.right = p;
            }
        }
    } else {
        g.color = RED;
        g.right.color = BLACK;
        RBTreeNode<T> p = leftRotate(g);
        p.parent = gg;
        if (gg != null) {
            if (isLeftChild(gg, g)) {
                gg.left = p;
            } else {
                gg.right = p;
            }
        }
    }

    return p;
}

最后，我们还需要实现一些辅助函数：

Java

private boolean isRed(RBTreeNode<T> x) {
    return x != null && x.color == RED;
}

private boolean isLeftChild(RBTreeNode<T> p, RBTreeNode<T> x) {
    return x == p.left;
}

private RBTreeNode<T> uncle(RBTreeNode<T> x) {
    if (x.parent == null || x.parent.parent == null) {
        return null;
    }
    
    return isLeftChild(x.parent.parent, x.parent) ? x.parent.parent.right : x.parent.parent.left;
}

插入操作如下：

Java

private RBTreeNode<T> insert(RBTreeNode<T> x, T val) {
    if (x == null) {
        return new RBTreeNode<T>(val, RED);
    }

    if (val.compareTo(x.val) < 0) {
        x.left = insert(x.left, val);
        x.left.parent = x;
    } else {
        x.right = insert(x.right, val);
        x.right.parent = x;
    }

    if (isRed(x)) {
        RBTreeNode<T> p = x.parent;
        RBTreeNode<T> g = p.parent;
        RBTreeNode<T> u = uncle(x);

        if (isRed(p)) {
            if (isRed(u)) {
                return case1(g);
            } else {
                if (isLeftChild(g, p)) {
                    if (isLeftChild(p, x)) {
                        return case2(p, true);
                    } else {
                        return case3(g, true);
                    }
                } else {
                    if (isLeftChild(p, x)) {
                        return case3(g, false);
                    } else {
                        return case2(p, false);
                    }
                }
            }
        }
    }

    return x;
}

public void insert(T val) {
    root = insert(root, val);
    case0(root);
}

红黑树的查找、插入和删除操作的时间复杂度都是 \(O\left(\log n\right)\)，其中 \(n\) 是树的节点数。

相比平衡树，红黑树的实现更加复杂，整棵树也不如平衡树平衡，但是红黑树的插入和删除操作需要的旋转次数更少，因此红黑树的性能更好，在实际应用中更加广泛。

B 树

B 树（B-Tree）是上述平衡树的一般化形式。它一种多路搜索树，每个节点可以有多个子节点。对于 \(m\) 阶的 B 树，其满足以下性质：

每个节点最多有 \(m\) 个子节点；
每个内部节点至少有 \(\left\lceil m / 2 \right\rceil\) 个子节点；
如果根节点不是叶子节点，则根节点至少有 \(2\) 个子节点；
有 \(k\) 个子节点的节点包含 \(k - 1\) 个键；
所有叶子节点都在同一层。

下面是一个典型的 \(4\) 阶 B 树：

B-Tree Example

可以看到，它除了满足上述性质外，还满足中序遍历的有序性。

树的节点和树的定义如下：

Java

public class BTree<T extends Comparable<T>> {
    public class BTreeNode<T extends Comparable<T>> {
        List<T> keys;
        List<BTreeNode<T>> children;
        BTreeNode<T> parent;
        BTreeNode() {
            this.keys = new ArrayList<T>();
            this.children = new ArrayList<BTreeNode<T>>();
        }
    }

    private BTreeNode<T> root;
    private int m;
}

在插入时，首先按照大小比较关系在叶子节点中找到插入位置并插入。

如果该节点元素个数小于 \(m - 1\)，则无需其它操作；
如果该节点元素个数等于 \(m - 1\)，则需要分裂该节点：
- 将该节点的中间元素插入到父节点中；
- 将该节点分裂为两个节点，分别包含左右两部分元素；
- 递归向上分裂，直到根节点。

例如，我们想要构建一棵 \(5\) 阶 B 树：

我们首先插入 1、3、7、14：
插入 8 时，节点元素达到 \(5\)，引起分裂：
继续插入 5、11、17，不会引起分裂：
插入 13 时，节点元素达到 \(5\)，引起分裂：
继续插入 6、12、20、23
插入 26 时，节点元素达到 \(5\)，引起分裂：
插入 4 时，节点元素达到 \(5\)，引起分裂：
继续插入 16、18、24、25
插入 19 时，节点元素达到 \(5\)，引起分裂：

插入操作如下：

Java

private BTreeNode<T> insert(BTreeNode<T> x, T val) {
    if (x == null) {
        return new BTreeNode<T>();
    }

    int i = 0;
    while (i < x.keys.size() && val.compareTo(x.keys.get(i)) > 0) {
        i++;
    }

    if (x.children.isEmpty()) {
        x.keys.add(i, val);
    } else {
        BTreeNode<T> child = insert(x.children.get(i), val);
        x.keys.add(i, child.keys.remove(0));
        x.children.add(i + 1, child);
        child.parent = x;
    }

    if (x.keys.size() == m) {
        return split(x);
    }

    return x;
}

private BTreeNode<T> split(BTreeNode<T> x) {
    BTreeNode<T> y = new BTreeNode<T>();
    int mid = x.keys.size() / 2;
    T key = x.keys.get(mid);

    y.keys.addAll(x.keys.subList(mid + 1, x.keys.size()));
    x.keys.subList(mid, x.keys.size()).clear();

    y.children.addAll(x.children.subList(mid + 1, x.children.size()));
    x.children.subList(mid + 1, x.children.size()).clear();

    if (x.parent == null) {
        BTreeNode<T> root = new BTreeNode<T>();
        root.keys.add(key);
        root.children.add(x);
        root.children.add(y);
        x.parent = root;
        y.parent = root;
        return root;
    }

    int i = 0;
    while (i < x.parent.keys.size() && key.compareTo(x.parent.keys.get(i)) > 0) {
        i++;
    }

    x.parent.keys.add(i, key);
    x.parent.children.add(i + 1, y);
    y.parent = x.parent;

    if (x.parent.keys.size() == m) {
        return split(x.parent);
    }

    return x.parent;
}

public void insert(T val) {
    root = insert(root, val);
}

删除时，首先找到要删除的元素，然后：

首先删除 8，直接删除即可：
删除 20，并将继任节点（23）上移：
删除 18，该叶子节点中的元素个数剩了 \(1\)。而刚好发现有个相邻的兄弟节点很丰满，于是借道父节点借一个元素：
删除 5，该内部节点中的元素个数剩了 \(1\)。而它相邻的兄弟节点都并不丰满，无法借给它。于是只能合并：

删除操作如下：

Java

private BTreeNode<T> delete(BTreeNode<T> x, T val) {
    if (x == null) {
        return null;
    }

    int i = 0;
    while (i < x.keys.size() && val.compareTo(x.keys.get(i)) > 0) {
        i++;
    }

    if (x.children.isEmpty()) {
        x.keys.remove(i);
    } else {
        BTreeNode<T> child = delete(x.children.get(i), val);
        if (child == null) {
            x.keys.remove(i);
            x.children.remove(i);
        }
    }

    if (x.keys.size() < m / 2) {
        return merge(x);
    }

    return x;
}

private BTreeNode<T> merge(BTreeNode<T> x) {
    if (x.parent == null) {
        if (x.keys.isEmpty()) {
            return x.children.get(0);
        }
        return x;
    }

    int i = 0;
    while (i < x.parent.children.size() && x != x.parent.children.get(i)) {
        i++;
    }

    if (i > 0 && x.parent.children.get(i - 1).keys.size() > m / 2) {
        BTreeNode<T> y = x.parent.children.get(i - 1);
        x.keys.add(0, x.parent.keys.get(i - 1));
        x.parent.keys.set(i - 1, y.keys.remove(y.keys.size() - 1));

        if (!y.children.isEmpty()) {
            x.children.add(0, y.children.remove(y.children.size() - 1));
            x.children.get(0).parent = x;
        }
    } else if (i < x.parent.children.size() - 1 && x.parent.children.get(i + 1).keys.size() > m / 2) {
        BTreeNode<T> y = x.parent.children.get(i + 1);
        x.keys.add(x.parent.keys.get(i));
        x.parent.keys.set(i, y.keys.remove(0));

        if (!y.children.isEmpty()) {
            x.children.add(y.children.remove(0));
            x.children.get(x.children.size() - 1).parent = x;
        }
    } else {
        BTreeNode<T> y = x.parent.children.get(i - 1);
        y.keys.add(x.parent.keys.remove(i - 1));
        y.keys.addAll(x.keys);
        y.children.addAll(x.children);
        x.keys.clear();
        x.children.clear();
        x.parent.children.remove(i);
    }

    if (x.parent.keys.size() < m / 2) {
        return merge(x.parent);
    }

    return x.parent;
}

public void delete(T val) {
    root = delete(root, val);
}

B 树的查找、插入和删除操作的时间复杂度都是 \(O\left(\log n\right)\)，其中 \(n\) 是树的节点数。

B+ 树

B+ 树（B+ Tree）是 B 树的一种变体，其与 B 树的区别在于：

有 \(k\) 个子节点的节点包含 \(k\) 个键；
所有叶子节点都在同一层，且叶子节点包含了所有的元素；
非叶子节点只包含索引，不包含元素。索引为子节点中的最小（大）元素。

B+ 树的优点在于内部节点只包含索引，占据更少的空间，因此一次性可以加载更多的索引到内存中，提高了查找效率。

算法笔记 | (1)

搜索树

二叉搜索树

平衡树

红黑树

B 树

B+ 树

Series 算法笔记

Suggested Posts

Comments

算法笔记 | (1) 搜索树

二叉搜索树

平衡树

红黑树

B 树

B+ 树

Series 算法笔记

Suggested Posts

Comments

Share This Post

算法笔记 | (1)

搜索树