数据结构：树

发表于 更新于 分类于
本文字数： 16k 阅读时长 ≈ 28 分钟
二叉树

二叉树

分类

  • 完全二叉树。
  • 满二叉树。
  • 二叉搜索树。
  • AVL树。
    • 红黑树。
    • 线段树。

二叉查找树

  • 左子树的键值总是小于根的键值。右子树的键值总是大于根的键值。即没有键值相等的节点。
  • 中序遍历结果有序。

二叉查找树的常用操作有：

  • put()：插入节点
  • get()：寻找一个节点
  • floor(key)：小于等于键的最大键
  • rank(key) 返回key的排名。
  • min()：返回最小值
  • deleteMin()：删除最小值
  • delete()：删除一个节点
  • keys()：将键值排序输出

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

img

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

img

BST 有一个重要性质，就是它的中序遍历结果递增排序。

img

数据结构与操作

基本数据结构：

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
public class BST<Key extends Comparable<Key>, Value> implements OrderedST<Key, Value> {

    protected Node root;

    protected class Node {
        Key key;
        Value val;
        Node left;
        Node right;
        // 以该节点为根的子树节点总数
        int N;
        // 红黑树中使用
        boolean color;

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

    @Override
    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null)
            return 0;
        return x.N;
    }

    protected void recalculateSize(Node x) {
        x.N = size(x.left) + size(x.right) + 1;
    }
}

为了方便绘图，下文中二叉树的空链接不画出来。

get()

  • 如果树是空的，则查找未命中；
  • 如果被查找的键和根节点的键相等，查找命中；
  • 否则递归地在子树中查找：如果被查找的键较小就在左子树中查找，较大就在右子树中查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Override
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()

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

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 @Override
public void put(Key key, Value value) {
    root = put(root, key, value);
}

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

floor()

floor(key)：小于等于键的最大键

  • 如果键小于根节点的键，那么 floor(key) 一定在左子树中；
  • 如果键大于根节点的键，需要先判断右子树中是否存在 floor(key)，如果存在就返回，否则根节点就是 floor(key)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);
    return t != null ? t : x;
}

rank()

rank(key) 返回 key 的排名。

  • 如果键和根节点的键相等，返回左子树的节点数；
  • 如果小于，递归计算在左子树中的排名；
  • 如果大于，递归计算在右子树中的排名，加上左子树的节点数，再加上 1（根节点）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Override
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
6
7
8
9
10
11
12
@Override
public Key min() {
    return min(root).key;
}

private Node min(Node x) {
    if (x == null)
        return null;
    if (x.left == null)
        return x;
    return min(x.left);
}

deleteMin()

令指向最小节点的链接指向最小节点的右子树。

img

1
2
3
4
5
6
7
8
9
10
11
public void deleteMin() {
    root = deleteMin(root);
}

public Node deleteMin(Node x) {
    if (x.left == null)
        return x.right;
    x.left = deleteMin(x.left);
    recalculateSize(x);
    return x;
}

delete()

  • 如果待删除的节点只有一个子树， 那么只需要让指向待删除节点的链接指向唯一的子树即可；
  • 否则，让右子树的最小节点替换该节点。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
    recalculateSize(x);
    return x;
}

keys()

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Override
public List<Key> keys(Key l, Key h) {
    return keys(root, l, h);
}

private List<Key> keys(Node x, Key l, Key h) {
    List<Key> list = new ArrayList<>();
    if (x == null)
        return list;
    int cmpL = l.compareTo(x.key);
    int cmpH = h.compareTo(x.key);
    if (cmpL < 0)
        list.addAll(keys(x.left, l, h));
    if (cmpL <= 0 && cmpH >= 0)
        list.add(x.key);
    if (cmpH > 0)
        list.addAll(keys(x.right, l, h));
    return list;
}

分析

二叉查找树所有操作在最坏的情况下所需要的时间都和树的高度成正比。二叉查找树的算法运行时间取决于树的形状，而树的形状又取决于键被插入的先后顺序。

最好的情况下树是完全平衡的，每条空链接和根节点的距离都为 logN。

img

在最坏的情况下，树的高度为 N。

img

AVL树

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：

  • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。
  • 并且左右两个子树都是一棵平衡二叉树。

平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。

AVL树定义：AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。在AVL中任何节点的两个儿子子树的高度最大差别为1，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

数据结构与算法

AVL树的自平衡操作——旋转：

AVL树最关键的也是最难的一步操作就是旋转。旋转主要是为了实现AVL树在实施了插入和删除操作以后，树重新回到平衡的方法。下面我们重点研究一下AVL树的旋转。

对于一个平衡的节点，由于任意节点最多有两个儿子，因此高度不平衡时，此节点的两颗子树的高度差2.容易看出，这种不平衡出现在下面四种情况：

img

  • 6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。
  • 6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。
  • 2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。
  • 2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。

从图2中可以可以看出，1和4两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。

单旋转

单旋转是针对于左左和右右这两种情况的解决方案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决方案，节点k2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的左子树X子树，所以属于左左情况。

img

为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。

这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，它是一棵AVL树，因为X向上一移动了一层，Y还停留在原来的层面上，Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同，插入操作使得X高度长高了。因此，由于这颗子树高度没有变化，所以通往根节点的路径就不需要继续旋转了。

双旋转

对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决方案，节点k3不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的右子树k2子树，所以属于左右情况。

img

为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树。

堆

堆是一颗完全二叉树。

操作

  • 插入节点
  • 删除元素。
  • 删除最大(最小元素)

其存在一部分的私有方法：

  • 上浮/下沉。

分类

数组堆

可以看常用算法：排序算法。

假设以数组0位开始存储。则假设节点的index为i，其父类节点的index=(i-1)/2其左孩子的index=2*i+1

二(d)叉堆

d叉堆在下沉时需要考虑d次。

索引堆

数组堆只能看到堆首的元素，而不能看到堆中间的元素。

如果需要看到堆中间的元素，或需要对中间的元素进行修改。则需要使用索引堆，其维护了一个元素的索引。

2-3查找树

2-3查找树引入了2-节点和3-节点，目的是为了让树平衡。即一个节点可以存放一个元素或两个元素，其具有2/3个孩子，也是其名称的原因。

一颗完美平衡的2-3查找树的所有空链接到根节点的距离应该是相同的。2-3树是一颗绝对平衡的树。

img

操作

算法操作

维持平衡：对于2-3树而言，添加节点永远不会添加到一个空的位置，即它会和最后找到的叶子节点进行融合。

常用操作有：

  • 插入操作。
  • 删除操作。

插入操作

插入操作和BST的插入操作有很大区别，BST 的插入操作是先进行一次未命中的查找，然后再将节点插入到对应的空链接上。但是2-3查找树如果也这么做的话，那么就会破坏了平衡性。它是将新节点插入到叶子节点上。

根据叶子节点的类型不同，有不同的处理方式：

  • 如果插入到2-节点上，那么直接将新节点和原来的节点组成3-节点即可。

img

  • 如果是插入到3-节点上，就会产生一个临时4-节点时，需要将4-节点分裂成3个2-节点，并将中间的2-节点移到上层节点中。如果上移操作继续产生临时4-节点则一直进行分裂上移，直到不存在临时4-节点。

img

性质

2-3查找树插入操作的变换都是局部的，除了相关的节点和链接之外不必修改或者检查树的其它部分，而这些局部变换不会影响树的全局有序性和平衡性。

2-3查找树的查找和插入操作复杂度和插入顺序无关，在最坏的情况下查找和插入操作访问的节点必然不超过logN个，含有10亿个节点的2-3查找树最多只需要访问30个节点就能进行任意的查找和插入操作。

红黑树

概述

红黑树是2-3查找树，但它不需要分别定义2-节点和3-节点，而是在普通的二叉查找树之上，为节点添加颜色。指向一个节点的链接颜色如果为红色，那么这个节点和上层节点表示的是一个3-节点，而黑色则是普通链接。

img

性质

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制的一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色（叶子是NIL节点）。
  4. 如果一个节点是红色的，那么它的孩子节点都是黑色的。
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
    • 则没有路径能多于任何其他路径的两倍长。

其性质有：

  • 红链接都为左链接；
  • 完美黑色平衡，即任意空链接到根节点的路径上的黑链接数量相同。
  • 它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。

画红黑树时可以将红链接画平。

img

1
2
3
4
5
6
7
8
9
10
11
public class RedBlackBST<Key extends Comparable<Key>, Value> extends BST<Key, Value> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

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

算法

以下内容整理自wiki百科之红黑树。

红黑树的自平衡操作：

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为O(logn)次。

我们首先以二叉查找树的方法增加节点并标记它为红色。如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的（违背性质5）。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意：

  • 性质1和性质3总是保持着。
  • 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。
  • 性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。

算法

红黑树的操作思想与2-3树的思想完全一致，只是变为了一颗二叉树而已。

在操作方面，红黑树不同的地方主要在于插入操作与删除操作。其他操作与一般2-3树并无太大不同。

并且由于其插入操作与删除操作，额外带来了颜色转换操作，以及更为复杂的旋转操作。

插入操作

插入的节点一定为红色，红色的节点代表它要和它的父亲节点做融合。

情形1: 该树为空树，直接插入根结点的位置，违反性质1，把节点颜色有红改为黑即可。

情形2：Black Root，并拥有一个Red left，插入Red Right。

  • 则此时Root是一个4-节点，为将其分裂，使得子节点颜色为Black，父节点转为Red Root。

情形3：Black Root，拥有一个Red Left1，Red Left1拥有一个Red Left2。

  • 此时Root依然是一个4-节点，为将其分裂，进行右旋转操作。
  • G.left = 3;，P.right = G;，P.color = G.color;，G.color=Red

情形5 示意图

情形4：Black Root，拥有一个Red Left，Red Left拥有Red Right。

  • 由于红链接都是左链接，因此首先需要进行左旋转操作。
  • 之后转变为了情形3，即需要右旋转。

情形4 示意图

删除操作

如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题。对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素，并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值，不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。

我们只需要讨论删除只有一个儿子的节点(如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点（此时该节点的儿子将都为叶子节点），它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏性质3和性质4。通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。

需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N(在新的位置上)，称呼它的兄弟(它父亲的另一个儿子)为S。在下面的示意图中，我们还是使用P称呼N的父亲，SL称呼S的左儿子，SR称呼S的右儿子。

如果N和它初始的父亲是黑色，则删除它的父亲导致通过N的路径都比不通过它的路径少了一个黑色节点。因为这违反了性质5，树需要被重新平衡。有几种情形需要考虑:

情形1: N是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。

注意: 在情形2、5和6下，我们假定N是它父亲的左儿子。如果它是右儿子，则在这些情形下的左和右应当对调。

情形2: S是红色。在这种情形下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），所以我们可以接下去按情形4、情形5或情形6来处理。

情形2 示意图

情形3: N的父亲、S和S的儿子都是黑色的。在这种情形下，我们简单的重绘S为红色。结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。

情形3 示意图

情形4: S和S的儿子都是黑色，但是N的父亲是红色。在这种情形下，我们简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。

情形4 示意图

情形5: S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子。在这种情形下我们在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，他的右儿子是红色的，所以我们进入了情形6。N和它的父亲都不受这个变换的影响。

情形5 示意图

情形6: S是黑色，S的右儿子是红色，而N是它父亲的左儿子。在这种情形下我们在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质3没有被违反。但是，N现在增加了一个黑色祖先: 要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。所以，通过N的路径都增加了一个黑色节点。

此时，如果一个路径不通过N，则有两种可能性:

  • 它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。
  • 它通过N的新叔父，S的右儿子。那么它以前通过S、S的父亲和S的右儿子，但是现在只通过S，它被假定为它以前的父亲的颜色，和S的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。

在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。

情形6 示意图

操作

左旋转

因为合法的红链接都为左链接，如果出现右链接为红链接，那么就需要进行左旋转操作。

img

1
2
3
4
5
6
7
8
9
10
public Node rotateLeft(Node root) {
    Node B = root.right;
    toot.right = B.left;
    B.left = root;
    B.color = root.color;
    root.color = RED;
    B.N = root.N;
    recalculateSize(toot);
    return x;
}

右旋转

进行右旋转是为了转换两个连续的左红链接，这会在之后的插入过程中探讨。

img

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

颜色转换

维护颜色的时机：与AVL树一样。

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

img

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

插入

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

  • 如果右子节点是红色的而左子节点是黑色的，进行左旋转；
  • 如果左子节点是红色的，而且左子节点的左子节点也是红色的，进行右旋转；
  • 如果左右子节点均为红色的，进行颜色转换。

img

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
@Override
public void put(Key key, Value value) {
    root = put(root, key, value);
    root.color = BLACK;
}

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

    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);

    recalculateSize(x);
    return x;
}

可以看到该插入操作和二叉查找树的插入操作类似，只是在最后加入了旋转和颜色变换操作即可。

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

分析

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

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

  • 对于完全随机的数据，普通二分搜索树更有效。
    • 缺点：极端情况退化为链表。
  • 对于查询较多的情况，AVL有效。
  • 红黑树一定程度上牺牲了平衡性。
  • 统计性能更优（综合增删改查所有操作）。

B树

B-树

B树也是一种用于查找的平衡树，但是它不是二叉树。

B树的定义：B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

在B树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。

特征

B树作为一种多路搜索树（并不是二叉的）：

  1. 定义任意非叶子结点最多只有M个儿子；且M>2；
  2. 根结点的儿子数为[2, M]；
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
  4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）；
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
  6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  8. 所有叶子结点位于同一层；

B树创建的示意图：

img

B+树

B+树是B树的变体，也是一种多路搜索树：B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树，所有记录节点都是按照键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。

其定义基本与B-树相同，除了：

  1. 非叶子结点的子树指针与关键字个数相同；
  2. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
  3. 为所有叶子结点增加一个链指针；
  4. 所有关键字都在叶子结点出现；

B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的性质：

  1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
    1. 1554189317854
  2. 不可能在非叶子结点命中；
  3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
  4. 更适合文件索引系统。

下面为一个B+树创建的示意图：

img

B+树的插入

B+树的插入必须保证插入后叶子结点中的记录依然排序

1554189709939

页的拆分意味着磁盘的操作，所以应该在可能情况下尽量减少页的拆分操作

旋转

当leaf Page已经满，但是其左右的兄弟结点没有满，则进行旋转，将记录移到所在页的兄弟结点上。

删除

B+树使用填充因子来控制删除，填充因子的最小值是50%

1554190074278

B*树

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。

B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

线段树Segment Tree

概述

为什么要用

  • 有一种问题只关注一个区间
  • 是一个动态的问题，数据是不断变化的。

案例问题

  • 区间染色：有一面墙长度为n，每次选择一段墙进行染色。在m次操作后可以看到多少种颜色？在[i,j]区间内可以看到多少种颜色。
    • 动态的，因为染色的次数不确定。
  • 区间查询：对一个区间内的所有数据进行统计查询，例如查询[i,j]内的最大值、最小值、或区间数字和。

数据结构与操作

Trie树

Tire树称为字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。　

Tire树的三个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
  3. 每个节点的所有子节点包含的字符都不相同。

应用

  1. 串的快速检索

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。

在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

  1. “串”排序

给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

  1. 最长公共前缀

对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为求公共祖先的问题。

并查集

用于解决动态连通性问题，能动态连接两个点，并且判断两个点是否连通。

参考

  1. Cyc2018