备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】红黑树

2023-10-11 22
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】红黑树

1. 红黑树的概念与性质


1.1 概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

0cfc542fb78782c12ad634a67f9fe291.png


1.2 性质

红黑树的性质有以下几条，相较于AVL树使用平衡因子来限制绝对平衡，红黑树的性质是更加重要的，红黑树能够保证接近平衡的原理是通过这几条性质来对结构进行限制的。

  1. 每个节点的颜色只能是红色或者黑色
  2. 红黑树的根节点是只能是黑色
  1. 如果一个节点是红色的，那么他的孩子节点只能是黑色（这里只说了红节点的孩子不能是红色，没说黑节点的孩子不能是黑色）
  1. 对于任意一个节点，从该节点开始到后叶子节点的简单路径上，黑色节点的个数是相同的（路径是指从该节点开始直到空节点为止，是把空节点也算作一个节点）
  1. 每个叶子节点的颜色都是黑色的（这里的叶子节点指的是空节点）


那么问题来了，为什么这些性质就能够使最长路径的节点个数不会超过最短路径节点个数的两倍？

首先，我们想一想：从一个节点，从它向下的所有到叶子节点的路径上，黑色节点的个数相同的情况下，如果让路径最短，那么就只能让所有节点都是黑色节点，假设有n个，那么最长的路径的情况就是红-黑-红，由于根节点和叶子节点都只能是黑色，所以最长的路径的情况就是一黑一红交替出现，长度最多是2*n，这样就能够确保没有一条路径会比其他路径长出两倍。


2. 红黑树的实现


2.1 节点和结构的定义

首先，由于红黑树是使用红色或者黑色来标志节点的，所以这里可以使用一个枚举类型来对颜色进行限制

enum Color
{
    RED,
    BLACK
};


然后考虑节点的结构，实际上节点的结构和AVL树基本相同，只是不需要平衡因子，而是变成了颜色标识，所以结构如下

template<class K, class V>
struct RBTreeNode
{
    pair<K,V> _kv;
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    Color _col;//颜色
    RBTreeNode(const pair<K,V> kv)//构造函数
        :_kv(kv)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_col(RED)
    {}
};

现在节点的结构已经有了，然后要考虑的就是树的结构，树的结构和AVL树是一样的，只需要一个根节点成员变量即可

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;//为了方便使用，重定义一下节点
public:
    //...
private:
    Node* _root = nullptr;
}

2.2 红黑树的节点插入(重点！！！！)

红黑树的本质还是二叉搜索树，所以插入的过程和二叉搜索树一样，需要先找到插入位置，然后new一个节点插入进去。


然后对于红黑树的特殊结构，需要进行判断，判断插入之后的红黑树的结构是否符合限制条件即可

🤔️插入的节点的默认颜色应该是什么？

✅应该是红色，如果新插入的节点是黑色的话，就一定不会符合条件。因为在插入之前，树的结构肯定是满足红黑树性质的，所以黑色节点的个数是固定的，如果再次插入一个黑色节点的话，那么结构一定会被破坏，但是插入红色节点只是有可能破坏结构，所以这里选择默认插入节点的颜色是红色，然后再判断。


有了上面的基础，现在就可以进入到插入的重点部分——调节了


这里我们假设parent是grandfather的左节点，对于另一种情况也是相同的处理方式，对称过去即可。


1⃣️首先，已知了插入的节点是红色的，默认在插入之前树是一个红黑树，由于条件限制不能出现连续的红色节点，所以需要判断一下parent是否是红色，如果不是，那么就不用做任何操作，插入过程直接完成。


如果parent是红色节点的话，就去看uncle是否是红色，如果也是红色的话，那么就将parent和uncle的颜色变成黑色，然后grandfather变成红色，这样的话grandfather路径下的所有路径的黑色节点个数不会发生改变，也满足了不能出现连续红节点的性质。

8b7a820000abef78725942a916fccc79.png

但是，此时改变了grandfather的颜色，不确定grandfather上面的节点是否满足性质，所以需要向上迭代，把grandfather当作新插入的节点来再次判断，直到满足性质或者到根节点。


❕这里已知cur和parent都是红色时，可以推测出grandfather一定是黑色


2⃣️如果uncle是黑色的话，就不能直接变成红色了，因为要保证每条路径下黑色节点的个数不变，所以如果走到这里，那就说明现在的结构是出现问题的，需要进行调整，这里的调整方式也是进行旋转，这里旋转的方式和AVL树的旋转也是相同的，所以就不赘述了，想了解的话可以看看我的这篇博客链接🔗。这里只需要用到左单旋和右单旋。

这里可以再分为两类：

1⃣️cur是parent的左节点，也就是grandfather、parent、cur在一条直线上

28481ced4228d9809c3573af095fd838.png

此时只需要对grandfather进行右单旋，让parent作为新的”根“节点，然后cur和grandfather分别作为parent的左右子树即可，然后调节一下节点的颜色，让“根”节点——parent变成黑色，其余两个变成红色，然后就完美解决了问题。


2⃣️cur是parent的右节点

6aebdd11b8e177b2cf797c56acb99159.png

此时，可以参考之前对于AVL树的处理，只对grandfather进行一次旋转是不可能解决问题的，所以需要先对parent进行一次左单旋，,此时变成了上一种情况，然后再对grandfather进行一次右单旋，最终的结构就是cur作为parent和grandfather的父节点，然后再处理节点颜色：cur变为黑色，parent和grandfather变成红色。


然后以相同的方式处理parent是grandfather的右节点即可。

最后，再次把根节点的颜色置为黑色，防止前面的各种修改导致根节点的颜色不符合性质。

//红黑树插入代码
bool Insert(const pair<K,V>& kv)
{
  if(_root == nullptr)
  {
    _root = new Node(kv);
    _root->_col = BLACK;
    return true;
  }
  Node* cur = _root;
  Node* parent = nullptr;
  //找到插入位置
  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;
  //连接上
  cur->_parent = parent;
  if(parent->_kv.first > cur->_kv.first)
  {
    parent->_left = cur;
  }
  else
  {
    parent->_right = cur;
  }
  //判断颜色是否合法
  while(parent && cur->_parent->_col == RED)
  {
    Node* grandfather = parent->_parent;
    if(parent == grandfather->_left)//当parent是grandfather左节点
    {
      Node* uncle = grandfather->_right;
      //情况一：uncle存在且为红
      if(uncle && uncle->_col == RED)
      {
        grandfather->_col = RED;
        uncle->_col = parent->_col = BLACK;
        cur = grandfather;
        parent = cur->_parent;
      }
      //出现下面的情况就说明树的结构出现问题，需要对结构进行调整（旋转）
      else//uncle不存，或者在且为黑
      {
        //情况二：grandfather、parent、cur在一条直线上
        if(parent->_left == cur)
        {
          RotateR(grandfather);
          grandfather->_col = RED;
          parent->_col = BLACK;
        }
        //情况二：grandfather、parent、cur在一条折线上
        else
        {
          RotateL(parent);
          RotateR(grandfather);
          cur->_col = BLACK;
          grandfather->_col = RED;
        }
        break;
      }
    }
    else//当parent是grandfather右节点
    {
      Node* uncle = grandfather->_left;
      //情况一：uncle存在且为红
      if(uncle && uncle->_col == RED)
      {
        parent->_col = uncle->_col = BLACK;
        grandfather->_col = RED;
        cur = grandfather;
        parent = cur->_parent;
      }
      else//uncle不存在，或者存在且为黑
      {
        //情况二：grandfather、parent、cur在一条直线上
        if(parent->_right == cur)
        {
          RotateL(grandfather);
          grandfather->_col = RED;
          parent->_col = BLACK;
        }
        //情况二：grandfather、parent、cur在一条折线上
        else
        {
          RotateR(parent);
          RotateL(grandfather);
          grandfather->_col = RED;
          cur->_col = BLACK;
        }
        break;
      }
    }
  }
  _root->_col = BLACK;
  return true;
}
//左单旋
void RotateL(Node* parent)
{
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  Node* ppNode = parent->_parent;
  //处理subRL的部分
  parent->_right = subRL;
  if(subRL)
    subRL->_parent = parent;
  //处理parent和subR之间的关系
  subR->_left = parent;
  parent->_parent = subR;
  //处理subR的parent
  if(ppNode)//parent不是根节点的时候，需要处理parent的父亲节点
  {
    subR->_parent = ppNode;
    if(ppNode->_left == parent)//parent是左节点
    {
      ppNode->_left = subR;
    }
    else//parent是右节点
    {
      ppNode->_right = subR;
    }
  }
  else//parent是根节点的时候
  {
    _root = subR;
    subR->_parent = nullptr;
  }
}
//右单旋
void RotateR(Node* parent)
{
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  Node* ppNode = parent->_parent;
  if(subLR)
    subLR->_parent = parent;
  parent->_left = subLR;
  subL->_right = parent;
  parent->_parent = subL;
  if(ppNode)
  {
    subL->_parent = ppNode;
    if(ppNode->_left == parent)
      ppNode->_left = subL;
    else
      ppNode->_right = subL;
  }
  else
  {
    _root = subL;
    subL->_parent = nullptr;
  }
}

补充说明：红黑树节点的删除

同样的，这里不做讲解，有兴趣的小伙伴可以去参考一下《算法导论》或者《STL源码剖析》

同时，这里推荐一篇博客：博客链接


3. 红黑树的验证与性能分析


3.1红黑树的验证

红黑树首先一定是一个二叉搜索树，所以这里首先对树进行中序遍历，判断遍历结果是否是有序的，如果是有序的证明是二叉搜索树，然后再对其进行红黑树特有性质的判断；


红黑树没有办法直接判断，由于红黑树的结构是由多条性质来对结构进行限制的，所以这里可以通过对每条性质的判断来做到判断红黑树的结构


  1. 针对第一条性质，在实现的时候使用了枚举的方式就已经限制过了，所以不需要再次判断
  2. 对于第二条性质，直接判断即可
  3. 对于第五条性质，直接这样理解即可，因为空节点实际上没有颜色
  4. 对于第三条性质，这里建议去判断该节点的颜色与其父节点的颜色而不是子节点，因为父节点只有一个，更加方便
  5. 对于第四条性质，这里可以首先任选一条路径，计算出从根节点开始直到叶子节点的黑色节点个数ref，然后使用DFS遍历所有路径，计算黑色节点个数与ref比较，如果不相等就返回false。
//红黑树的验证代码
void InOrder(vector<pair<K,V>>& v, Node* root)//中序遍历
{
  if(root == nullptr)
    return;
  InOrder(v, root->_left);
  v.push_back(root->_kv);
  InOrder(v, root->_right);
}
bool isBSTree(Node* root)//判断是否是二叉搜索树
{
  vector<pair<K,V>> v;
  InOrder(v,root);
  for(size_t i = 0; i < v.size() - 1; ++i)
  {
    if(v[i].first > v[i+1].first)
      return false;
  }
  return true;
}
bool Check(Node* root, int blackNum, int ref)
{
  if(root == nullptr)//如果已经是空树，那么判断当前路径黑色节点个数与其他路径是否相等
  {
    if(blackNum != ref)
    {
      cout << "count of black is error" << endl;
      return false;
    }
    return true;
  }
  if(root->_col == RED && root->_parent->_col == RED)//判断当前节点与父节点的颜色是否都是红色
  {
    cout << "more red node" << endl;
    return false;
  }
  if(root->_col == BLACK)//如果当前节点是黑色，就在当前路径黑节点个数下加一
    ++blackNum;
  return Check(root->_left, blackNum, ref)
    && Check(root->_right, blackNum, ref);
}
bool isRBTree()
{
  if(_root == nullptr)//空树也是红黑树
    return true;
  if(isBSTree(_root))//判断是否是二叉搜索树
  {
    if(_root->_col != BLACK)//判断根节点是否是黑色，如果不是直接返回false
      return false;
    //计算出当前节点下的其中一个路径下黑色节点的个数
    int ref = 0;
    Node* left = _root;
    while(left)
    {
      if(left->_col == BLACK)
        ++ref;
      left = left->_left;
    }
    //判断是否满足对于任意节点下的所有路径下黑色节点个数是否相等
    return Check(_root, 0, ref);
  }
  else
    return false;
}

3.2红黑树的性能分析——与AVL树的对比

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(l o g 2 N log_2 Nlog

2

N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。


3.3红黑树的应用

  1. C++ STL库——map/set、mutil_map/mutil_set
  2. Java 库
  3. Linux内核
  4. 其他一些库

最后，附上本节源码

/***********RBTree.hpp****************/
//
//  RBTree.hpp
//  RBTree
//
//  Created by zht on 2023/5/14.
//
#pragma once
#include <iostream>
using namespace std;
enum Color
{
    RED,
    BLACK
};
template<class K, class V>
struct RBTreeNode
{
    pair<K,V> _kv;
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    Color _col;
    RBTreeNode(const pair<K,V> kv)
        :_kv(kv)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_col(RED)
    {}
};
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* cur = _root;
        Node* parent = nullptr;
        //找到插入位置
        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;
        //连接上
        cur->_parent = parent;
        if(parent->_kv.first > cur->_kv.first)
        {
            parent->_left = cur;
        }
        else
        {
            parent->_right = cur;
        }
        //判断颜色是否合法
        while(parent && cur->_parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            if(parent == grandfather->_left)//当parent是grandfather左节点
            {
                Node* uncle = grandfather->_right;
                //情况一：uncle存在且为红
                if(uncle && uncle->_col == RED)
                {
                    grandfather->_col = RED;
                    uncle->_col = parent->_col = BLACK;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                //出现下面的情况就说明树的结构出现问题，需要对结构进行调整（旋转）
                else//uncle不存，或者在且为黑
                {
                    //情况二：grandfather、parent、cur在一条直线上
                    if(parent->_left == cur)
                    {
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    //情况二：grandfather、parent、cur在一条折线上
                    else
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else//当parent是grandfather右节点
            {
                Node* uncle = grandfather->_left;
                //情况一：uncle存在且为红
                if(uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//uncle不存在，或者存在且为黑
                {
                    //情况二：grandfather、parent、cur在一条直线上
                    if(parent->_right == cur)
                    {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    //情况二：grandfather、parent、cur在一条折线上
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return true;
    }
    void RotateL(Node* parent)//左单旋
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        Node* ppNode = parent->_parent;
        //处理subRL的部分
        parent->_right = subRL;
        if(subRL)
            subRL->_parent = parent;
        //处理parent和subR之间的关系
        subR->_left = parent;
        parent->_parent = subR;
        //处理subR的parent
        if(ppNode)//parent不是根节点的时候，需要处理parent的父亲节点
        {
            subR->_parent = ppNode;
            if(ppNode->_left == parent)//parent是左节点
            {
                ppNode->_left = subR;
            }
            else//parent是右节点
            {
                ppNode->_right = subR;
            }
        }
        else//parent是根节点的时候
        {
            _root = subR;
            subR->_parent = nullptr;
        }
    }
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        Node* ppNode = parent->_parent;
        if(subLR)
            subLR->_parent = parent;
        parent->_left = subLR;
        subL->_right = parent;
        parent->_parent = subL;
        if(ppNode)
        {
            subL->_parent = ppNode;
            if(ppNode->_left == parent)
                ppNode->_left = subL;
            else
                ppNode->_right = subL;
        }
        else
        {
            _root = subL;
            subL->_parent = nullptr;
        }
    }
    void InOrder(vector<pair<K,V>>& v, Node* root)
    {
        if(root == nullptr)
            return;
        InOrder(v, root->_left);
        v.push_back(root->_kv);
        InOrder(v, root->_right);
    }
    bool isBSTree(Node* root)
    {
        vector<pair<K,V>> v;
        InOrder(v,root);
        for(size_t i = 0; i < v.size() - 1; ++i)
        {
            if(v[i].first > v[i+1].first)
                return false;
        }
        return true;
    }
    bool Check(Node* root, int blackNum, int ref)
    {
        if(root == nullptr)
        {
            if(blackNum != ref)
            {
                cout << "count of black is error" << endl;
                return false;
            }
            return true;
        }
        if(root->_col == RED && root->_parent->_col == RED)
        {
            cout << "more red node" << endl;
            return false;
        }
        if(root->_col == BLACK)
            ++blackNum;
        return Check(root->_left, blackNum, ref)
            && Check(root->_right, blackNum, ref);
    }
    bool isRBTree()
    {
        if(_root == nullptr)
            return true;
        if(isBSTree(_root))
        {
            if(_root->_col != BLACK)//判断性质2
                return false;
            int ref = 0;
            Node* left = _root;
            while(left)
            {
                if(left->_col == BLACK)
                    ++ref;
                left = left->_left;
            }
            return Check(_root, 0, ref);
        }
        else
            return false;
    }
private:
    Node* _root = nullptr;
};
/***********Test.cpp****************/
#include <iostream>
#include <time.h>
#include "RBTree.hpp"
using namespace std;
void TestRBTree1()
{
//    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//    int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    RBTree<int, int> t;
    for (auto e : a)
    {
        t.Insert(make_pair(e, e));
    }
    cout << t.isRBTree() << endl;
}
void TestRBTree2()
{
    srand(time(0));
    const size_t N = 10;
    RBTree<int, int> t;
    for (size_t i = 0; i < N; ++i)
    {
        size_t x = rand() % 100;
        //cout << x << ":";
        t.Insert(make_pair(x, x));
        //cout << t.isRBTree() << endl;
    }
    cout << t.isRBTree() << endl;
}
int main()
{
    TestRBTree1();
    TestRBTree2();
    return 0;
}

本节完。。。

文章标签：
C++
Java
Linux
算法
关键词：
数据结构红黑树
小张在努力写代码
目录
相关文章
起飞的风筝
|
算法 C++
【数据结构与算法】—— 手撕红黑树
【数据结构与算法】—— 手撕红黑树
起飞的风筝
40 0
jerrywangsap
|
2月前
|
存储 Java 数据库
手撕红黑树 - 聊聊这个基本却又重要的数据结构
手撕红黑树 - 聊聊这个基本却又重要的数据结构
jerrywangsap
21 0
慕斯(˘▽˘)っ
|
4月前
|
存储 关系型数据库 数据库
【数据结构】—红黑树（C++实现）
【数据结构】—红黑树（C++实现）
慕斯(˘▽˘)っ
37 0
我是廖志伟
|
7月前
|
存储 Java 数据库
【红黑树数据结构及其应用】
【红黑树数据结构及其应用】
我是廖志伟
63 0
lingeringfear
|
7月前
|
存储
数据结构之二叉查找树(Binary Search Tree)和红黑树(Red Black Tree)
二叉查找树又可以称之为 : 二叉搜索树 , 二叉排序树 , 它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势 , 下图中这棵树，就是一棵典型的二叉查找树
lingeringfear
114 1
&zeta;◇十点半就睡觉
|
7月前
|
关系型数据库
【数据结构】红黑树
【数据结构】红黑树
&zeta;◇十点半就睡觉
36 0
盒马盒马
|
1天前
|
存储 算法 Java
数据结构/C++：红黑树
数据结构/C++：红黑树
盒马盒马
10 3
Bigcrab__
|
1天前
|
存储 缓存 算法
数据结构与算法 树（B树，B+树，红黑树待完善）
数据结构与算法 树（B树，B+树，红黑树待完善）
Bigcrab__
7 0
游客tvcyhbd42sol2
|
4天前
数据结构===红黑树
红黑树是平衡二叉搜索树，关键点在于其满足5个性质，包括根节点为黑，叶子为黑，红色节点不能相邻且路径上黑节点数相等。插入和删除时结合左旋、右旋操作。插入时，针对叔叔节点颜色（红或黑），参照AVL树的失衡处理，分为4种情况，并调整颜色策略。删除操作同样复杂，涉及节点替换和颜色调整。
游客tvcyhbd42sol2
10 1
测试技术 数据库
21 3