devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

红黑二叉搜索树（RB-Tree）_rbtree top-down insert

作者：繁依Fanyi0 | 2024-03-16 01:40:16

赞

踩

rbtree top-down insert

一、介绍

上一篇介绍了AVL-Tree，这里介绍另一个被广泛运用的平衡二叉搜索树（红黑树）（提示：知识是递进的，如果二叉搜索树都不了解，请学习相关内容再来）。

所谓的RB-Tree，不仅是一个二叉搜索树，还要满足以下条件：

（1）每个节点不是黑色就是红色。

（2）根节点是黑色。

（3）如果一个节点是红色的，则它的子节点必须是黑色的，也就是说不可能出现两个连续的红色节点，不过两个连续的黑色节点是可能出现的。

（4）从任意一个节点到NULL（树尾端）的任何路径，所包含的黑节点数必须相同。

根据规则4，新增节点必须为红；根据规则3，新增节点之父节点必须为黑。当心节点根据二叉搜索树的规则到达其插入点，却未能符合上述条件时，就必须调整颜色并旋转树形。如下图所示，（注意：深色表示黑，浅色表示红）

二、插入

要点：

1、红黑树在插入数据的时候，会先遍历数据应该插入到哪个位置，插入的位置肯定在底部，不可能在中间突然插入一个值。

2、插入的数据一定是红色的（因为要遵守红黑树的第4条规则，如果有一条分支增加了一个黑色节点，就会打破该规则）

3、插入之后，为了满足规则4，就需要用到换色与左旋、右旋的操作了

现在我们延续上图的状态，插入一些节点，看看会产生什么

假设我们对上图，插入3,8,35,75。根据二叉搜索树的规则，它们应该如下图所示。这样就破坏了红黑的规则，我们必须调整树形，也就是旋转树形并改变节点的颜色。

为了方便讨论,让我先为某些特殊节点定义一些代名.以下讨论都将沿用这些
代名.假设新节点为X,其父节点为P(Parent),祖父节点为G（Grand），伯父节点(父节点之兄弟节点)为S(Sibling),曾祖父节点为GG。现在,根据二叉搜索树的规则,新节点X必为叶子节点。根据红黑树规则4,X必为红。若P亦为红(这就违反了规则3,必须调整树形),则G必为黑(因为原为RB-tree,必须遵循规则3)。于是,根据Ⅹ的插入位置及外围节点(S和GG)的颜色,有了以下四种考虑 ：

注意,此时可能产生不平衡状态(高度相差1以上)例如图中的A和B为null，D或E不为null。这倒没关系,因为RB-tree的平衡性本来就比AVL-tree弱，然而RB-tree通常能够导致良好的平衡状态。是的,经验告诉我们,RB-tree的搜寻平均效率和AVL-tree几乎相等 

最后一个步骤

为了避免状况4——父子节点皆为红色”的情况。持续向RB-tree的上层结构发展，形成处理时效上的瓶颈，我们可以施行一个由上而下的步骤( top-downprocedure)：假设新增节点为A，那么就延着A的路径，只要看到有某节点X的两个子节点皆为红色，就把X改为红色，并把两个子节点改为黑色，如图5-15e所示 

 三、代码实现

  1.         #ifndef CM_RBTREE_HPP
  2.         #define CM_RBTREE_HPP  
  3.       	#include "BinarySearchTree.hpp"
  4.       	namespace cm
  5.       	{
  6.       	  template<typename T> class RBTreeNode;
  7.       	  template<typename T> class RBTreeIterator;
  8.       	  template<typename T> class RBTree;
  9.       	
  10.       	  template<typename T>
  11.       	    class RBTreeNode
  12.       	    {
  13.       	      public:
  14.       	        typedef T VALUE_TYPE;
  15.       	        enum Color_t { 
  16.       	          COLOR_BLACK,
  17.       	          COLOR_RED
  18.       	        };
  19.       	
  20.       	      public:
  21.       	        explicit RBTreeNode(const T& v=T(), Color_t c=COLOR_BLACK)
  22.       	          : value_(v)
  23.       	            , left_(NIL)
  24.       	            , right_(NIL)
  25.       	            , parent_(NIL)
  26.       	            , color_(c)
  27.       	      {
  28.       	      }
  29.       	
  30.       	        RBTreeNode<T>* left()  {  return left_;   }
  31.       	        RBTreeNode<T>* right() {  return right_;  }
  32.       	        RBTreeNode<T>* parent(){  return parent_; }
  33.       	        RBTreeNode<T>* left()   const {  return left_;   }
  34.       	        RBTreeNode<T>* right()  const {  return right_;  }
  35.       	        RBTreeNode<T>* parent() const {  return parent_; }
  36.       	        const T&     value()        const {  return value_;  }
  37.       	        Color_t color()             const {  return color_;  }
  38.       	
  39.       	        void left(RBTreeNode<T>* node)  {  left_ = node;   }
  40.       	        void right(RBTreeNode<T>* node) {  right_ = node;  }
  41.       	        void parent(RBTreeNode<T>* node){  parent_ = node; }
  42.       	        void value(const T& value)          {  value_ = value; }
  43.       	        void color(Color_t c)               { color_ = c;      }
  44.       	
  45.       	        operator bool() const
  46.       	        {
  47.       	          return this != NIL;
  48.       	        }
  49.       	
  50.       	        bool operator !() const
  51.       	        {
  52.       	          return this == NIL;
  53.       	        }
  54.       	
  55.       	      public:
  56.       	        static RBTreeNode<T>* NIL;
  57.       	
  58.       	      private:
  59.       	        T            value_;
  60.       	        RBTreeNode<T>* left_;
  61.       	        RBTreeNode<T>* right_;
  62.       	        RBTreeNode<T>* parent_;
  63.       	        Color_t color_;
  64.       	    }; 
  65.       	  template<typename T>
  66.       	    RBTreeNode<T>* RBTreeNode<T>::NIL(new RBTreeNode<T>());
  67.       	
  68.       	  template<typename T>
  69.       	    class RBTree: public BinarySearchTree_T< RBTreeNode<T> >
  70.       	  {
  71.       	    public:
  72.       	      typedef RBTreeNode<T> Node;
  73.       	
  74.       	    public:
  75.       	      size_t bh() const
  76.       	      {
  77.       	        return this->bh(this->getRoot());
  78.       	      }
  79.       	      size_t bh(const Node* node) const
  80.       	      {
  81.       	        Node* n = node;
  82.       	        size_t h =  ;
  83.       	        while (n) {
  84.       	          if (n->color() == Node::COLOR_BLACK) {
  85.       	            ++h;
  86.       	          }
  87.       	          n = n->left();
  88.       	        }
  89.       	        return h;
  90.       	      }
  91.       	      size_t insert(const T& key)
  92.       	      {
  93.       	        Node* z = new Node(key, Node::COLOR_RED);    // 要插入的节点
  94.       	        Node* y = Node::NIL;    // y 是 x 的父节点
  95.       	        Node* x = this->root();
  96.       	        while (x != Node::NIL) {
  97.       	          y = x;
  98.       	          if (key == x->value()) {
  99.       	            return  0;
  100.       	          }
  101.       	
  102.       	          if (key < x->value()) {
  103.       	            x = x->left();
  104.       	          }
  105.       	          else {
  106.       	            x = x->right();
  107.       	          }
  108.       	        }
  109.       	
  110.       	        z->parent(y);
  111.       	
  112.       	        if (y == Node::NIL) {
  113.       	          this->root_ = z;
  114.       	          this->root_->parent(Node::NIL);
  115.       	        }
  116.       	        else {
  117.       	          if(key < y->value()) {
  118.       	            y->left(z);
  119.       	          }
  120.       	          else {
  121.       	            y->right(z);
  122.       	          }
  123.       	        }
  124.       	
  125.       	        z->left(Node::NIL);
  126.       	        z->right(Node::NIL);
  127.        	          insert_fixup(z);
  128.       	
  129.       	        ++this->size_;
  130.       	        return  ;
  131.       	      }
  132.       	
  133.       	      void remove(Node* z)
  134.       	      {
  135.       	        Node* y = Node::NIL;
  136.       	        Node* x = Node::NIL;
  137.       	        if (z->left() == Node::NIL || z->right() == Node::NIL) {
  138.       	          y = z;
  139.       	        }
  140.       	        else {
  141.       	          //y = this->successor(z);
  142.       	          y = z->right();
  143.       	          while (y->left() != Node::NIL) {
  144.       	            y = y->left();
  145.       	          }
  146.       	        }
  147.       	
  148.       	        // x 是 y的唯一孩子
  149.       	        if (y->left() != Node::NIL) {
  150.       	          x = y->left();
  151.       	        }
  152.       	        else {
  153.       	          x = y->right();
  154.       	        }
  155.       	
  156.       	        x->parent(y->parent());
  157.       	
  158.       	        if(y->parent() == Node::NIL) {
  159.       	          this->root_ = x;
  160.       	        }
  161.       	        else {
  162.       	          if (y == y->parent()->left()) {
  163.       	            y->parent()->left(x);
  164.       	          }
  165.       	          else {
  166.       	            y->parent()->right(x);
  167.       	          }
  168.       	        }
  169.       	
  170.       	        if (y != z) {
  171.       	          z->value(y->value());
  172.       	        }
  173.       	
  174.       	        if (y->color() == Node::COLOR_BLACK) {
  175.       	          this->delete_fixup(x);
  176.       	        }
  177.       	
  178.       	        delete y;
  179.       	        --this->size_;
  180.       	      }
  181.       	
  182.       	      /// 如果key存在，删除并返回 ，否则返回 
  183.       	      size_t remove(const T& key)
  184.       	      {
  185.       	        Node* node = this->find(key);
  186.       	        if (node != Node::NIL) {
  187.       	          this->remove(node);
  188.       	          return  ;
  189.       	        }
  190.       	
  191.       	        return  ;
  192.       	      }
  193.       	
  194.       	    private:
  195.       	      void left_rotate(Node* x)
  196.       	      {
  197.       	        Node* y = x->right();
  198.       	
  199.       	        // 把y的左子数变成x的右子树
  200.       	        x->right(y->left());
  201.       	
  202.       	        if (y->left() != Node::NIL) {
  203.       	          y->left()->parent(x);
  204.       	        }
  205.       	
  206.       	        if (y != Node::NIL) {
  207.       	          y->parent(x->parent());
  208.       	        }
  209.       	
  210.       	        if (x->parent() == Node::NIL) {
  211.       	          this->root_ = y;
  212.       	        }
  213.       	        else {
  214.       	          if (x == x->parent()->left()) {
  215.       	            x->parent()->left(y);
  216.       	          }
  217.       	          else {
  218.       	            x->parent()->right(y);
  219.       	          }
  220.       	        }
  221.       	
  222.       	        // 把x变成y的左子节点
  223.       	        y->left(x);
  224.       	        if (x != Node::NIL) {
  225.       	          x->parent(y);
  226.       	        }
  227.       	      }
  228.       	      void right_rotate(Node* x)
  229.       	      {
  230.       	        Node* y = x->left();
  231.       	         x->left(y->right());
  232.       	
  233.       	        if (y->right() != Node::NIL) {
  234.       	          y->right()->parent(x);
  235.       	        }
  236.       	
  237.       	        if (y != Node::NIL) {
  238.       	          y->parent(x->parent());
  239.       	        }
  240.       	
  241.       	        if (x->parent() == Node::NIL) {
  242.       	          this->root_ = y;
  243.       	        }
  244.       	        else {
  245.       	          if (x == x->parent()->left()) {
  246.       	            x->parent()->left(y);
  247.       	          }
  248.       	          else {
  249.       	            x->parent()->right(y);
  250.       	          }
  251.       	        }
  252.       	
  253.       	        y->right(x);
  254.       	        if (x != Node::NIL) {
  255.       	          x->parent(y);
  256.       	        }
  257.       	      }
  258.       	
  259.       	      void insert_fixup(Node* z)
  260.       	      {
  261.       	        Node* y = Node::NIL;
  262.       	        while (z != this->root() && z->parent()->color() == Node::COLOR_RED) {
  263.       	          if (z->parent() == z->parent()->parent()->left()) {
  264.       	            y = z->parent()->parent()->right();
  265.       	            if (y->color() == Node::COLOR_RED) {
  266.       	              z->parent()->color(Node::COLOR_BLACK);
  267.       	              y->color(Node::COLOR_BLACK);
  268.       	              z->parent()->parent()->color(Node::COLOR_RED);
  269.       	              z = z->parent()->parent();
  270.       	            }
  271.       	            else {
  272.       	              if (z == z->parent()->right()) {
  273.       	                z = z->parent();
  274.       	                this->left_rotate(z);
  275.       	              }
  276.       	
  277.       	              z->parent()->color(Node::COLOR_BLACK);
  278.       	              z->parent()->parent()->color(Node::COLOR_RED);
  279.       	              this->right_rotate(z->parent()->parent());
  280.       	            }
  281.       	          }
  282.       	          else {
  283.       	            y = z->parent()->parent()->left();
  284.       	            if (y->color() == Node::COLOR_RED) {
  285.       	              z->parent()->color(Node::COLOR_BLACK);
  286.       	              y->color(Node::COLOR_BLACK);
  287.       	              z->parent()->parent()->color(Node::COLOR_RED);
  288.       	              z = z->parent()->parent();
  289.       	            }
  290.       	            else {
  291.       	              if (z == z->parent()->left()) {
  292.       	                z = z->parent();
  293.       	                this->right_rotate(z);
  294.       	              }
  295.       	
  296.       	              z->parent()->color(Node::COLOR_BLACK);
  297.       	              z->parent()->parent()->color(Node::COLOR_RED);
  298.       	              this->left_rotate(z->parent()->parent());
  299.       	            }
  300.       	          }
  301.       	        }
  302.       	
  303.       	        this->root()->color(Node::COLOR_BLACK);
  304.       	      }
  305.       	
  306.       	      void delete_fixup(Node* x)
  307.       	      {
  308.       	        Node* w = Node::NIL;
  309.       	        while (x != this->root() && x->color() == Node::COLOR_BLACK) {
  310.       	          if (x == x->parent()->left()) {
  311.       	            w = x->parent()->right();
  312.       	            if (w->color() == Node::COLOR_RED) {
  313.       	              w->color(Node::COLOR_BLACK);
  314.       	              x->parent()->color(Node::COLOR_RED);
  315.       	              this->left_rotate(x->parent());
  316.       	              w = x->parent()->right();
  317.       	            }
  318.       	            if (w->left()->color() == Node::COLOR_BLACK && w->right()->color() == Node::COLOR_BLACK) {
  319.       	              w->color(Node::COLOR_RED);
  320.       	              x = x->parent();
  321.       	            } else {
  322.       	              if (w->right()->color() == Node::COLOR_BLACK) {
  323.       	                w->left()->color(Node::COLOR_BLACK);
  324.       	                w->color(Node::COLOR_RED);
  325.       	                right_rotate(w);
  326.       	                w = x->parent()->right();
  327.       	              }
  328.       	              w->color(x->parent()->color());
  329.       	              x->parent()->color(Node::COLOR_BLACK);
  330.       	              w->right()->color(Node::COLOR_BLACK);
  331.       	              left_rotate(x->parent());
  332.       	              x = this->root();
  333.       	            }
  334.       	          } else {
  335.       	            w = x->parent()->left();
  336.       	            if (w->color() == Node::COLOR_RED) {
  337.       	              w->color(Node::COLOR_BLACK);
  338.       	              x->parent()->color(Node::COLOR_RED);
  339.       	              right_rotate(x->parent());
  340.       	              w = x->parent()->left();
  341.       	            }
  342.       	            if (w->right()->color() == Node::COLOR_BLACK && w->left()->color() == Node::COLOR_BLACK) {
  343.       	              w->color(Node::COLOR_RED);
  344.       	              x = x->parent();
  345.       	            } else {
  346.       	              if (w->left()->color() == Node::COLOR_BLACK) {
  347.       	                w->right()->color(Node::COLOR_BLACK);
  348.       	                w->color(Node::COLOR_RED);
  349.       	                left_rotate(w);
  350.       	                w = x->parent()->left();
  351.       	              }
  352.       	              w->color(x->parent()->color());
  353.       	              x->parent()->color(Node::COLOR_BLACK);
  354.       	              w->left()->color(Node::COLOR_BLACK);
  355.       	              right_rotate(x->parent());
  356.       	              x = this->root();
  357.       	            }
  358.       	          }
  359.       	        }
  360.       	
  361.       	        x->color(Node::COLOR_BLACK);
  362.       	      }
  363.       	  };
  364.       	
  365.       	  template<typename T>
  366.       	    class RBTreeIterator
  367.       	    {
  368.       	      public:
  369.       	        RBTreeIterator()
  370.       	          : tree_(RBTreeNode<T>::NIL), current_(RBTreeNode<T>::NIL)
  371.       	        {
  372.       	        }
  373.       	
  374.       	        RBTreeIterator(RBTree<T>& tree, typename RBTree<T>::Node* current)
  375.       	          : tree_(tree), current_(current)
  376.       	        {
  377.       	        }
  378.       	
  379.       	        const T& operator*() const
  380.       	        {
  381.       	          return current_->value();
  382.       	        }
  383.       	
  384.       	        T* operator->()
  385.       	        {
  386.       	          return current_;
  387.       	        }
  388.       	
  389.       	        bool operator==(const RBTreeIterator& rhs) const
  390.       	        {
  391.       	          return current_ == rhs.current_;
  392.       	        }
  393.       	
  394.       	        bool operator!=(const RBTreeIterator& rhs) const
  395.       	        {
  396.       	          return current_ != rhs.current_;
  397.       	        }
  398.       	        RBTreeIterator& operator++()
  399.       	        {
  400.       	          current_ = tree_.successor(current_);
  401.       	          return *this;
  402.       	        }
  403.       	
  404.       	      private:
  405.       	        RBTree<T>& tree_;
  406.       	        typename RBTree<T>::Node* current_;
  407.       	    };
  408.       	
  409.       	
  410.       	} // end namespace cm
  411.       	
  412.       	#endif // CM_RBTREE_HPP

 参考：

【算法】红黑树插入数据（变色，左旋、右旋）（二）_lsr40的博客-CSDN博客_红黑树左旋右旋

深入理解红黑树及C++实现 - 守功 - 博客园

红黑树的C++实现与解析_wang11chao01的博客-CSDN博客_c++红黑树案例

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/246131
推荐阅读

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。