红黑树算法实现与改进.ppt

红黑树算法的实现和改进，1。红黑树的分析和算法实现，1)红黑树的介绍，2)红黑树插入算法的介绍，3)红黑树搜索算法的介绍，4)红黑树删除算法的介绍，5)红黑树修改算法的介绍，2)红黑树的扩展和变换，1)序列统计树OS2)红黑树索引，1.1红黑树原点，2-3-4树，二叉平衡树，红黑树，1.2红黑树定义节点为红色或黑色，属性2。根为黑色，属性3。所有叶子都是黑色的(叶子是无节)，属性4。每个红色节点的两个子节点是黑色的，属性5。从任何节点到它的每一片叶子的所有简单路径都包含相同数量的黑色节点。红色和黑色本身没有特殊意义。是的，键值决定了节点的颜色。1.3红黑树算法的可行性证明。设置：红黑树的高度是Hrb，红黑树的内部节点(非空节点)的数量是n。有：Hrb=22(N 1) 1证明：假设红黑树的最长路径包含黑色节点的数量，红黑树的黑色高度被设置为：Hb由已知条件决定：从上述结论可以看出，红黑树的最不理想的遍历数量是2log2(N 1) 1，并且算法复杂度是O(log介绍左手和右手，父亲，儿子，弟弟，右手，太阳，儿子，父亲，弟弟，太阳，太阳，太阳，左手，1)红黑树算法是左手和右手操作中最基本的调用函数。2)在下面的演示中，假设树的左分支，默认的新节点是左子节点，右半部分的操作与默认节点对称。1.5插入算法简介，场景1:新节点是根节点，或者父节点是黑色(最初为红色)，直接染成黑色，场景2。新节点的父节点为红色，父节点为黑色，父节点、父节点、父节点、新节点、父节点、直接黑色染父节点，场景3。新节点的父节点为红色，叔叔节点为红色，父亲、叔叔、父亲、新、父亲、父亲、叔叔将父亲和叔叔节点染成黑色，将祖父节点染成红色，继续调整祖父节点。场景4。新节点的父节点为红色，父节点为空。父节点，父节点，父节点，新节点，父节点，父节点，父节点，父节点，父节点，父节点，父节点，父节点，父节点，父节点。继续调整祖父节点并返回到根节点。5，1.7红黑树搜索算法。红黑树是从二进制平衡树派生出来的。其搜索算法在破坏红黑树结构的前提下，遵循二叉平衡树或二叉搜索树的搜索过程。递归，迭代，1.8删除算法分析，删除过程主要分为以下几个场景(这里的替换节点指的是前一个节点B不是A)，1)删除节点不存在，直接返回，2)删除节点存在，替换节点为红色，删除算法思路：找到替换点，覆盖，删除替换节点。例如，假设删除了节点A。1.在节点A的右子树中找到顺序遍历的第一个节点B作为替换节点。2.在不改变a. 3颜色的情况下，将b的键值分配给a。删除节点B4。根据b的具体情况，自底向上调整和删除算法的关键是调整。，9，4，8，AK，BK，用B的键值覆盖A的键值，删除B，BK，BK，1.9删除场景调整续(1)，3.1用黑色兄弟节点和“八字符”红色侄子节点替换节点B，D，C，F，A，1。左侧节点F2。节点C继承了F的颜色，以及被染色的黑色节点F和节点D3的键值。删除到A4。删除B、B、F、C、D、D、bk，1.10删除方案调整续(2)、3.2)将节点B替换为带有黑色兄弟节点和“平行”红色侄子节点的黑色节点，A、F、B、C、D、红色、D、F、B、C、红色、A、bk、1。对节点f，c，d进行“中间顺序旋转”。节点d继承了f的颜色，染成黑色F3。覆盖a，删除b，1.10红黑树删除算法续(3)，3.3)用黑色替换节点b。红色的兄弟节点需要将节点b标记为“双黑”。a、f、b、c、a、c、f、b、1。左手节点C2。节点c继承了f的颜色并染成红色F3。将双黑色“b”的情况与3.1、3.2和3.3进行比较，并继续调整，直到结构调整到3.1或3.2。1.11红黑树删除调整继续(4)，3.4)替换节点b为黑色，带有黑色兄弟节点，侄子节点为空，a、f、b、c、1。染色红色节点c 2。染成黑色的节点F3。键值4覆盖节点a删除节点B，C，F，1.12红黑树删除过程演示，选择一个场景其他类似的，12，6，18，9，10，16，19，20，删除12，找到替换节点16，根据场景3.3处理，上移20，19，16，和“双黑”标记，18，覆盖节点12，删除节点16，16，18，和1.13红黑树修改算法介绍，修改从1.3的结论来看，红黑树的最大树高hh=2xlog (n1) 1是o (logn)，因为所有上述操作都是基于遍历的，所以算法的复杂度是o (logn)，红黑树的2.1扩展，顺序统计树，顺序统计树增加了一个SIZE字段来记录子树的大小。根据大小，我们可以得到树中节点的序列大小，2.2棵红黑树的变换，红黑树的索引，12，18，9，16，19，6，19，12，6，例如：查找键值为4的节点，将值4与索引中的值进行比较，从节点6开始搜索，直到最小值4为6。6，这可以在一定程度上提高搜索速度，3总结和确认，3.1