论坛 › 技巧探讨 › 算法导论 红黑树 学习 删除(四)

def 发表于 2017-2-16 11:23:13

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

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

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

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

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

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

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

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

代码由本人写成

转载请标明出处


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

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

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

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

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

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







伪代码如图



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

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;
    // todofixup
    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;
}



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

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;
    // todofixup
    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;
}

运行效果图

查看完整版本: 算法导论 红黑树 学习 删除(四)