算法导论 红黑树 学习 删除(四)

def

技术博客 http://blog.csdn.net/stecdeng 技术交流群 群号码：324164944 欢迎c c++ windows驱动爱好者 服务器程序员沟通交流

学习算法 还是建议看看算法导论

算法导论第三版 如果不看数学推导 仅看伪代码 难度还是适中

本系列只是记录我的学习心得 和伪代码转化代码的过程

深入学习 还是建议大家看看算法书籍 教程更加系统。

本文参考算法导论第13章节 红黑树

代码由本人写成

转载请标明出处


先看看不做颜色处理的删除

不做颜色处理的删除基本就和二叉树类似

如果删除节点没有子树 最简单 直接删除

如果待删除的节点只有一个儿子(左子树或者右子树) 那么删除该节点 儿子补上即可

[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
void RBTransplant(std::shared_ptr<node>& root,  
    std::shared_ptr<node> u, std::shared_ptr<node> v) {  
    if (u->parent_ == nil)  
        root = v;  
    else if (u == u->parent_->left_)  
        u->parent_->left_ = v;  
    else  
        u->parent_->right_ = v;  
    v->parent_ = u->parent_;  
}  

u是要删除的节点 v是补上的节点
过程如图:



若是待删除节点有两个子树 那么寻找待删除节点右子树最小的节点，这个节点要么就是删除节点右子树，要么就是沿着删除节点右子树向左遍历的终点

如图： 如果7是待删除节点，那么目标不是11 就是9

将删除节点和目标节点值互换 在处理目标节点  那么就把两棵子树节点的删除更改为无子树或者单子树节点的删除，很巧妙！







伪代码如图



删除代码及测试代码如下(删除未调整颜色版本,可运行)

[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
// rbTreeTest.cpp : 定义控制台应用程序的入口点。  
//  
  
#include "stdafx.h"  
#include <memory>  
#include <iostream>  
  
using namespace std;  
  
enum Color {  
    red = 1,  
    black  
};  
  
struct node {  
    Color color_;  
    std::shared_ptr<node> left_;  
    std::shared_ptr<node> right_;  
    std::shared_ptr<node> parent_;  
    int value_;  
    node() {  
        left_ = right_ = parent_ = nullptr;  
        value_ = -1;  
        color_ = black;  
    }  
};  
  
std::shared_ptr<node> nil(new node);  
  
  
std::shared_ptr<node> CreateNode(Color color, int i) {  
    std::shared_ptr<node> p(new node);  
    p->color_ = color;  
    p->left_ = nil;  
    p->right_ = nil;  
    p->parent_ = nil;  
    p->value_ = i;  
    return p;  
}  
  
void RightRotate(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
    std::shared_ptr<node> y = x->left_;  
    x->left_ = y->right_;  
    if (y->right_ != nil)  
        y->right_->parent_ = x;  
    y->parent_ = x->parent_;  
    if (x->parent_ == nil) {  
        root = y;  
    }  
    else if (x->parent_->left_ == x) {  
        x->parent_->left_ = y;  
    }  
    else {  
        x->parent_->right_ = y;  
    }  
  
    y->right_ = x;  
    x->parent_ = y;  
}  
  
void LeftRotate(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
    std::shared_ptr<node> y = x->right_;  
    x->right_ = y->left_;  
    if (y->left_ != nil)  
        y->left_->parent_ = x;  
  
    y->parent_ = x->parent_;  
    if (x->parent_ == nil) {  
        root = y;  
    }  
    else if (x->parent_->left_ == x) {  
        x->parent_->left_ = y;  
    }  
    else {  
        x->parent_->right_ = y;  
    }  
    y->left_ = x;  
    x->parent_ = y;  
}  
  
void PrinTree(std::shared_ptr<node> root) {  
    if (root == nil) {  
        std::cout << "nil:" << ":color-" << root->color_ << " ; " << std::endl << std::endl;  
        return;  
    }  
    std::cout << root->value_ << ":color-" << root->color_ << "; address:" << root << std::endl;  
    if (root->parent_ == nil) {  
        std::cout << "parent_:" << "nil" << std::endl;  
    }  
    else {  
        std::cout << "parent_:" << root->parent_->value_ << std::endl;  
    }  
  
    if (root->left_ == nil) {  
        std::cout << "left_:" << "nil" << std::endl;  
    }  
    else {  
        std::cout << "left_:" << root->left_->value_ << std::endl;  
    }  
  
  
    if (root->right_ == nil) {  
        std::cout << "right_:" << "nil" << std::endl;  
    }  
    else {  
        std::cout << "right_:" << root->right_->value_ << std::endl;  
    }  
  
    std::cout << std::endl;  
  
  
    if (root->left_ != nil)  
        PrinTree(root->left_);  
    if (root->right_ != nil)  
        PrinTree(root->right_);  
}  
  
void RBInsertFixup(std::shared_ptr<node>& root, std::shared_ptr<node> z) {  
    while (z->parent_->color_ == red) {   //插入节点Z是红色 若Z父节点也是红色则需要调整  
        if (z->parent_ == z->parent_->parent_->left_) {  // 父节点是左子树的情况  
            std::shared_ptr<node> y = z->parent_->parent_->right_;  
            if (y->color_ == red) {                   //  情况1  
                z->parent_->color_ = black;  
                y->color_ = black;  
                z->parent_->parent_->color_ = red;  
                z = z->parent_->parent_;  
            }  
            else {  
                if (z == z->parent_->right_) {  
                    z = z->parent_;                  //  情况2  
                    LeftRotate(root, z);  
                }  
                z->parent_->color_ = black;           //  情况3  
                z->parent_->parent_->color_ = red;  
                RightRotate(root, z->parent_->parent_);  
            }  
        }  
        else {// 父节点是右子树的情况 与上面判断处理均是镜像对称  
            std::shared_ptr<node> y = z->parent_->parent_->left_;  
            if (y->color_ == red) {  
                z->parent_->color_ = black;  
                y->color_ = black;  
                z->parent_->parent_->color_ = red;  
                z = z->parent_->parent_;  
            }  
            else {  
                if (z == z->parent_->left_) {  
                    z = z->parent_;  
                    RightRotate(root, z);  
                }  
                z->parent_->color_ = black;  
                z->parent_->parent_->color_ = red;  
                LeftRotate(root, z->parent_->parent_);  
            }  
        }  
    }//while (z->parent_->color_ == red)  
    root->color_ = black;  
}//function end  
  
void RBInsert(std::shared_ptr<node>& root, std::shared_ptr<node> ins) {  
    std::shared_ptr<node> y = nil;  
    std::shared_ptr<node> x = root;  
  
    while (x != nil) {  
        y = x;  
        if (ins->value_ < x->value_) {  
            x = x->left_;  
        }  
        else {  
            x = x->right_;  
        }  
    }  
    ins->parent_ = y;  
    if (y == nil) {  
        root = ins;  
    }  
    else if (ins->value_ < y->value_) {  
        y->left_ = ins;  
    }  
    else {  
        y->right_ = ins;  
    }  
    ins->left_ = ins->right_ = nil;  
    ins->color_ = red;  
    // todo  fixup  
    RBInsertFixup(root, ins);  
}  
  
std::shared_ptr<node> CreateRB() {  
    std::shared_ptr<node> root = nil;  
    std::shared_ptr<node> x = CreateNode(red, 7);  
    RBInsert(root, x);  
  
  
    x = CreateNode(red, 4);  
    RBInsert(root, x);  
  
    x = CreateNode(red, 11);  
    RBInsert(root, x);  
  
    x = CreateNode(red, 3);  
    RBInsert(root, x);  
  
  
      
    //PrinTree(root);  
    //std::cout << std::endl;  
  
    return root;  
}  
  
//=============================================  
// delete test  
std::shared_ptr<node> RBMinimum(std::shared_ptr<node> n) {  
    while (n->left_ != nil) {  
        n = n->left_;  
    }  
    return n;  
}  
  
std::shared_ptr<node> RBMaximum(std::shared_ptr<node> n) {  
    while (n->right_ != nil) {  
        n = n->right_;  
    }  
    return n;  
}  
  
std::shared_ptr<node> RBSuccessor(std::shared_ptr<node> n) {  
    if (n->right_ != nil)  
        return RBMinimum(n->right_);  
    std::shared_ptr<node> y = n->parent_;  
    while (y != nil && n == y->right_) {  
        n = y;  
        y = y->parent_;  
    }  
    return y;  
}  
  
void RBTransplant(std::shared_ptr<node>& root,  
    std::shared_ptr<node> u, std::shared_ptr<node> v) {  
    if (u->parent_ == nil)  
        root = v;  
    else if (u == u->parent_->left_)  
        u->parent_->left_ = v;  
    else  
        u->parent_->right_ = v;  
    v->parent_ = u->parent_;  
}  
  
void RBDelete(std::shared_ptr<node>& root,std::shared_ptr<node> z) {  
    if (root == nil || z == nil) {  
        return;  
    }  
    std::shared_ptr<node> y = z;  
    Color original_color = y->color_;  
    std::shared_ptr<node> x;  
    if (z->left_ == nil) {  
        x = z->right_;  
        RBTransplant(root, z, z->right_);  
    }  
    else if (z->right_ == nil) {  
        x = z->left_;  
        RBTransplant(root, z, z->left_);  
    }  
    else {  
        y = RBMinimum(z->right_);  
        original_color = y->color_;  
        x = y->right_;  
        if (y->parent_ == z)  
            x->parent_ = y;  
        else {  
            RBTransplant(root,y,y->right_);  
            y->right_ = z->right_;  
            y->right_->parent_ = y;  
        }  
        RBTransplant(root,z,y);  
        y->left_ = z->left_;  
        y->left_->parent_ = y;  
        y->color_ = z->color_;  
    }  
    if (y->color_ == black) {}  
        //RBDeleteFixup(root,x);  
         
}  
  
//=============================================  
  
int main()  
{  
    std::shared_ptr<node> root = CreateRB();  
    PrinTree(root);  
    std::cout << "===========================" << std::endl;  
      
    RBDelete(root,root);  
    PrinTree(root);  
    std::cout << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << std::endl;  
      
  
  
    return 0;  
}  



最后全部代码如下  增删 打印 调整功能 可运行调试

[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
// rbTreeTest.cpp : 定义控制台应用程序的入口点。  
//  
  
#include "stdafx.h"  
#include <memory>  
#include <iostream>  
  
using namespace std;  
  
enum Color {  
    red = 1,  
    black  
};  
  
struct node {  
    Color color_;  
    std::shared_ptr<node> left_;  
    std::shared_ptr<node> right_;  
    std::shared_ptr<node> parent_;  
    int value_;  
    node() {  
        left_ = right_ = parent_ = nullptr;  
        value_ = -1;  
        color_ = black;  
    }  
};  
  
std::shared_ptr<node> nil(new node);  
  
  
std::shared_ptr<node> CreateNode(Color color, int i) {  
    std::shared_ptr<node> p(new node);  
    p->color_ = color;  
    p->left_ = nil;  
    p->right_ = nil;  
    p->parent_ = nil;  
    p->value_ = i;  
    return p;  
}  
  
void RightRotate(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
    std::shared_ptr<node> y = x->left_;  
    x->left_ = y->right_;  
    if (y->right_ != nil)  
        y->right_->parent_ = x;  
    y->parent_ = x->parent_;  
    if (x->parent_ == nil) {  
        root = y;  
    }  
    else if (x->parent_->left_ == x) {  
        x->parent_->left_ = y;  
    }  
    else {  
        x->parent_->right_ = y;  
    }  
  
    y->right_ = x;  
    x->parent_ = y;  
}  
  
void LeftRotate(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
    std::shared_ptr<node> y = x->right_;  
    x->right_ = y->left_;  
    if (y->left_ != nil)  
        y->left_->parent_ = x;  
  
    y->parent_ = x->parent_;  
    if (x->parent_ == nil) {  
        root = y;  
    }  
    else if (x->parent_->left_ == x) {  
        x->parent_->left_ = y;  
    }  
    else {  
        x->parent_->right_ = y;  
    }  
    y->left_ = x;  
    x->parent_ = y;  
}  
  
void PrinTree(std::shared_ptr<node> root) {  
    if (root == nil) {  
        std::cout << "nil:" << ":color-" << root->color_ << " ; " << std::endl << std::endl;  
        return;  
    }  
    std::cout << root->value_ << ":color-" << root->color_ << "; address:" << root << std::endl;  
    if (root->parent_ == nil) {  
        std::cout << "parent_:" << "nil" << std::endl;  
    }  
    else {  
        std::cout << "parent_:" << root->parent_->value_ << std::endl;  
    }  
  
    if (root->left_ == nil) {  
        std::cout << "left_:" << "nil" << std::endl;  
    }  
    else {  
        std::cout << "left_:" << root->left_->value_ << std::endl;  
    }  
  
  
    if (root->right_ == nil) {  
        std::cout << "right_:" << "nil" << std::endl;  
    }  
    else {  
        std::cout << "right_:" << root->right_->value_ << std::endl;  
    }  
  
    std::cout << std::endl;  
  
  
    if (root->left_ != nil)  
        PrinTree(root->left_);  
    if (root->right_ != nil)  
        PrinTree(root->right_);  
}  
  
void RBInsertFixup(std::shared_ptr<node>& root, std::shared_ptr<node> z) {  
    while (z->parent_->color_ == red) {   //插入节点Z是红色 若Z父节点也是红色则需要调整  
        if (z->parent_ == z->parent_->parent_->left_) {  // 父节点是左子树的情况  
            std::shared_ptr<node> y = z->parent_->parent_->right_;  
            if (y->color_ == red) {                   //  情况1  
                z->parent_->color_ = black;  
                y->color_ = black;  
                z->parent_->parent_->color_ = red;  
                z = z->parent_->parent_;  
            }  
            else {  
                if (z == z->parent_->right_) {  
                    z = z->parent_;                  //  情况2  
                    LeftRotate(root, z);  
                }  
                z->parent_->color_ = black;           //  情况3  
                z->parent_->parent_->color_ = red;  
                RightRotate(root, z->parent_->parent_);  
            }  
        }  
        else {// 父节点是右子树的情况 与上面判断处理均是镜像对称  
            std::shared_ptr<node> y = z->parent_->parent_->left_;  
            if (y->color_ == red) {  
                z->parent_->color_ = black;  
                y->color_ = black;  
                z->parent_->parent_->color_ = red;  
                z = z->parent_->parent_;  
            }  
            else {  
                if (z == z->parent_->left_) {  
                    z = z->parent_;  
                    RightRotate(root, z);  
                }  
                z->parent_->color_ = black;  
                z->parent_->parent_->color_ = red;  
                LeftRotate(root, z->parent_->parent_);  
            }  
        }  
    }//while (z->parent_->color_ == red)  
    root->color_ = black;  
}//function end  
  
void RBInsert(std::shared_ptr<node>& root, std::shared_ptr<node> ins) {  
    std::shared_ptr<node> y = nil;  
    std::shared_ptr<node> x = root;  
  
    while (x != nil) {  
        y = x;  
        if (ins->value_ < x->value_) {  
            x = x->left_;  
        }  
        else {  
            x = x->right_;  
        }  
    }  
    ins->parent_ = y;  
    if (y == nil) {  
        root = ins;  
    }  
    else if (ins->value_ < y->value_) {  
        y->left_ = ins;  
    }  
    else {  
        y->right_ = ins;  
    }  
    ins->left_ = ins->right_ = nil;  
    ins->color_ = red;  
    // todo  fixup  
    RBInsertFixup(root, ins);  
}  
  
std::shared_ptr<node> CreateRB() {  
      
    std::shared_ptr<node> root = nil;  
    std::shared_ptr<node> x = CreateNode(red, 15);  
    RBInsert(root, x);  
  
  
    x = CreateNode(red, 10);  
    RBInsert(root, x);  
  
    x = CreateNode(red, 20);  
    RBInsert(root, x);  
  
    x = CreateNode(red, 5);  
    RBInsert(root, x);  
  
    x = CreateNode(red, 13);  
    RBInsert(root, x);  
  
    x = CreateNode(red, 17);  
    RBInsert(root, x);  
  
    x = CreateNode(red, 25);  
    RBInsert(root, x);  
      
  
    return root;  
}  
  
//=============================================  
// delete test  
std::shared_ptr<node> RBMinimum(std::shared_ptr<node> n) {  
    while (n->left_ != nil) {  
        n = n->left_;  
    }  
    return n;  
}  
  
std::shared_ptr<node> RBMaximum(std::shared_ptr<node> n) {  
    while (n->right_ != nil) {  
        n = n->right_;  
    }  
    return n;  
}  
  
std::shared_ptr<node> RBSuccessor(std::shared_ptr<node> n) {  
    if (n->right_ != nil)  
        return RBMinimum(n->right_);  
    std::shared_ptr<node> y = n->parent_;  
    while (y != nil && n == y->right_) {  
        n = y;  
        y = y->parent_;  
    }  
    return y;  
}  
  
void RBTransplant(std::shared_ptr<node>& root,  
    std::shared_ptr<node> u, std::shared_ptr<node> v) {  
    if (u->parent_ == nil)  
        root = v;  
    else if (u == u->parent_->left_)  
        u->parent_->left_ = v;  
    else  
        u->parent_->right_ = v;  
    v->parent_ = u->parent_;  
}  
  
void RBDeleteFixup(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
    while (x != root && x->color_ == black) {  
        if (x == x->parent_->left_) {  
            std::shared_ptr<node> w = x->parent_->right_;  
            if (w->color_ == red) {  
                w->color_ = black;  
                x->parent_->color_ = red;  
                LeftRotate(root, x->parent_);  
                w = x->parent_->right_;  
            }  
  
            if (w->left_->color_ == black && w->right_->color_ == black) {  
                w->color_ = red;  
                x = x->parent_;  
            }  
            else {  
                if (w->right_->color_ == black) {  
                    w->left_->color_ = black;  
                    w->color_ = red;  
                    RightRotate(root,w);  
                    w = x->parent_->right_;  
                }  
                w->color_ = x->parent_->color_;  
                x->parent_->color_ = black;  
                w->right_->color_ = black;  
                LeftRotate(root,x->parent_);  
                x = root;  
            }  
        }else {  
            std::shared_ptr<node> w = x->parent_->left_;  
            if (w->color_ == red) {  
                w->color_ = black;  
                x->parent_->color_ = red;  
                RightRotate(root, x->parent_);  
                w = x->parent_->left_;  
            }  
  
            if (w->right_->color_ == black && w->left_->color_ == black) {  
                w->color_ = red;  
                x = x->parent_;  
            }  
            else {  
                if (w->left_->color_ == black) {  
                    w->right_->color_ = black;  
                    w->color_ = red;  
                    LeftRotate(root, w);  
                    w = x->parent_->left_;  
                }  
                w->color_ = x->parent_->color_;  
                x->parent_->color_ = black;  
                w->left_->color_ = black;  
                RightRotate(root, x->parent_);  
                x = root;  
            }  
        }  
    }//while (x != root && x->color_ == black)   
  
    x->color_ = black;  
}  
  
  
  
  
  
  
void RBDelete(std::shared_ptr<node>& root,std::shared_ptr<node> z) {  
    if (root == nil || z == nil)  
        return;  
    std::shared_ptr<node> y;  
    std::shared_ptr<node> x;  
    if (z->left_ == nil || z->right_ == nil) {  
        y = z;  
    }  
    else {  
        y = RBSuccessor(z);  
    }  
  
    if (y->left_ != nil) {  
        x = y->left_;  
    }  
    else {  
        x = y->right_;  
    }  
    x->parent_ = y->parent_;  
    if (y->parent_ == nil) {  
        root = x;  
    }  
    else {  
        if (y == y->parent_->left_) {  
            y->parent_->left_ = x;  
        }  
        else {  
            y->parent_->right_ = x;  
        }  
    }  
  
    if (y != z) {  
        z->value_ = y->value_;  
    }  
  
    if (y->color_ == black) {  
        //todo  
        RBDeleteFixup(root,x);  
    }  
}  
  
  
  
//=============================================  
  
int main()  
{  
    std::shared_ptr<node> root = CreateRB();  
    PrinTree(root);  
    std::cout << "===========================" << std::endl;  
  
  
    RBDelete(root,root);  
    PrinTree(root);  
    std::cout << "===========================" << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << "===========================" << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << "===========================" << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << "===========================" << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << "===========================" << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << "===========================" << std::endl;  
  
    RBDelete(root, root);  
    PrinTree(root);  
    std::cout << "===========================" << std::endl;  
  
    return 0;  
}  

运行效果图