红黑树插入

红黑树的插入

之前有写过红黑树的一些性质

里面讲了两个旋转,一个是左旋,一个是右旋

左旋:P的右节点代替P的位置,P作为右节点的左节点,P的右节点的左节点作为P的右节点,P的左节点不变(左旋只 操作右侧节点)

右旋:P的左节点F顶替P的位置,F的右节点为P,P的左节点为F原右节点,P原右节点不变(右旋只旋转左侧节点)

红黑树插入过程

红黑树插入主要分:1,寻找红黑树插入位置,2:如果当前位置已经存在,只需要更新值,3:如果找到的位置是插入位置,4:先建一个node,设置parent等信息,把颜色设置成红色(后续调整方便),5:调整红黑树

这里只写调整的情况

假定插入的节点为N,父节点为P,叔叔节点为U,祖父节点为G

情况有分三种:

1、N的叔叔U是红色的

将P和U重绘为黑色并重绘结点G为红色。现在新结点N有 了一个黑色的父结点P,因为通过父结点P或叔父结点U的任何路径都必定通过祖父结点G, 在这些路径上的黑结点数目没有改变。但是,红色的祖父结点G的父结点也有可能是红色 的,这就违反了性质3。为了解决这个问题,我们在祖父结点G递归向上调整颜色,如图:

2、N的叔叔U是黑色的,且N是左孩子

对祖父结点G 的一次右旋转; 在旋转产生的树中,以前的父结点P现在是新结点N和以前的祖父节点 G 的父结点,然后交换以前的父结点P和祖父结点G的颜色,结果仍满足红黑树性质。如下图所示。在(b)中,虚线代表原来的指针,实线代表旋转过后的指针。所谓旋转就是改变图中所示的两个指针的值即可。当然,在实际应用中,还有父指针p也需要修改,这里为了图示的简洁而省略掉了

3、N的叔叔U是黑色的,且N是右孩子

我们对P进行一次左旋转调换新结点和其父 结点的角色,就把问题转化成了第二种情况。如下图所示

范例

插入(1,2,3,4,5,6,7,8,9,10)

参考

https://zhuanlan.zhihu.com/p/25358857?refer=hinus

打赏

扫一扫,分享到微信

微信分享二维码

请我喝杯咖啡吧~

支付宝
微信