RB-tree(红黑树)详解

简介: RB-tree(红黑树)详解

RB-tree(红黑树)

红黑树的规则如下:

1.每个节点不是红色就是黑色

2.根节点为黑色

3.如果节点为红色,那么它的子节点必须为黑色

4.任何一个节点到NULL(树的尾端)的任何路径所包含的黑节点个数相同

简而言之就是每个路径的黑色节点数量相同

新增的节点必须为红,因为增加红色节点所要付出的代价会比黑色的要小很多,如果新增节点为黑色,那么就会打破第四条规则,整棵树都要调整,代价是相当之大的

红黑树节点的定义

enum Colour
{
  Red,
  Black
};
template<class K, class V>
struct RBTreeNode
{
  RBTreeNode<K, V>* _left;
  RBTreeNode<K, V>* _right;
  RBTreeNode<K, V>* _parent;
  pair<K, V> _kv;
  Colour _col;
  RBTreeNode()
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
  {}
};

红黑树的插入操作

红黑树的插入操作分为几种情况

情况一:

当cur为红、parent为红、grandparent为黑、uncle存在并且为红

操作过程:

将parent和uncle全部染成黑色,grandparent染成红色,然后把cur给grandparent继续向上判断,如果cur的parent依旧为红色,那么就要继续染色,如果cur为_root了,将根节点染成黑色。

具象图:

抽象图:

在抽象图当中,在a或者b子树当中触发了染色机制,然后一路染色上来,一直到cur也染成了红色,cur和p就造成冲突,需要继续染色。

情况二:

当cur为红,p为红,g黑,u不存在/u为黑

操作:

p为g的左孩子,cur为p的左孩子,则进行右单旋转;

相反,p为g的右孩子,cur为p的右孩子,则进行左单旋转

最后p变为黑色,cur和g变为红色

具象图:

当uncle为空的时候

抽象图:

情况三:

当cur和p为红,g为黑,u为黑/不存在

如果parent为grandparent的左儿子,对parent左旋,再对grandparent右旋

如果parent为grandparent的右儿子,对parent右旋,再对grandparent左旋

cur染为黑色,cur和grandparent染为红色。

具象图:

抽象图:

红黑树+测试代码

#pragma once
#include"AVLTree.h"
enum Colour
{
  Red,
  Black
};
template<class K, class V>
struct RBTreeNode
{
  RBTreeNode<K, V>* _left;
  RBTreeNode<K, V>* _right;
  RBTreeNode<K, V>* _parent;
  pair<K, V> _kv;
  Colour _col;
  RBTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
  {}
};
template<class K,class V>
class RBTree
{
  typedef RBTreeNode<K,V> Node;
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)
    {
      //创建根节点
      _root = new Node(kv);
      _root->_col = Black;
      return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_kv.first<kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return false;
      }
    }
    //找到插入点
    cur = new Node(kv);
    cur->_col = Red;
    //链接节点
    if (parent->_kv.first < kv.first)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
    //检查是否满足红黑树的要求
    while (parent && parent->_col == Red)
    {
      //如果父亲节点的颜色为红色,那么就有可能需要改变颜色或者旋转
      Node* grandparent = parent->_parent;
      assert(grandparent);
      assert(grandparent->_col == Black);//父亲为红色,那么祖父一定为黑色,不然之前的插入就存在问题
      if (parent == grandparent->_left)
      {
        Node* uncle = grandparent->_right;
        //情况一,uncle存在并且uncle为红色,就要继续往上染色
        if (uncle && uncle->_col == Red)
        {
          parent->_col = uncle->_col = Black;
          grandparent->_col = Red;
          cur = grandparent;
          parent = cur->_parent;
        }
        else
        {
          //uncle不存在或者uncle为黑色就会走到这里
          //情况二+情况三
          if (cur == parent->_left)
          {
            // 情况二:右单旋+变色
            //     g 
            //   p   u
            // c
            //右旋+染色
            RotateR(grandparent);
            parent->_col = Black;
            grandparent->_col = Red;
          }
          else
          {
            // 情况三:左右单旋+变色
            //     g 
            //   p   u
            //     c
            RotateL(parent);
            RotateR(grandparent);
            cur->_col = Black;
            parent->_col = grandparent->_col = Red;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandparent->_left;
        if (uncle && uncle->_col == Red)
        {
          parent->_col = uncle->_col = Black;
          grandparent->_col = Red;
          cur = grandparent;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_right)
          {
            RotateL(grandparent);
            parent->_col = Black;
            grandparent->_col = Red;
          }
          else
          {
            RotateR(parent);
            RotateL(grandparent);
            cur->_col = Black;
            grandparent->_col = Red;
          }
          break;
        }
      }
    }
    _root->_col = Black;
    return true;
  }
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
  bool IsBalance()
  {
    if (_root == nullptr)
    {
      return true;
    }
    if (_root->_col == Red)
    {
      cout << "根节点不是黑色" << endl;
      return false;
    }
    // 黑色节点数量基准值
    int benchmark = 0;
    Node* cur = _root;
    while (cur)
    {
    if (cur->_col == Black)
    ++benchmark;
    cur = cur->_left;
    }
    return PrevCheck(_root, 0, benchmark);
  }
private:
  bool PrevCheck(Node* root, int blackNum, int& benchmark)
  {
    if (root == nullptr)
    {
      if (blackNum != benchmark)
      {
        cout << "某条黑色节点的数量不相等" << endl;
        return false;
      }
      else
      {
        return true;
      }
    }
    if (root->_col == Black)
    {
      ++blackNum;
    }
    if (root->_col == Red && root->_parent->_col == Red)
    {
      cout << "存在连续的红色节点" << endl;
      return false;
    }
    return PrevCheck(root->_left, blackNum, benchmark)
      && PrevCheck(root->_right, blackNum, benchmark);
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* pparent = parent->_parent;
    parent->_right = subRL;
    if (subRL)
    {
      subRL->_parent = parent;
    }
    subR->_left = parent;
    parent->_parent = subR;
    if (parent == _root)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
      {
        pparent->_left = subR;
      }
      else
      {
        pparent->_right = subR;;
      }
      subR->_parent = pparent;
    }
  }
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    Node* pparent = parent->_parent;
    //防止空指针
    if (subLR)
    {
      subLR->_parent = parent;
    }
    subL->_right = parent;
    parent->_parent = subL;
    if (parent == _root)
    {
      //如果parent就是根节点
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      //如果parent只是一颗子树的根节点,就还需要连接好parent
      //判断是左还是右节点
      if (pparent->_left == parent)
      {
        pparent->_left = subL;
      }
      else
      {
        pparent->_right = subL;
      }
      subL->_parent = pparent;
    }
  }
  Node* _root = nullptr;
};
void TestRBTree2()
{
  size_t N = 1000;
  srand(time(0));
  RBTree<int, int> t1;
  for (size_t i = 0; i < N; ++i)
  {
    int x = rand();
    cout << "Insert:" << x << ":" << i << endl;
    t1.Insert(make_pair(x, i));
  }
  cout << "IsBalance:" << t1.IsBalance() << endl;
}

运行结果:

目录
相关文章
|
6月前
|
数据库 C++
二叉搜索树(Binary Search Tree,BST)
二叉搜索树(Binary Search Tree,BST)
|
7月前
|
定位技术 索引
R-tree 总结
R-tree 总结
90 0
树(Tree)和二叉树(Binary Tree)——(代码篇)
树(Tree)和二叉树(Binary Tree)——(代码篇)
78 0
|
存储 分布式数据库
树(Tree)和二叉树(Binary Tree)——(概念篇)
树(Tree)和二叉树(Binary Tree)——(概念篇)
79 0
|
存储 数据格式
1367:查找二叉树(tree_a)
1367:查找二叉树(tree_a)
|
存储 数据库 索引
B-Tree和B+Tree特点
B - Tree和B + Tree特点
157 0
|
数据库 索引
B-Tree, B+Tree
B-Tree, B+Tree
86 0
|
存储 Python
数据结构(二):二叉搜索树(Binary Search Tree)
二分法猜数字的游戏应该每个人都知道,通过对猜测数字“大了”、“小了”的情况判断,来猜出最终的数字。序列范围为 的集合,复杂度为 ,即最多需要 次可以猜到最终数字。
1629 0