数据结构

大约 30 分钟

数据结构

线性表

数组

  • 一维数组
  • 二位数组（矩阵）

字符串基础

  • 字符串遍历
  • 字符串比较
  • 字符串分割
  • 字符计数
  • 字符串翻转
  • 回文串

栈open in new window

在栈(stack)中，栈实现的是一种后进先出(last-in，first-out， LIFO)策略。

栈上的INSERT操作称为压入(PUSH)，而无元素参数的DELETE操作称为弹出(POP)。

  • 顺序栈
  • 链式栈

队列open in new window

在队列(queue)中，队列实现的是一种先进先出(first-in，first-out， FIFO)策略。

队列上的INSERT操作称为入队(ENQUEUE)，DELETE操作称为出队(DEQUEUE)。队列有队头(head)和队尾(tail)。

队列中的元素存放在位置Q.head， Q.head+ 1， ...， Q.tail—1， 并在最后的位置“环绕“，感觉好像位置1紧邻在位置n后面形成一个环序。

当Q.head=Q.tail时，队列为空。初始时有Q.head=Q.tail=l。如果试图从空队列中删除一个元素，则队列发生下溢。当Q.head= Q.tail+l时，队列是满的，此时若试图插入一个元素，则队列发生上溢。

  • 普通队列
  • 双端队列
  • 阻塞队列
  • 并发队列
  • 阻塞并发队列

链表open in new window

链表(linked list)是一种这样的数据结构，其中的各对象按线性顺序排列。数组的线性顺序是由数组下标决定的，然而与数组不同的是，链表的顺序是由各个对象里的指针决定的。

双向链表(doubly linked list) L的每个元素都是一个对象，每个对象有一个关键字key和两个指针：next和prev。对象中还可以包含其他的辅助数据（或称卫星数据）。设x为链表的一个元素，x.next指向它在链表中的后继元素，x.prev则指向它的前驱元素。如果x. prev=NIL， 则元素x没有前驱，因此是链表的第一个元素，即链表的头(head)。如果x.next= NIL， 则元素x没有后继，因此是链表的最后一个元素，即链表的尾(tail)。属性L.head指向链表的第一个元素。如果L.head= NIL， 则链表为空。

链表可以有多种形式。它可以是单链接的或双链接的，可以是已排序的或未排序的，可以是循环的或非循环的。如果一个链表是单链接的(singly linked) ， 则省略每个元素中的prev指针。

如果链表是已排序(sorted)的，则链表的线性顺序与链表元素中关键字的线性顺序一致；据此，最小的元素就是表头元素，而最大的元素则是表尾元素。如果链表是未排序(unsorted)的，则各元素可以以任何顺序出现。

在循环链表(circular list)中，表头元素的prev指针指向表尾元素，而表尾元素的next指针则指向表头元素。我们可以将循环链表想象成一个各元素组成的圆环。

哨兵(sentinel)是一个哑对象，其作用是简化边界条件的处理。

散列表（哈希表）open in new window

散列表

散列表(hash table)是实现字典操作的一种有效数据结构。尽管最坏情况下，散列表中查找一个元素的时间与链表中查找的时间相同，达到了。然而在实际应用中，散列查找的性能是极好的。在一些合理的假设下，在散列表中查找一个元素的平均时间是。

在直接寻址方式下，具有关键字k的元素被存放在槽k中。在散列方式下，该元素存放在槽h(k)中；即利用散列函数(hash function)h， 由关键字k计算出槽的位置。这里，函数h将关键字的全域U映射到散列表(hash table) T[0 .. m—1]的槽位上：

这里散列表的大小m一般要比切小得多。我们可以说一个具有关键字k的元素被散列到槽h(k)上，也可以说h(k)是关键字k的散列值。

这里存在一个问题：两个关键字可能映射到同一个槽中。我们称这种情形为冲突(collision)。幸运的是，我们能找到有效的方法来解决冲突。

我们一方面可以通过精心设计的散列函数来尽量减少冲突的次数，另一方面仍需要有解决可能出现冲突的办法， 链接法(chaining)，开放寻址法(open addressing)。

散列函数

在散列表中，为了将数据分布到不同的桶中，常常使用一个散列函数将数据映射到桶的索引上。常见的散列函数包括取模散列、乘法散列、除法散列等。

除法散列法

在用来设计散列函数的除法散列法中，通过取k除以m的余数，将关键字k映射到m个槽中的某一个上，即散列函数为：

在使用除法散列法时，需要选择一个适当的模数m，以便将键散列到[0， m-1]范围内的槽中。如果选择不当的m值，可能会导致一些槽被过度利用，而其他槽则未被使用，这将导致散列表性能降低。为避免这种情况，通常需要避免选择以下m值：

  • 选择2的幂次，这可能会导致对低位的散列函数没有利用；
    • 如果散列表的大小是2的幂次，比如说选择散列表大小为64，那么取模运算实际上就变成了取元素的低6位，因为64等于。这种情况下，元素的高位信息就被丢失了，只有低位信息被使用来计算散列值。这可能导致很多不同的元素被映射到同一个位置上，因为它们的低位信息相同。因此，选择2的幂次作为散列表大小时，可能会导致对低位的散列函数没有利用，从而影响散列的均匀性和性能。
    • 例如，m不应为2的幕，因为如果m=2八则h(k)就是K的p个最低位数字。
  • 选择约为2的整数次幂的值，这可能会导致散列函数对于某些特定的键值序列无法工作；
  • 选择质数，尽管这种方法不是绝对的保险，但在实践中，质数通常可以获得比较好的性能。
乘法散列法

构造散列函数的乘法散列法包含两个步骤。

  • 第一步，用关键字k乘上常数A(O<A<1)，并提取kA的小数部分。
  • 第二步，用m乘以这个值，再向下取整。总之，散列函数为：，这里"kA mod 1"是取kA的小数部分，即。

链接法(chaining)

通过链接法解决冲突

在链接法中，把散列到同一槽中的所有元素都放在一个链表中。

链接法散列的分析

给定一个能存放n个元素的、具有m个槽位的散列表T，定义T的装载因子(load factor) a 为n/m，即一个链的平均存储元素数。我们的分析将借助a来说明，a可以小于、等于或大于1。

  • 哈希表的负载因子（load factor）是指哈希表中已存储的键值对数量 与哈希表的容量 的比值，即 。在哈希表中，当负载因子过高时，冲突的概率也就越大，哈希表的性能也就越低。因此，为了保持哈希表的性能，通常需要调整哈希表的容量，使得负载因子保持在一个合适的范围内，比如 0.7 左右。

散列方法的最坏情况性能很差，所有的n个关键字都散列到同一个槽中，从而产生出一个长度为n的链表。这时，最坏情况下查找的时间为再加上计算散列函数的时间，如此就和用一个链表来链接所有的元素差不多了。

散列方法的平均性能依赖于所选取的散列函数h，将所有的关键字集合分布在m个槽位上的均匀程度。

如果散列表中槽数至少与表中的元素数成正比，则有，从而。所以，查找操作平均需要常数时间。当链表采用双向链接时，插入操作在最坏情况下需要时间，删除操作最坏情况下也需要时间，因而，全部的字典操作平均情况下都可以在时间内完成。

开放寻址法(open addressing)

开放寻址法是一种哈希表的解决冲突方法，它的基本思想是：当发生哈希冲突时，依次探查哈希表中的下一个位置，直到找到一个空闲的位置为止。其具体步骤如下：

  • 根据散列函数计算出要插入的元素的哈希值，得到在哈希表中的位置。
  • 如果该位置没有被占据，则直接插入该元素；如果该位置被占据了，则使用一定的探测策略找到下一个空闲位置，并将该元素插入到该位置。
  • 如果探测到哈希表的末尾仍然没有找到空闲位置，则需要扩大哈希表的容量，并将原有的元素重新哈希到新的哈希表中。

在开放寻址法中，探测策略有很多种，比较常见的有线性探测、二次探测和双重散列等。其中，线性探测是最简单、最常用的一种探测策略，它的探测方式是按照线性的顺序依次访问下一个位置，直到找到一个空闲的位置为止。二次探测和双重散列则是线性探测的改进版本，它们可以更加灵活地选择下一个探测位置，从而避免线性探测的一些缺陷。

树open in new window

术语

  • wiki:https://en.wikipedia.org/wiki/Tree_%28data_structure%29

  • 树的定义：

    • 树是一种非线性的数据结构，它由节点（node）和边（edge）组成。
    • 节点(node)：包括一个数据元素及若干指向其他节点的分支信息。
    • 节点的度（degree）：指节点拥有的子节点数量。
    • 树的度（degree）：指树中节点的最大度数。
    • 叶子节点（leaf）：指没有子节点的节点。
    • 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
    • 深度：对于任意节点n，n的深度为从根到n的唯一路径长，根的深度为0。
    • 高度：对于任意节点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0。
    • 子树（subtree）：指树中某个节点的所有后代节点和边组成的树。
    • 祖先节点（ancestor）：指从根节点到某个节点路径上的所有节点，包括该节点本身。
    • 后代节点（descendant）：指某个节点的所有子孙节点。
    • 兄弟节点（sibling）：指具有同一个父节点的节点。

  • 树的深度和高度的区别：open in new window

    • I learned that depth and height are properties of a node:
      • The depth of a node is the number of edges from the node to the tree's root node.
        • A root node will have a depth of 0.
      • The height of a node is the number of edges on the longest path from the node to a leaf.
        • A leaf node will have a height of 0.
    • Properties of a tree:
      • The height of a tree would be the height of its root node， or equivalently， the depth of its deepest node.
      • The diameter (or width) of a tree is the number of nodes on the longest path between any two leaf nodes. The tree below has a diameter of 6 nodes.

二叉树的定义：

  • 每个节点的度都不大于2.
  • 每个节点的孩子节点次序不能任意颠倒。

二叉树的性质：

  • 在非空二叉树中，第 i 层的最大结点数为 ， i ≥ 1。
  • 一个深度为 的二叉树最多有 个节点。
  • 一个有 个节点的二叉树，其深度至少为 。
  • 对于任意一棵二叉树，如果其叶子节点数为 ，度数为 的节点数为 ，则 。
  • 具有 n 个结点的完全二叉树的深度为 。
  • 具有 n 个结点的满二叉树的深度为 。

完全二叉树的性质：

  • 深度为 的完全二叉树，其前 层结点数均达到最大值，第 层的结点都集中在最左边。
  • 对于任意一棵完全二叉树，如果其叶节点数为 ，度为 的非叶子节点数为 ，则 。
  • 对于任意一棵非空完全二叉树，设其深度为 ，则：
    • 第 层（ ），有 个节点；
    • 第 层的节点数在 范围内。
  • 若将一棵深度为 、有 个结点的二叉树自顶向下、从左至右编号，则对任意结点 （ ），有：
    • 结点 的左儿子编号为 ，右儿子编号为 ；
    • 结点 的父结点编号为 （ 时）。
  • 在按层序编号的情况下，如果一个节点的编号为 ，则它在完全二叉树中的深度 为 。
  • 这些性质中，第一条和第三条是最为重要的。第一条性质说明了完全二叉树的结构，而第三条性质则说明了完全二叉树的节点数与深度之间的关系。

满二叉树的性质有：

  • 深度为k的满二叉树，共有个节点。
  • 满二叉树中，第i（1≤i≤2^k-1）个节点，如果存在，则其左子树的编号为2i，右子树的编号为2i+1。
  • 满二叉树中，叶子节点只出现在最下一层，每个非叶子节点都有两个子节点。

树的种类

树的种类:

  • 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树。
  • 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
    • 二叉树：每个节点最多含有两个子树的树称为二叉树；
      • 完全二叉树：对于一棵二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
        • 满二叉树：所有叶节点都在最底层的完全二叉树；
      • 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
      • 排序二叉树(二叉查找树（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树；
    • 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
    • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。

常见的树类型：

  • 二叉树（Binary Tree）：每个节点最多有两个子节点的树结构，包括二叉搜索树、平衡二叉树、满二叉树、完全二叉树等。
  • 红黑树（Red-Black Tree）：一种自平衡二叉搜索树，保证了任何一个节点的左右子树的高度差小于两倍。
  • B树（B-Tree）：一种多路平衡查找树，节点可以有多个子节点，被广泛应用于文件系统和数据库中。
  • Trie树（字典树，Prefix Tree）：一种树形结构，用于表示字符串集合，具有快速查找、插入和删除字符串的特点。
  • AVL树（平衡二叉树）：一种自平衡二叉搜索树，通过旋转操作来保持树的平衡，任何节点的左子树和右子树的高度最多相差1。
  • Huffman树（最优二叉树）：一种带权路径长度最短的树结构，用于数据压缩算法中的数据编码。
  • 伸展树（Splay Tree）：一种自适应搜索树，通过对访问过的节点进行旋转操作，将其移动到根节点位置，以提高访问效率。
  • 树状数组（Binary Indexed Tree）：一种特殊的树形数据结构，用于高效地计算数列的前缀和、区间和等。
  • KD树（K-Dimensional Tree）：一种用于存储k维空间中的数据的树形结构，可以快速查找k维空间中的最近邻点。
  • 23树（2-3 Tree）：一种自平衡二叉树，节点可以有2个或3个子节点，常用于文件系统和数据库中。
  • 树堆（Tree Heap）：一种基于树形结构实现的堆数据结构，用于支持高效的插入、删除和查找最小值操作。
  • 字典森林（Trie Forest）：由多个Trie树构成的集合，用于高效地存储和查找大量字符串。

二叉搜索树open in new window

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于有n个结点的一棵完全二叉树来说，这些操作的最坏运行时间为。然而，如果这棵树是一条n个结点组成的线性链，那么同样的操作就要花费的最坏运行时间。

实际上，我们并不能总是保证随机地构造二叉搜索树，然而可以设计二叉搜索树的变体，来保证基本操作具有好的最坏情况性能。给出了一个这样的变形，即红黑树，它的树高为。

二叉搜索树定义

OI WIKIopen in new window

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 任意节点的左、右子树也分别为二叉查找树；

二叉搜索树中的关键字总是以满足二叉搜索树性质的方式来存储：

  • 设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key <= x. key。如果y是x右子树中的一个结点，那么y.key >= x.key。

遍历

定理12.1

  • 如果x是一棵有n个结点子树的根，那么调用INORDER-TREE-WALK(x)需要时间。

递归算法来按序输出二叉搜索树中的所有关键字：

  • 中序遍历(inorder tree walk)中输出的子树根的关键字位于其左子树的关键字值和右子树的关键字值之间。
  • 先序遍历(preorder tree walk)中输出的根的关键字在其左右子树的关键字值之前。
  • 后序遍历(postorder tree walk)中输出的根的关键字在其左右子树的关键字值之后。
INORDER-TREE-WALK(x)
1 if x ≠ NIL
2   INORDER-TREE-WALK(x.left)
3   print x.key
4   INORDER-TREE-WALK(x.right)

查询

定理12.2

  • 在一棵高度为h的二叉搜索树上，动态集合上的操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR可以在O(h)时间内完成。
查找
TREE-SEARCH(x， k)
1   if x == NIL or k == x.key
2       return x
3   if k < x.key
4       return TREE-SEARCH(x.left， k)
5   else 
6       return TREE-SEARCH(x.right， k)

ITERATIVE-TREE-SEARCH(x， k)
1   while x ≠ NIL and k ≠ x.key
2       if k < x.key
3           x = x.left
4       else
5           x = x.right
6   return x

从树根开始递归期间遇到的结点就形成了一条向下的简单路径，所以TREE-SEARCH的运行时间为，其中h是这棵树的高度。

最大关键字元素和最小关键字元素

算法导论中的TREE-MINIMUM用于找到二叉搜索树中的最小关键字节点，其伪代码如下：

TREE-MINIMUM(x)
1  while x.left != NIL
2      x = x.left
3  return x

其中，x为二叉搜索树中的任意节点，NIL表示一个空节点，也可以理解为null。该算法的思想是从x开始沿着左子树一直走到最底层，最后返回该节点即可。如果二叉搜索树为空树，则返回NIL。

算法导论中的TREE-MAXIMUM用于找到一棵二叉搜索树中键值最大的节点。其伪代码如下：

TREE-MAXIMUM(x)
1  while x.right != NIL
2      x = x.right
3  return x

其中，x为二叉搜索树中的任意节点，NIL表示一个空节点，也可以理解为null。该算法的思想是从x开始沿着右子树一直走到最底层，最后返回该节点即可。如果二叉搜索树为空树，则返回NIL。

后继和前驱

给定一棵二叉搜索树中的一个结点，有时候需要按中序遍历的次序查找它的后继。如果所有的关键字互不相同，则一个结点x的后继是大于x.key的最小关键字的结点。

一棵二叉搜索树的结构允许我们通过没有任何关键字的比较来确定一个结点的后继。

TREE-SUCCESSOR 是二叉搜索树中的一种操作，用于查找某个节点的后继节点（即中序遍历中当前节点的下一个节点）。算法导论中 TREE-SUCCESSOR 的伪代码如下：

TREE-SUCCESSOR(x)
1. if x.right != NIL
2.    return TREE-MINIMUM(x.right)
3. y = x.p
4. while y != NIL and x == y.right
5.    x = y
6.    y = y.p
7. return y

TREE-SUCCESSOR的伪代码分为两种情况。

  • 如果结点x的右子树非空，那么x的后继恰是x右子树中的最左结点，通过第2行中的TREE-MINIMUM(x.right)调用可以找到。
  • 如果结点x的右子树非空并有一个后继y，那么y就是x的有左孩子的最底层祖先，并且它也是x的一个祖先。为了找到y，只需简单地从x开始沿树而上直到遇到一个其双亲有左孩子的结点。TREE-SUCCESSOR中的第3~7行正是处理这种情况。

TREE-PREDECESSOR 是二叉搜索树中的一种操作，用于查找某个节点的前驱节点（即中序遍历中当前节点的上一个节点）。算法导论中TREE-PREDECESSOR的伪代码如下：

TREE-PREDECESSOR(x) 
1.  if x.left != NIL 
2.      return TREE-MAXIMUM(x.left) 
3.  y = x.p 
4.  while y != NIL and x == y.left 
5.      x = y 
6.      y = y.p 
7.  return y

TREE-PREDECESSOR的伪代码分为两种情况：

  • 如果x有左子树，那么它的前驱就是左子树中最大的节点；
  • 否则，它的前驱就是它的最低祖先节点，且该祖先节点有一个右孩子也是x的祖先。

在一棵高度为h的树上，TREE-SUCCESSOR的运行时间为，因为该过程或者遵从一条简单路径沿树向上或者遵从简单路径沿树向下。过程TREE-PREDECESSOR与TREE­SUCCESSOR是对称的，其运行时间也为。

插入和删除

定理12.3

  • 在一棵高度为h的二叉搜索树上，实现动态集合操作INSERT和DELETE的运行时间均为。
插入
TREE-INSERT(T， z)
1   y = NIL
2   x = T.root
3   while x != NIL
4       y = x
5       if z.key < x.key
6           x = x.left
7       else 
            x = x.right
8   z.p = y
9   if y == NIL
10      T.root = z      // 树T原来为空树，直接插入节点z作为根节点
11  elseif z.key < y.key
12      y.left = z      // z的key小于y的key，z成为y的左儿子
13  else 
        y.right = z   // z的key大于等于y的key，z成为y的右儿子

TREE-INSERT从树根开始，指针x记录了一条向下的简单路径，并查找要替换的输入项z的NIL。该过程保持遍历指针(trailing pointer) y作为x的双亲。初始化后，第3~7行的while循环使得这两个指针沿树向下移动，向左或向右移动取决于z.key和x.key的比较，直到x变为NIL。这个NIL占据的位置就是输入项z要放置的地方。我们需要遍历指针y，这是因为找到NIL时要知道z属于哪个结点。第8~13行设置相应的指针，使得z插入其中。

与其他搜索树上的原始操作一样，过程TREE­INSERT在一棵高度为h的树上的运行时间为。

删除

从一棵二叉搜索树T中删除一个结点z的整个策略分为三种基本情况（如下所述），但只有一种情况有点棘手。

  • 如果z没有孩子结点，那么只是简单地将它删除，并修改它的父结点，用NIL作为孩子来替换z。
  • 如果z只有一个孩子，那么将这个孩子提升到树中z的位置上，并修改z的父结点，用z的孩子来替换z。
  • 如果z有两个孩子，那么找z的后继y(一定在z的右子树中），并让y占据树中z的位置。z的原来右子树部分成为y的新的右子树，并且z的左子树成为y的新的左子树。这种情况稍显麻烦（如下所述），因为还与y是否为z的右孩子相关。

从一棵二叉搜索树T中删除一个给定的结点z，这个过程取指向T和z的指针作为输入参数。考虑4种情况，它与前面概括出的三种情况有些不同。

  • 如果z没有左孩子，那么用其右孩子来替换z，这个右孩子可以是NIL，也可以不是。
  • 如果z仅有一个孩子且为其左孩子，那么用其左孩子来替换z。
  • 如果z既有一个左孩子又有一个右孩子。
    • 我们要查找z的后继y。
      • 如果y位于z的右子树中并且没有左孩子。现在需要将y移出原来的位置进行拼接，并替换树中的z，并仅留下y的右孩子。
      • 如果y位于z的右子树中并且不是z的右孩子。在这种情况下，先用y的右孩子替换y，然后再用y替换之。

为了在二叉搜索树内移动子树，定义一个子过程TRANSPLANT，它是用另一棵子树替换一棵子树并成为其双亲的孩子结点。当TRANSPLANT用一棵以v为根的子树来替换一棵以u为根的子树时，结点u的双亲就变为结点v的双亲，并且最后v成为u的双亲的相应孩子。

TRANSPLANT(T， u， v)
1. if u.p == NIL
2.  T.root = v
3. elseif u == u.p.left
4.  u.p.left = v
5. else 
    u.p.right = v
6. if v != NIL
7.  v.p = u.p

第1~2行处理u是T的树根的情况。否则，u是其双亲的左孩子或右孩子。如果u是一个左孩子，第3~4行负责u.p. left的更新；如果u是一个右孩子，第5行更新u.p. right。我们允许v为NIL，如果v为非NIL时，第6~7行更新v.p。注意到，TRANSPLANT并没有处理v. left和v.right的更新；这些更新都由TRANSPLANT的调用者来负责。

TREE-DELETE(T， z)  
1   if z.left == NIL  
2       TRANSPLANT(T， z， z.right)     // replace z by its right child  
3   elseif z.right == NIL  
4       TRANSPLANT(T， z， z.left)      // replace z by its left child  
5   else 
        y = TREE-MINIMUM(z.right)       // y is z’s successor  
6       if y ≠ z.right                  // is y farther down the tree?  
7           TRANSPLANT(T， y， y.right) // replace y by its right child
8           y.right = z.right           // z’s right child becomes  
9           y.right.p = y               // y’s right child
10      TRANSPLANT(T， z， y)           // replace z by its successor y
11      y.left = z.left                 // and give z’s left child to y，
12      y.left.p = y                    // which had no left child

从一棵二叉搜索树中删除结点z。结点z可以是树根，可以是结点q的一个左孩子，也可以是q的一个右孩子。

  • (a)结点z没有左孩子。用其右孩子r来替换z，其中r可以是NIL，也可以不是。
  • (b)结点z有一个左孩子l但没有右孩子。用l来替换z。
  • (c)结点z有两个孩子，其左孩子是结点l， 其右孩子y还是其后继，y的右孩子是结点x。用y替换z，修改使l成为y的左孩子，但保留x仍为y的右孩子。
  • (d)结点z有两个孩子（左孩子l和右孩子r)，并且z的后继y#r位于以r为根的子树中。用y自己的右孩子x来代替y，并且置y为r的双亲。然后，再置y为q的孩子和l的双亲

TREE-DELETE过程处理4种情况如下。

  • 第1~2行处理z没有左孩子的情况。
  • 第3~4行处理z没有右孩子的情况。
  • 第5~12行处理剩下的两种情况，也就是z有两个孩子的情形。
    • 第5行查找结点y，它是z的后继。因为z的右子树非空，这样后继一定是这个子树中具有最小关键字的结点，因此就调用TREE-MINIMUM(z.right)。
      • 如果y位于z的右子树中并且没有左孩子，将y移出它的原来位置进行拼接，并替换树中的z。第10~12行用y替换z并成为z的双亲的一个孩子，用z的左孩子替换y的左孩子。
      • 如果y位于z的右子树中并且不是z的右孩子，第7~9行用y的右孩子替换y并成为y的双亲的一个孩子，然后将z的右孩子转变为y的右孩子，最后第10~12行用y替换z并成为z的双亲的一个孩子，再用z的左孩子替换为y的左孩子。

除了第5行调用TREE-MINIMUM之外，TREE-DELETE的每一行，包括调用TRANSPLANT，都只花费常数时间。因此，在一棵高度为h的树上，TREE-DELETE的运行时间为。

红黑树open in new window

如果搜索树二叉树的高度较低时，这些集合操作会执行得较快。然而，如果树的高度较高时，这些集合操作可能并不比在链表上执行得快。红黑树(red-blacktree)是许多“平衡“搜索树中的一种，可以保证在最坏情况下基本动态集合操作的时间复杂度为。

红黑树的性质

红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。

树中每个结点包含5个属性：color、key、left、right和p。如果一个结点没有子结点或父结点，则该结点相应指针属性的值为NIL。我们可以把这些NIL视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。

一棵红黑树是满足下面红黑性质的二叉搜索树：

    1. 节点是红色或黑色。
    1. 根是黑色。
    1. 所有叶子都是黑色（叶子是NIL节点）。
    1. 每个红色节点必须有两个黑色的子节点。（或者说从每个叶子到根的所有路径上不能有两个连续的红色节点。）（或者说不存在两个相邻的红色节点，相邻指两个节点是父子关系。）（或者说红色节点的父节点和子节点均是黑色的。）
  1. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

为了便于处理红黑树代码中的边界条件，使用一个哨兵来代表NIL。对于一棵红黑树T，哨兵T.nil是一个与树中普通结点有相同属性的对象。它的color属性为BLACK，而其他属性p、left、right和key可以设为任意值。所有指向NIL的指针都用指向哨兵T.nil的指针替换。

使用哨兵后，就可以将结点x的NIL孩子视为一个普通结点，其父结点为x。

某个结点x出发（不含该结点）到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高(black-height)，记为bh(x)。根据性质5，黑高的概念是明确定义的，因为从该结点出发的所有下降到其叶结点的简单路径的黑结点个数都相同。于是定义红黑树的黑高为其根结点的黑高。

引理13.1

  • 一棵有n个内部结点的红黑树的高度至多为
  • 以任一结点x为根的子树中至少包含个内部结点。

由该引理可知，动态集合操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR可在红黑树上在时间内执行，因为这些操作在一棵高度为h的二叉搜索树上的运行时间为，而任何包含n个结点的红黑树又都是高度为的二叉搜索树。

图

图的存储

  • 邻接矩阵
  • 邻接表

拓扑排序

最短路径

关键路径

最小生成树

二分图

最大流

上次编辑于:
贡献者: biezhihua