红黑树详解

格式：pdf
大小：1.19 MB
文档页数：17

下载文档原格式

/ 17

红黑树详解

红黑树详解在本文，我将比较透彻地讲解红黑树。

本文适合那些有对二叉树有一定的基础，并且熟悉C语言的读者。

本文最主要的参考资料是《Introduction to Algorithms 3rd Edition》。

1.1 二叉查找树1.1.1 基本概念二叉查找树是在数据结构中比较重要的数据结构之一，从外部看它满足集合性质，具有查找，插入和删除的基本功能，同时还可以求最大值和最小值。

由于二叉查找树独特的性质，它特别适合用来存储动态集合。

定义：对于二叉树上的所有结点x，如果y是x的左子树，那么y.key ≤ x.key。

如果y 是x的右子树，那么y.key ≥ x.key，这样的二叉树就称为二叉查找树(Binary Search Tree)。

我们关心的二叉查找树的逻辑结构，下面的两棵二叉树：图1 二叉查找树。

(a)这一棵高度为3的二叉树，因为10比15小，所以10在15的左子树上；同理在以10为根的左子树里，7比10小所以7在左子树上，12在10为根的子树的右子树上；20在以15为根的右子树上。

(b)这是一棵高度是4的二叉查找树，它的所有key与图(a)是一样的。

在图(a)中，查找最坏的情况是7和12，它们需要经过3次比较才能找到，而图(b)最坏情况是20，需要经过4次比较才能找到。

要想二叉树的查找的花费时间小，我们尽可能让二叉树不出现类以于单链形态的二叉树，让树的高度尽量的低。

对于高度为h的二叉查找树，从树根对叶子最坏的情况是比较h 次。

也就是说，对于高度为h的二叉查找树的最坏查找情况的运行时间是O(h)。

二叉树的查找效率取决于树的高度。

1.1.2 操作二叉树做为动态集，它有查找、插入、删除、最大值、最小值、前驱和后继这些基本操作。

为了后序的方便，我们定义了结点和树，另外我们还用0表示空子树。

查找在二叉查找树中根据给定的key找到该结点。

由于二叉树的性质，我们就知道，如果目标key比当前结点的key要小，那么目标结点必定在当前结点的左子树上。

c++map的底层实现原理

c++map的底层实现原理
C++ STL中的map是通过红黑树实现的，红黑树是一种自平衡的二叉查找树，它的插入、删除、查找操作都能在对数时间复杂度内完成，可以保证较稳定的性能。

具体来说，map内部是用一颗红黑树（Red-Black Tree）实现的。

红黑树是一种对平衡性要求比较低的二叉查找树（Binary Search Tree），在红黑树上进行查找、插入、删除等操作的时间复杂度都是log(N)。

红黑树的特点是每个节点要么是红色，要么是黑色，并且满足以下规则：
1、根节点是黑色的；
2、每个叶子节点都是黑色的空节点（NIL节点）；
3、如果一个节点是红色的，则它的子节点必须是黑色的；
4、从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点；
由于map底层采用红黑树实现，因此它具有以下特点：
1、自动排序；
2、查找、插入、删除操作的时间复杂度都是O(logN)，极端情况下会退化成链表；
3、可以支持迭代器操作，比如反向迭代；
4、支持按照自定义规则排序；
综上所述，map的底层实现原理是通过红黑树实现的，红黑树是一种自平衡的二叉查找树，能够保证较稳定的性能。

红黑树面试题

红黑树面试题红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它能够保持在插入、删除等操作之后仍保持平衡。

在面试中，红黑树是常见的面试题目之一。

本文将通过解答一些常见的红黑树面试题来帮助读者更好地理解红黑树的性质和操作。

1. 什么是红黑树？红黑树是一种自平衡的二叉搜索树，它的每个节点都有一个额外的存储位来表示节点的颜色，可以是红色或黑色。

它满足以下性质：(1) 每个节点要么是红色，要么是黑色。

(2) 根节点是黑色。

(3) 每个叶子节点（NIL节点，空节点）是黑色。

(4) 如果一个节点是红色的，则它的两个子节点都是黑色的。

(5) 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

2. 如何实现红黑树的插入操作？红黑树的插入操作可以分为以下几个步骤：(1) 将节点插入到二叉搜索树中，按照二叉搜索树的规则找到合适的位置。

(2) 将插入的节点标记为红色。

(3) 根据红黑树的性质，调整树的结构来满足红黑树的要求，确保不会出现连续的红色节点。

具体的调整操作分为几种情况，我们以插入节点为A为例进行说明：(1) A是根节点，将A标记为黑色。

(2) A的父节点是黑色，不需要进行调整。

(3) A的父节点是红色：a. A的叔节点是红色：将A的父节点和叔节点都标记为黑色，将A的祖父节点标记为红色，然后以祖父节点为当前节点进行进一步的调整。

b. A的叔节点是黑色或不存在，且A是其父节点的右子节点：以A的父节点为支点进行左旋转，然后再以A的父节点为当前节点进行进一步的调整。

c. A的叔节点是黑色或不存在，且A是其父节点的左子节点：将A的父节点标记为黑色，将A的祖父节点标记为红色，以A的祖父节点为支点进行右旋转，最后整个树都符合红黑树的要求。

3. 如何实现红黑树的删除操作？红黑树的删除操作相对于插入操作要复杂一些。

删除操作可以分为以下几个步骤：(1) 根据删除节点的值，在红黑树中找到要删除的节点。

(2) 根据要删除的节点的情况进行不同的处理：a. 要删除的节点没有子节点或只有一个子节点：直接删除该节点，并将其子节点接替上来。

红黑树的特点范文

红黑树的特点范文红黑树是一种自平衡的二叉树，它具有以下特点：1.二叉树属性：红黑树满足二叉树的基本性质，即对于树中的每个节点，其左子树的所有节点的值都小于该节点的值，而右子树的所有节点的值都大于该节点的值。

2.红黑性质1：每个节点要么是红色，要么是黑色。

3.红黑性质2：根节点是黑色的。

4.红黑性质3：每个叶子节点（NIL节点，空节点）是黑色的。

5.红黑性质4：如果一个节点是红色的，那么它的两个子节点都是黑色的。

6.红黑性质5：对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点。

7.黑高度相等：从根节点到任意叶子节点的路径上的黑色节点数量必须相同，这个数量成为黑高度。

红黑树之所以被称为“红黑树”，是因为它的节点可以被标记为红色或黑色，并且通过这些颜色的约束规则实现了平衡性。

1. 自平衡性：通过红黑性质的约束规则，红黑树能够自动平衡，保持树的高度相对较低，从而能够提供较快的、插入和删除操作的平均时间复杂度为O(log n)，保证了树的高效性能。

2.结构简单：红黑树的基本特点较为简单，只有5个约束规则，相较于AVL树等平衡二叉树，实现和维护的复杂度较低。

3.有序性：红黑树是一个有序树，即树中的节点按照特定的顺序排列。

这使得红黑树非常适用于需要有序数据的场景，例如字典、索引等。

4. 广泛应用：红黑树被广泛应用于各种数据结构和算法中，如集合、映射、区间树、数据库索引等。

在C++的STL库中，map和set容器的实现就是基于红黑树。

红黑树的缺点：1.相对复杂：相较于其他二叉树，红黑树的实现和维护较为复杂，因为需要遵循红黑性质。

这增加了代码的复杂度和难度。

2. 插入和删除操作相对慢：虽然红黑树的平均情况下插入和删除的时间复杂度为O(log n)，但相较于普通二叉树，红黑树在实际性能上略慢一些。

总结：红黑树是一种自平衡的二叉树，通过红黑性质的约束规则，保持树的平衡性和有序性。

它具有较高的查询、插入和删除效率，并且广泛应用于各种数据结构和算法中。

红黑树优点和应用场景

红黑树优点和应用场景红黑树优点及应用场景红黑树是一种自平衡二叉查找树，具有优秀的平均性能和较稳定的最坏情况性能。

它的优点包括高效的查找、插入和删除操作，以及平衡性能好，不易退化成链表等。

本文将详细介绍红黑树的优点及其应用场景。

一、红黑树优点1.高效的查找、插入和删除操作红黑树的查找、插入和删除操作时间复杂度均为O(log n)，其中n 为树中节点数。

由于红黑树的平衡性，它的查找性能非常高，并且插入和删除操作也能够保持比较稳定的性能。

这使得红黑树在实际应用中非常受欢迎。

2.平衡性能好，不易退化成链表红黑树是一种自平衡二叉查找树，它通过保持节点的颜色、旋转等方式来保持树的平衡性。

这使得红黑树不易退化成链表，从而保证了它的查找、插入和删除操作的时间复杂度稳定。

3.易于实现和理解红黑树的实现相对简单，且易于理解。

它的平衡性质也使得它的实现相对稳定，不易出现错误。

这使得红黑树在实际应用中非常受欢迎，尤其是对于那些需要高效查找、插入和删除操作的应用场景。

二、红黑树应用场景1.数据库索引数据库索引是一种常见的应用场景，它通过建立一棵树来实现对数据的快速查找。

在这种情况下，红黑树是一种非常合适的数据结构，因为它能够提供高效的查找、插入和删除操作，并且能够保持较好的平衡性。

2.操作系统调度操作系统调度是一种需要高效查找和插入操作的应用场景。

在这种情况下，红黑树可以用来实现进程优先级的管理，从而保证高优先级进程的优先执行。

3.路由表路由表是一种需要高效查找和插入操作的应用场景。

在这种情况下，红黑树可以用来实现路由表的管理，从而保证路由的高效查找和更新操作。

4.编译器实现编译器是一种需要高效查找和插入操作的应用场景。

在这种情况下，红黑树可以用来实现符号表的管理，从而保证编译器的高效性能。

红黑树是一种非常优秀的数据结构，它具有高效的查找、插入和删除操作，以及平衡性能好，不易退化成链表等优点。

它在数据库索引、操作系统调度、路由表和编译器实现等应用场景中都有广泛的应用。

红黑树的定义和节点结构

红黑树的定义和节点结构红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。

红黑树具有如下性质：1. 每个节点要么是红色，要么是黑色。

2. 根节点是黑色。

3. 每个叶子节点（NIL节点，空节点）是黑色。

4. 如果一个节点是红色的，则它的两个子节点都是黑色的。

5. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

红黑树的节点结构通常包含以下几个字段：1. 键值（Key）：存储节点的关键字，用于进行搜索和比较。

2. 数据（Value）：存储节点关联的数据。

3. 左子节点（Left）：指向该节点的左子节点。

4. 右子节点（Right）：指向该节点的右子节点。

5. 父节点（Parent）：指向该节点的父节点。

6. 颜色（Color）：表示节点的颜色，通常用布尔值或枚举类型表示。

红黑树的定义和节点结构相互依赖，通过节点间的关系和颜色属性，实现了树的自平衡。

下面将详细介绍红黑树的定义和节点结构。

红黑树的定义是基于二叉搜索树的基础上进行的。

二叉搜索树是一种有序的二叉树，对于任意节点，其左子节点的键值小于该节点的键值，而右子节点的键值大于该节点的键值。

这个性质使得在二叉搜索树上进行搜索、插入和删除等操作非常高效。

然而，如果只使用二叉搜索树，可能会出现树的不平衡情况，导致某些操作的时间复杂度变高。

为了解决这个问题，红黑树引入了节点的颜色属性，并通过一些特定的规则来保持树的平衡。

红黑树的节点结构包含了键值、数据和指向子节点的指针。

其中，键值用于进行搜索和比较，数据存储了节点关联的信息。

左子节点和右子节点分别指向该节点的左右子树，父节点指向该节点的父节点。

通过这些指针，可以在树中进行节点的插入、删除和查找等操作。

红黑树的节点还包含了颜色属性，用于表示节点的颜色。

颜色通常用布尔值或枚举类型表示，红色用true或RED表示，黑色用false 或BLACK表示。

面试题——轻松搞定面试中的红黑树问题

没有学习过红⿊树的同学请参考：<<Introduction to Algorithms>> Chapter 13 Red-Black Trees Chapter 14 Augmenting Data Structures1.stl中的set底层⽤的什么数据结构？2.红⿊树的数据结构怎么定义的？3.红⿊树有哪些性质？4.红⿊树的各种操作的时间复杂度是多少？5.红⿊树相⽐于BST和AVL树有什么优点？6.红⿊树相对于哈希表，在选择使⽤的时候有什么依据？7.如何扩展红⿊树来获得⽐某个结点⼩的元素有多少个？8.扩展数据结构有什么步骤？9 为什么⼀般hashtable的桶数会取⼀个素数详细解答1.stl中的set底层⽤的什么数据结构？红⿊树2.红⿊树的数据结构怎么定义？[cpp]1. enum Color2. {3. RED = 0,4. BLACK = 15. };6.7. struct RBTreeNode8. {9. struct RBTreeNode*left, *right, *parent;10. int key;11. int data;12. Color color;13. };3.红⿊树有哪些性质？⼀般的，红⿊树，满⾜以下性质，即只有满⾜以下全部性质的树，我们才称之为红⿊树：1）每个结点要么是红的，要么是⿊的。

2）根结点是⿊的。

3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是⿊的。

4）如果⼀个结点是红的，那么它的俩个⼉⼦都是⿊的。

5）对于任⼀结点⽽⾔，其到叶结点树尾端NIL指针的每⼀条路径都包含相同数⽬的⿊结点。

4.红⿊树的各种操作的时间复杂度是多少？能保证在最坏情况下，基本的动态⼏何操作的时间均为O（lgn）5.红⿊树相⽐于BST和AVL树有什么优点？红⿊树是牺牲了严格的⾼度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从⽽提⾼了性能。

treeset排序原理

treeset排序原理
TreeSet是一种基于红黑树的Set集合，它可以自动进行元素排序。

TreeSet的排序原理是通过对元素进行比较，将它们按照特定的顺序排列。

在创建TreeSet时，可以传入一个Comparator对象，它可以定义元素的比较规则。

如果没有传入Comparator，则元素必须实现Comparable接口，该接口中定义了一个compareTo()方法，该方法用于定义元素的自然顺序。

TreeSet使用红黑树的数据结构来存储元素。

红黑树是一种自平衡的二叉搜索树，它具有以下特点：
1. 每个节点都是红色或黑色。

2. 根节点是黑色的。

3. 每个叶子节点（NIL节点）都是黑色的。

4. 如果一个节点是红色的，则它的子节点必须是黑色的。

5. 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

由于红黑树是自平衡的，因此在插入和删除元素时，它会自动调整树的结构，以保持树的平衡。

这样可以确保元素的插入和删除操作的时间复杂度都是O(log n)，其中n为树中元素的个数。

另外，由于TreeSet是一个Set集合，因此它不允许包含重复的元素。

如果试图将重复元素插入TreeSet中，它会被忽略。

总之，通过使用红黑树作为数据结构和元素比较规则，TreeSet
可以自动对元素进行排序，并且具有高效的插入和删除操作。

hashmap红黑树退化条件

hashmap红黑树退化条件
hashmap的实现中，使用了红黑树来优化hash冲突引起的链表退化问题，但红黑树也有可能会退化，那么什么条件下红黑树会发生退化呢？
1. 大量重复的key：当hashmap中存在大量重复的key时，会导致红黑树退化成链表。

因为红黑树的时间复杂度是O(logn)，而链表的时间复杂度是O(n)，所以红黑树退化成链表后，性能会大幅下降。

2. key的hashCode相同：hashmap使用hashCode来计算key在数组中的位置，如果存储的key的hashCode相同，会导致红黑树的插入、查找等操作退化成链表操作。

因为此时，红黑树的左右子树都为空，相当于链表。

3. 扩容导致的rehash：当hashmap扩容时，会导致所有的key 重新计算hash值，如果新的hash值相同，会导致红黑树退化成链表。

因此，为了避免这种情况，可以使用自定义的hashCode方法，使得每个key的hashCode都不相同，从而避免rehash引起的退化。

总之，红黑树退化成链表是一种很严重的问题，会影响hashmap 的性能。

因此，在实际开发中，需要注意避免上述情况的发生。

- 1 -。

红黑树的时间复杂度

红黑树的时间复杂度红黑树（Red-Black Tree）是一种自平衡的二叉查找树，通过保持树的黑高（从根节点到任意叶节点的黑色节点个数）相等，来确保树的高度始终保持在O(log n)的级别。

红黑树的时间复杂度在插入、删除和查找操作中都能够保持较好的性能。

一、插入操作在红黑树中插入节点的过程中，我们需要涉及到一些调整，以保持树的平衡。

这主要包括旋转操作和颜色调整。

1.1 旋转操作旋转操作是红黑树中的核心操作之一，用于维持树的平衡。

在插入节点时，如果出现了某些情况，比如连续的红色节点或者违反了树的性质，就需要进行旋转操作。

左旋操作和右旋操作分别通过改变节点指针的指向来实现。

左旋操作将一个节点的右子节点提升为其父节点，同时原来的父节点成为新的左子节点。

右旋操作则是左旋操作的镜像操作。

1.2 颜色调整在插入节点后，可能会违反红黑树性质的第三条和第四条。

第三条要求红黑树的每个红色节点的两个子节点都是黑色，而第四条则要求从任意节点到其每个叶子的路径上包含相同数目的黑色节点。

为了恢复平衡，我们会进行一系列的颜色调整操作。

这包括变换节点颜色、变换父子节点的颜色以及进行旋转操作。

综上，红黑树的插入操作的时间复杂度为O(log n)。

二、删除操作红黑树的删除操作相对于插入操作稍微复杂一些。

同样也需要进行旋转操作和颜色调整。

2.1 旋转操作删除节点后，为了保持树的平衡，我们可能需要进行多次旋转操作，使树保持平衡。

2.2 颜色调整删除节点后可能会导致红黑树的性质被破坏，我们需要进行颜色调整以恢复性质。

删除操作的时间复杂度也是O(log n)。

三、查找操作红黑树的查找操作与二叉查找树相同，通过比较节点的值进行搜索。

由于红黑树始终保持平衡，查找操作的时间复杂度为O(log n)。

综上，红黑树的插入、删除和查找操作的时间复杂度均为O(log n)，其中n为红黑树的节点个数。

红黑树的时间复杂度保持在一个较低的级别，使其在各种应用场景中都能够提供高效的性能。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

n 40 41 ... 4 h 1 40
1 4h 4h 1 1 4 3 （公式 1）
对于高度为 h 并且所有的 “叶子” 结点的高度都是相等的 234 树最少有多少个结点呢？要想结点最少，那么它就退化出了满二叉树了。所以，树的结点个数 n 满足：
n 20 21 ... 2 h 1 20
下面我具体针对这 3 种情形进行分解。情形 1，z 没有右孩子，我们只要将左孩子替换 z 在树中位置就能完成删除操作，其实我们拿 z 的前驱替换也是可以的；情形 2，z 有右孩子，所以我们找到 z 的后继替换 z。因为 z 的 key 小于右子树所有的 key（假设没有重复的 key），那么 z 的后继就是右子树上的最小 key。如图 5 的中 b 和 c，z 的后继可能是 z 的右孩子（当右孩子没有左孩子就会出现该情况），那么调用 transplant(T,z,y)。另外，要连接上原来 z 的左子树； z 的后继也有可能不是 z 的右孩子（图 c 所示的情况），首先我们调用 transplant(T,y,y->r)，这时候 y 已经从树中脱离了，然后我们将 y 嫁接到 z 的右孩子的双亲上，这样 y 就成了 z 右孩子的双亲了，这和情形 b 是同一种情况了。下面是删除的代码：
图 6 红黑树的表示。key 为 64 的结点的黑高度为 3，key 为 26，81，14，44 的结点黑高度为 2，key 为 5，19，30，76，92 的结点黑高度为 1。
证明：我们将红色结点吸附到黑色的双亲结点上，那么一个黑色结点最多可以吸附 2 个结点，并且可以有 4 个孩子，那么就形成了一个大结点，如图 7 所示。这样树我称之为 234 树。红黑树的数学本质就是 234 树，并且所有的“叶子”结点的高度都是相等的。不难看出，黑高度就是这棵 234 树的高度。
对于某个结点 y 它的后继的位置是：如果 y 的右子树存在，那么后继是 y 的右子树中的 key 最小的结点；如果 y 的右子树不存在，那么我们只要找到哪个结点的前驱是 y，那么那个结点就是 y 的后继(图 2 中的 d)。
根据前驱和后继的定义，我们知道通过对树中最小值一直沿着后继直到结束，这样的序列就是中序遍历的序列。下面给出中序遍历的代码：
说运行时间为 O(lg n)。可以说它的效率是极高的。
1.2.1 基本概念
如果我把二叉查找树的每个结点都涂上红色或者黑色。如果它满足下面的 5 个性质，那么我们就称它为红黑树（Red Black Tree）： 1．每个结点不是红色就是黑色。 2．根结点是黑色的。 3．每个叶子结点（NIL）都是黑色的。 4．如果一个结点是红色的，那么它所有的孩子都是黑色的。 5．对于每一个结点，从当前结点到后代的叶子的路径上包含黑色结点的数量是相同的。根据红黑树的性质，我们可得出下面的结论：具有 n 内部结点的红黑树的高度最高为 2lg(n+1)。在证明这个结论之前，我们来看看红黑树的表示。每个结点到叶子结点（NIL）经过的黑色结点的个数（包括自已）称之为黑高度(black-height)。我们把 NIL 称之为外部结点，那些带有 key 的“合法”的结点称之为内部结点。
图 7 将图 6 中的红色结点吸附到双亲结点上，这样对应数学结构为 234 树。
对于高度为 h 并且所有的 “叶子” 结点的高度都是相等的 234 树最多有多少个结点呢？要想结点最多，并且所有的“叶子”结点的相同。那么它就是一棵满 234 树，每个结点的出度 4，每个结点包含 3 个内部结点，那么对于高度为 h 的 234 树，则树的结点个数 n，满足：
红黑树详解
在本文，我将比较透彻地讲解红黑树。本文适合那些有对二叉树有一定的基础，并且熟悉 C 语言的读者。本文最主要的参考资料是《Introduction to Algorithms 3rd Edition》。
1.1 二叉查找树 1.1.1 基本概念
二叉查找树是在数据结构中比较重要的数据结构之一，从外部看它满足集合性质，具有查找，插入和删除的基本功能，同时还可以求最大值和最小值。由于二叉查找树独特的性质，它特别适合用来存储动态集合。定义：对于二叉树上的所有结点 x，如果 y 是 x 的左子树，那么 y.key ≤ x.key。如果 y 是 x 的右子树，那么 y.key ≥ x.key，这样的二叉树就称为二叉查找树(Binary Search Tree)。我们关心的二叉查找树的逻辑结构，下面的两棵二叉树：
1.1.3 实现
参考附件：bstree.c。
1.1.4 思考题
1.Bunyan 教授认为他发现了二叉查找树的一个重要的性质。假设在二叉查找树上查找 key 为 k 的结点,并且 key 为 k 的结点是一个叶子结点。那么有三个集合：A，搜索路径的左边结点的集合；B，搜索路径上的结点的集合；C 是搜索路径右边的结点集合。Buyan 教授认为对于三个集合的任意值 a∈A，b∈B，c∈C 一定满足 a≤b≤c。对于上面的观点，请给出最小可能一个的反例。 2.证明：在高度为 h 的二叉查找树上，我们实现的动态集基本操作:min，max，successor， predecessor，search，insert 和 delete 的运行时间都是 O(h)。 3.在二叉查找树的删除操作中，假设我们不取 z 的后继而取 z 的前驱替换 z，请相应对称的代码。
ห้องสมุดไป่ตู้
插入对二叉查找树的插入，不能破坏二叉查找树的性质，那么我们要结点插入到什么地方呢？答案是叶子，新插入的结点，都是将成为某个叶子结点的左孩子或者右孩子。
图 3 二叉查找树的插入。图中 key 为 11 的结点插入到树中，其中浅色结点表示插入时候比较的路径。虚线表示插入的位置。
我们发现 insert 与 search 方法是一样的，只不过 search 是查找特定的 key，而 insert 是查找合适的叶子结点的位置，它的运行时间为 O(n)。删除在介绍删除二叉查找算法之前，我们先来介绍一个辅助函数 transplant，这个函数有 3 个参数，在树 T 中，将 v 替换 u 的位置，即 u 的双亲变成 v 的双亲，v 替换 u 成为 u 双亲的孩子。另外一个辅助函数 replace ，这个函数有 3 个参数，在树 T 中，将 v 完全代替 u，即 u 的双亲变成 v 的双亲，v 替换 u 成为 u 双亲的孩子，另外左右孩子均为 u 的孩子。
要想二叉树的查找的花费时间小，我们尽可能让二叉树不出现类以于单链形态的二叉树，让树的高度尽量的低。对于高度为 h 的二叉查找树，从树根对叶子最坏的情况是比较 h 次。也就是说，对于高度为 h 的二叉查找树的最坏查找情况的运行时间是 O(h)。二叉树的查找效率取决于树的高度。
1.1.2 操作
二叉树做为动态集，它有查找、插入、删除、最大值、最小值、前驱和后继这些基本操作。为了后序的方便，我们定义了结点和树，另外我们还用 0 表示空子树。
图 1 二叉查找树。(a)这一棵高度为 3 的二叉树，因为 10 比 15 小，所以 10 在 15 的左子树上；同理在以 10 为根的左子树里，7 比 10 小所以 7 在左子树上，12 在 10 为根的子树的右子树上；20 在以 15 为根的右子树上。(b)这是一棵高度是 4 的二叉查找树，它的所有 key 与图(a)是一样的。在图(a)中，查找最坏的情况是 7 和 12，它们需要经过 3 次比较才能找到，而图(b)最坏情况是 20，需要经过 4 次比较才能找到。
图 4 演示了 transplant 中 v 在树中替换 u 的过程。如果 u 是根，即 v.p==0 时，T 的树根就改变了。
我们来考查一下待删除的结点是 z。那么 z 可能有几种情况： z 没有右孩子； z 有右孩子：z 的右孩子有左孩子，z 的右孩子没有左孩子。
图 5 二叉树删除的三种情形。图中 z（浅色的）为待删除的结点。(a)没有右孩子的删除，将 z 的左孩子替换 z 即可，z 的左孩子有可能是 NIL 指针。(b)z 的右孩子不为空,y 是 z 的后继，但右孩子的左孩子为空，我们知道 z 的右孩子就是 z 的继，所以用 z 的右孩子替换 z 即可。(c)z 的后继 y 不是 z 的右孩子，y 的右孩子替换 y，从树中移出 y，将 y 作为 z 右孩子的双亲连接上，此时情形成了情形 b 了。
图 2 结点的后继和前驱。(a)y 是 x 的后继，因为 y 没有左子树，所以 y 是 x 右子树上 key 最小的结点。(b)y 是 x 的后继，因为 x 的左子不为空，所以 y 是 x 左子树中最左那个小那个，所以 y 是 x 的后继。(c)x 是 y 的前驱，因为 y 没有左子树，所以 y 是 x 左子树上 key 最大的那个结点。(d)y 是 x 的前驱，因为 x 有左子树，所以 x 左子树上 key 最大的在 x 左子树上最右的那个结点。也有可能是 z 右孩子的最左的那个子孙结点(图 b 所示)。如果 y 是的后继，那么 y 就是 x 的前驱。
h
1 2h 2 h 1 （公式 2） 1 2
由公式 2 得出：n 2 1 两边取对数 lg(n 1) h 即 h lg(n 1) 。这里的 h 是 234 树的高度，由前面所述，红黑数的黑高度就是对应 234 树的高度。对于黑高度了 h，由性质 2、 3、4 得出红色结点不可能多于黑色结点。所以结点个数不大于黑高度的 2 倍。所以具有 n 内部结点的红黑树的高度最高为 2lg(n+1)，证毕。我们证明的结论说明红黑树的搜索运行时间为 O(2lg(n+1))也就是 O(lg n)。为了方便操作，我们引入一个 NIL 结点，这个 NIL 结点是跟普通的结点一样，不过我们只使用 color 这个域，因为 NIL 结点是黑色的。
查找在二叉查找树中根据给定的 key 找到该结点。由于二叉树的性质，我们就知道，如果目标 key 比当前结点的 key 要小，那么目标结点必定在当前结点的左子树上。

红黑树详解

合集下载