技术宅的结界

 找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 527|回复: 0
收起左侧

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

[复制链接]

7

主题

18

帖子

210

积分

用户组: 中·技术宅

UID
536
精华
1
威望
16 点
宅币
146 个
贡献
9 次
宅之契约
0 份
在线时间
3 小时
注册时间
2014-11-6
发表于 2017-2-16 11:23:13 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有帐号?立即注册→加入我们

x
本帖最后由 def 于 2017-2-16 11:24 编辑

技术博客 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是补上的节点
过程如图:
1.png


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

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

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


2.png 3.png




伪代码如图

4.png

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

[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;  
}  

运行效果图 1.png

评分

参与人数 1威望 +1 宅币 +1 贡献 +1 收起 理由
cyycoish + 1 + 1 + 1 支持干货!

查看全部评分

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号|网站地图

GMT+8, 2018-12-12 19:52 , Processed in 0.101542 second(s), 36 queries , Gzip On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表