可能性1:若P是黑色的 :不需要做任何事情,由于插入的节点总是红色的。若父节点是黑色的,则 没有红色节点连接红色节点冲突也不会增加黑色节点数目,所以此时插入不需要做任何事情。
可能性2:P是红色,X是G的一个外侧子孙节点:这是插入后需要一次旋转和一些颜色变化,此时我们可以创建一个根为50的树,然后插入25,75和12。在插入12之前需要做一次颜色变换,然后向该树中插入6,得到下图中的a树,此时违背了红黑树规则,需要进行一下三个步骤的变换,
改变X的祖父节点G的颜色。
改变X父节点P的颜色。
以X的祖父节点G为顶旋转,方向为X的上升方向,变换后的树如下图中的b,再次成为一棵红黑树
可能性3:P是红色的X是G的一个内侧的子孙节点,这时需要做两次旋转和一些颜色改变,首先我们创建一颗节点为50,25,75,12,18的树(在插入节点12之前需要一次颜色变换)插入12后的树如下图a所示,插入节点18是一个内侧子孙节点,他和他的父节点都是红色,首先第一次旋转将子孙节点变为外侧子孙节点,下图中的b->c然后就可以利用同情况1相同的旋转,颜色转换和旋转的步骤如下:
改变X的祖父节点25的颜色
改变X节点18的颜色
用X的父节点P作为顶旋转,方向为X上升的方向
再以X的祖父节点25为顶旋转,方向为X上升的方向
接下来我们讨论上面三种情况是否包含了所有的情况:
首先我们假设X有一个兄弟节点S,他是P的另外一个子节点,如果P是黑色的插入X没有问题(对应情况1),如果P是红色的那么他的两个子节点必须是黑色,所以此时不能单独存在一个黑色子节点S,否则路径上的黑色高度就不一样了,当P为红色的时候X不可能有兄弟节点。
另外一种可能是P的父节点G有一个子节点U,U是P的兄弟节点和X的树节点,此时如果P是黑色的,插入X不需要进行旋转。假设P是红色的,那么U必须也是红色的,不然黑色高度就不同了,这种情况在当我们沿路径向下查找插入点的时候会变换颜色,会将P和U都变换成黑色节点,所以此时有变换回了情况1。
因此上面讨论的三种可能性是全部可能存在的情况(在可能性2和3中X可能是右子节点或者左子节点,以及G可能是右子节点或者左子节点)
Ⅴ、红-黑树的删除之前我们讨论的二叉搜索树编写删除的代码比编写插入的操作的代码要难很多,红-黑树也是如此,删除节点后要恢复红黑规则变得很复杂,一般我们会用其他的方法来回避,比如说只将节点做删除的标记而不真正的删除
Ⅵ、红-黑树的效率和一般的二叉搜索树类似,红-黑树的查找,插入删除的时间复杂度为O(log2N),红-黑树的查找时间和普通的二叉搜索树查找的时间几乎完全一样,额外的开销只是存储空间增加了一个存储红黑颜色的空间。
插入和删除的时间增加了一个常数因子,因为不得不在下行的路径上和插入点执行颜色变换和旋转。平均一次插入大概需要一次旋转,因此插入的时间复杂度还是O(log2N)但是比普通的二叉搜索树要慢(不用做颜色变换和旋转)
大多数应用中查找的次数比插入和删除的次数多,所以应用红-黑树取代二叉搜索树不会增加太多的时间开销,红黑树最大的优点就是对有序的数据的操作不会慢到O(N)的时间复杂度。
此篇就是关于红黑树结构的基本理解,不足之处欢迎指出,不懂得地方欢迎提问。