红黑树3----删除算法原理解析
红黑树的基本变换
1.左旋右旋,实现红连接的旋转操作
2.颜色变换实现分解4节点,将红连接向上传递
3.定义操作fixUp实现由下到上分解4节点
4.定义颜色变换,使某个节点h,left,right来结合为一个4节点
private void flipColorsD(Node h){
h.color = BLACK;
h.left.color = RED;
h.right.color = RED;
}
删除算法基本思想
由于直接删除一个2节点会破坏平衡性,因此在搜索删除节点过程中进行基本变换,使得最终待删除节点位置处是非2节点,则可以直接删除该节点,由于基本变换会导致出现临时4节点,因此需要删除节点后在由下到上进行调整,分解临时4节点
删除最大值deleteMax
从根节点开始往右子树一直遍历搜索,
如果最终待删除位置为非2节点,则直接删除即可,非2节点判断条件是h.left=red 或者h=red
由于红黑树需要保证完美黑色平衡,因此直接删除2节点即直接删除黑色连接,会破坏平衡性,因此在寻找最大值过程中,需要对于红黑树进行变换,使得最终节点为非2节点
如果兄弟节点为2节点,则直接与兄弟节点合并为4节点
如果兄弟节点为3,4节点,则从兄弟节点中借一个节点组成3节点
最终目标是使得h.right为红色,这样删除最大值,即删除h.right,不会破坏平衡性
如果h为红色,或者h.right为红色,则可以直接删除
如果h.left为红色,则可以通过右旋转来变换
如果h.left,h.right,h.right.left均非红,此时待删除节点h.right为黑色,不能直接删除,因此应该从其兄弟节点借一个值,此时又分为两种情况:
兄弟节点为2节点 h.left.left=黑色,此时将兄弟节点h.left,h,h.right通过颜色变换来变为4节点
兄弟节点为3,4节点,即h.left.left=red,此时从兄弟节点中借一个值
首先将h进行颜色变换,使得h.left,h,h.right结合为一个节点,然后将h右旋转,然后在进行颜色变换分解4节点,经过此变换后h.right为非2节点
从兄弟节点将本节点变换为非2节点代码:
private Node moveRedRight(Node h){
flipColorsD(h);
if(isRed(h.left.left)){
h = rotateRight(h);
flipColorsD(h);
}
return h;
}
private void flipColorsD(Node h){
h.color = BLACK;
h.left.color = RED;
h.right.color = RED;
}
最终删除最大值代码实现如下:
private void deleteMax(){
root = deleteMax(root);
root.color = BLACK;
}
private Node deleteMax(Node h) {
if(isRed(h.left))
h = rotateRight(h);
if(h.right == null)
return null;
if(!isRed(h.right)&&!isRed(h.right.left))
h = moveRedRight(h);
h.right = deleteMax(h.right);
return fixUp(h);
}
private Node moveRedRight(Node h){
flipColorsD(h);
if(isRed(h.left.left)){
h = rotateRight(h);
flipColorsD(h);
}
return h;
}
private Node fixUp(Node h){
if(isRed(h.right))
h = rotateLeft(h);
if(isRed(h.left)&&isRed(h.left.left))
h = rotateRight(h);
if(isRed(h.left)&&isRed(h.right))
flipColors(h);
return h;
}
判断待删除节点h.right是否是2节点
h.right=black&&h.right.left=black
当某个待删除节点为2节点时,从兄弟节点处理,将该节点变为非2节点
1.兄弟节点为2节点 h.left.left=black,此时颜色变换,产生一个临时4节点
2.兄弟节点为非2节点 h.left.left=red 构造4节点,右旋转,颜色变换分解4节点
删除最大值示例
由上到下,进行变换,最终待删除节点为3节点,直接删除即可,由下到上进行4节点调整,保持平衡性。
由上到下,进行基本变换,如果h.left=red。则将红连接进行右旋转
删除最小值deleteMin
从根节点往左子树搜索,如果左子树为红连接,删除最小值直接删除即可
左节点为2节点 h.left=black h.left.left=black
此时分为两种情况,其兄弟节点为2节点h.right.left=back,直接颜色变换来生成4节点
兄弟节点为非2节点h.right.left=red,从兄弟节点中借一个值,使得该节点为3节点
生成4节点,右旋转,左旋转,分解4节点
public void deleteMin(){
root = deleteMin(root);
root.color = BLACK;
}
private Node deleteMin(Node h){
if(h.left == null)
return null;
if(!isRed(h.left)&&!isRed(h.left.left))
h = moveRedLeft(h);;
h.left = deleteMin(h.left);
return fixUp(h);
}
private Node moveRedLeft(Node h){
flipColorsD(h);
if(isRed(h.right.left)){
h.right = rotateRight(h.right);
h = rotateLeft(h);
flipColors(h);
}
return h;
}
删除最小值示例:
删除算法delete
从根节点出发寻找待删除节点位置,利用moveRedLeft,moveRedRight来不断调整左右分支内2节点,使得最终待删除节点位置处为非2节点,找到待删除节点,然后利用待删除节点右子树的最小值来取代该删除位置节点,最后由下到上依次分解4节点保持红黑树平衡。
最终实现代码:
上述删除算法,需要注意,在查找待删除子节点过程中,进入左右分支需要进行变换,这样会改变h指向节点指针,因此在变换之后需要重新进行判断,判断变换后h.key值与待删除key值大小关系
public void delete(Key key){
root = delete(root, key);
root.color = BLACK;
}
private Node delete(Node h, Key key){
int cmp = key.compareTo(h.key);
//System.out.println(h.key);
if(cmp < 0){
if(!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
h.left = delete(h.left, key);
}else{
if(isRed(h.left))
h = rotateRight(h);
//注意右旋转会改变h指针 需要重新进行判断
if(key.compareTo(h.key) == 0 && h.right == null)
return null;
//System.out.println(h.key + " " + h.right.key + " " + h.right.left.color);
if(!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);
//上面变换改变h指针,需要重新进行判断
if(key.compareTo(h.key) == 0){
//System.out.println("cmp = " + h.key);
h.key = min(h.right).key;
//System.out.println("min(h.right).key = " + min(h.right).key);
h.val = get(h.right, h.key);
h.right = deleteMin(h.right);
}else{
h.right = delete(h.right, key);
}
}
return fixUp(h);
}
红黑树性能分析
1.一颗大小为N的红黑树高度不会超过2lgN
2.一颗大小为N的红黑树,根节点到任意节点平均路径长度为 1.00lgN
3.在红黑树中,一下操作都是对数级别的:查找 插入 删除
参考链接:http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf