RBTree 红黑树

 

纯属个人笔记，来自《Java数据结构和算法》

 

 

二叉搜索树

满足l.data<data<r.data

 

 

 

平衡树

满足|rh - lh|<=1

 

 

 

RBTree 

一、满足一下规则就是平衡树

1.每个节点红色或黑色

2.根总是黑色

3.如果节点时红色的，则它的子节点必须是黑色的

4.从跟到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点

（黑色深度需要相同）

 

重复的关键字要分配到关键字的两侧

 

 

二、修正违规的情况：

1.改变节点颜色

一般为改变根节点

 

 

2.执行旋转操作

RoR，右旋转：执行一次旋转，所有的节点都将改变位置，旋转节点的左子节点会成为他的父节点，他将成为右子节点，他的右子节点仍然是他的右子节点

 

RoL，左旋转：执行一次旋转，所有的节点都将改变位置，旋转节点的右子节点会成为他的父节点，他将成为左子节点，他的左子节点仍然是他的左子节点

 

旋转中的特殊情况-节点平移，指的是旋转节点要成为子节点的子节点，但是当子节点已经有了子节点，那么右旋，会平移到右子节点，反之亦然。

 

旋转时可以平移子树

 

 

三、插入节点

概念：G->P->X

      外侧子孙，p和x都是左子节点或右子节点

      内侧子孙，反之，p和x的左右位置不同

      

在节点下行途中的颜色变换

每当查找例程遇到一个有两个红色子节点的黑色节点时，则必须把子节点变为黑色，父节点变为红色

--会引起问题3，因为子根变为了红色

 

插入后的旋转

插入后有三种情况

1.P是黑色的

2.P是红色的，X是G的一个外侧子孙节点

3.P是红色的，X是G的一个内侧子孙节点

当是1时，不用做任何处理

当是2时，需要一次旋转和一些颜色变换

                改变G和P的颜色，G进行旋转，将X向上升的方向（一般P是什么子，就反着转，如是左子，             就右旋）

当是3时，需要两次旋转和一些颜色变换

                改变G和P的颜色，先P旋转，P是什么子，就怎么选（如是左子，就左旋），这样可以讲节点变为外侧子孙节点；接着跟情况2相同，G进行旋转，将X向上升的方向

 

在节点下行途中的旋转

（在所有的颜色变换情况，当子根变为了红色，都会导致问题3）

同样也有两种情况，子跟变换之后成为1.外侧子孙节点 2.内侧子孙节点

这是X节点为违背节点，操作和插入时的2,3情况操作相同

 

 

四、删除节点

可以如同普通二叉树那样，用中续后的节点代替；

或是不删除节点，只是忽略这个节点