数据结构课件-4-红黑树.pptx

数据结构计算机领域本科教育教学改革试点工作计划（“101计划”）研究成果俞勇、张铭、陈越、韩文弢上海交通大学、北京大学、浙江大学、清华大学101

12.4红黑树第12章高级查找戴波电子科技大学

12.4.1红黑树的定义12.4.2红黑树的旋转12.4.3红黑树的插入12.4.4红黑树的删除12.4.5红黑树的应用12.4.6红黑树的小结12.4.7红黑树的作业

12.4.1红黑树的定义12.4.1红黑树的定义数据结构红黑树是满足下列性质的二叉查找树：每个结点或者为黑色，或者为红色根结点为黑色每个空结点（NULL结点）都是黑色如果有一个结点是红色，那么他的2个孩子结点都是黑色（不能有2个相邻的红色结点）对于每一个结点，从该结点到其子孙的叶子结点的路径中所包含的黑色结点数量必须相等。从红黑树任意结点x出发，到达叶子结点的任意路径上（不包含x)的黑色结点个数称为x结点的黑高度，记为bh(x)，规定叶子结点高度为1，黑高度为1。红黑树的黑高度定义为根结点的黑高度。

12.4.1红黑树的定义12.4.1红黑树的定义数据结构着色性质二叉查找树中每个结点着色为红黑两色中的一种颜色；根结点为黑色；任一红结点的孩子只能为黑色。黑高度相等性质每个结点x到其所有子孙叶结点的路径中所包含的黑结点个数（不包含结点x）必须相等，并称该个数为结点x的黑高度，记为bh(x)，规定空结点的黑高度为0，则叶子结点的黑高度是1，根结点的黑高度为红黑树的黑高度。红黑树是一颗自平衡二叉查找树，在插入删除操作时通过特定操作保持二叉树的平衡，从而获得较高的查找性能。最坏O(logn)时间内完成查找，插入和删除。

写出该红黑树的每个结点的黑高度作答主观题10分

12.4.1红黑树的定义12.4.1红黑树的定义数据结构1121111122写出该红黑树的每个结点的黑高度解答：

图1红黑树左旋图2红黑树右旋12.4.2红黑树的旋转12.4.2红黑树的旋转数据结构1.旋转不会影响旋转结点的父结点，父结点以上结点结构保持不变2.旋转不考虑颜色！2.旋转是局部的，目的是当一边子树的结点少了，那么向另外一边子树“借入”一些结点；当一边子树的结点多了，那么向另外一边子树“出租”一些结点。

12.4.3红黑树的插入12.4.3红黑树的插入数据结构提问：红黑树进行插入操作，第一步是满足二叉查找树的性质，插入之后，怎么判断是否需要进行旋转？如何通过更改颜色（着色）使其仍然满足红黑树的定义？以这棵树为例子，分别插入4，14，92，5，77,插入后的红黑树是怎样的？

12.4.3红黑树的插入12.4.3红黑树的插入数据结构提问：红黑树插入操作的时候，插入位置已经找到，把插入结点放到正确的位置就可以啦，请问插入结点是应该是什么颜色呢？为什么？答案：插入红色结点。因为红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。注意：插入位置始终是叶子结点（查找失败的位置）

12.4.3红黑树的插入12.4.3红黑树的插入数据结构提问：请观察红黑树的红结点多还是黑结点多？最坏情况是怎样的？因此插入红结点除了因为父结点是黑色不用调整，还有什么优点？答案：通常黑结点多。最坏情况是根结点黑色，然后每一个结点的一个分支全部是黑结点，一个分支是一层红结点，一层黑结点，使得黑高度相同，但高度差1倍。因为大部分情况下黑结点多，插入红结点不用调整，使得插入操作比AVL树减少大量旋转，功能更优。

12.4.3红黑树的插入12.4.3红黑树的插入数据结构提问：红黑树的插入有几种情况？如何处理？

12.4.3红黑树的插入12.4.3红黑树的插入数据结构提问：红黑树的插入有几种情况？如何处理？

12.4.3红黑树的插入12.4.3红黑树的插入数据结构Insert(tree,key,value)输入：红黑树tree，键key，值value输出：无ifIsEmpty(tree)then//红黑树为空tree.root←RBNode(key,value,BLACK)returnendt←key在tree中的目标插入位置p←key在tree中的目标插入位置的父结点ift≠NILthen//key已存在t.value←valueelse//key不存在t←RBNode(key,value,RED,p)ift.p.color=REDthen//插入结点的父结点为红色Ins