首页 > 代码库 > 红黑树插入详解
红黑树插入详解
查找二叉树插入节点:
已知查找二叉树的性质为根节点的值大于左子树的值,小于右子树的值,按照此规律,根据要插入的值为其寻找合适的插入位置,最后将其插入即可:
Tree-Insert(T,z) { x = root(T); y = NULL; while(x != NULL) { y = x; if(key[z] < key[x]) x = left[x]; else x = right[x]; } p[z] = y; if(y == NULL) root[T] = z; else if(key[z] < key[y]) left[y] = z; else right[y] = z; }
红黑树插入节点:
红黑树插入节点类似于查找二叉树,但需要注意的是当新的节点插入红黑树时,可能会导致无法保持红黑树的性质,因此需对其进行修改。
通过函数RB-INSERT-FIXUP(T,z)使其保持红黑性质。
RB-Insert(T,z) { x = root(T); y = nil[T]; while(x != nil[T]) { y = x; if(key[z] < key[x]) x = left[x]; else x = right[x]; } p[z] = y; if(y == nil[T]) root[T] = z; else if(key[z] < key[y]) left[y] = z; else right[y] = z; left[z] = nil[T]; right[z] = nil[T]; color[z] = RED; RB-INSERT-FIXUP(T,z); }
不同于之前查找二叉树的插入,红黑二叉树的插入过程中主要在最后几步与其有异:将插入节点的颜色置红,修补红黑树性质。
接下来分析,当新的节点插入时,打破了红黑树的哪些性质。
红黑树的性质为:
1. 每个节点或是红的,或是黑的。
2. 根节点是黑的
3. 叶节点是黑的
4. 如果一个节点是红的,则其两个儿子都是黑的
5. 对每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑节点
易知新节点的插入不会影响性质1、3、5
现在的问题为如何保持性质2和4。
当z插入红黑树时,考虑z的父节点,当父节点为黑色时,性质2和4仍能保持,因此现考虑while(color[p[z]] == RED)时,如何保持性质2和4。
插入z后有两种情况:z == left[p[z]]或z == right[p[z]]。这里首先考虑z == left[p[z]]。
已知color[p[z]] == RED ,则由红黑树性质4知,color[p[p[z]]]必为黑色。因为若p[z]的父节点为红色,则p[z]需为黑色,矛盾。而z的叔叔(设为y)颜色即可能是红色,也可能是黑色。若y为红色,为保持性质4,应将p[z]、y均设为黑色,p[p[z]]设为红色。之后让z = p[p[z]],继续循环;若y为黑色,此时z有可能是p[z]的左子树或右子树。当z为右子树时,可执行以下步骤:z = p[z];LEFT-ROTATE(T,z),可将其转变为z为左子树的情况。此时右旋p[z],则p[p[z]]变成了p[z]的右子树,z仍为p的左子树。为保持红黑树性质,将p[z]置黑,p[z]的右子树置红。
最后,color[p[z]] != RED时,为保证性质2,color[root[T]] = BLACK;
红黑树插入详解