【C++】红黑树的简单模拟实现

简介: 红黑树和AVL树类似,是对搜索树的优化。不同于AVL树的绝对平衡,红黑树是近似平衡,即对于每个节点的以它为根的所有路径,其中最长路径的节点数不大于最短路径节点数的2倍。

一. 什么是红黑树?


1. 基本概念


红黑树和AVL树类似,是对搜索树的优化。不同于AVL树的绝对平衡,红黑树是近似平衡,即对于每个节点的以它为根的所有路径,其中最长路径的节点数不大于最短路径节点数的2倍。


2. 红黑树的特性


  • 每个节点不是红色就是黑色,其中根节点为黑
  • 红色节点不连续,即红色节点的左右孩子只能为黑色
  • 每个节点,以它为根的所有路径中黑色节点的数量相同

以上特性,就是红黑树近似平衡的原因:

  1. 红色节点不连续,说明最短路径的节点都是黑色,最长路径的节点是红黑相间。
  2. 每条路径节的黑色节点个数必须相同,决定了最短路径不超过最长路径的2倍。

b7738de2dc624a8c9af8bf0bb2f7e4c5.png


二. 为什么要有红黑树?


为什么要有红黑树?下面通过红黑树和搜索树、平衡树的比较来回答这个问题。


1. 红黑树和搜索树


当插入有序数据时,搜索树会退化为单枝树从而导致查找效率降为线性。红黑树通过对各个节点颜色的控制和位置的调整,使得树永远处于近似平衡状态,保证了O(logN)的查找效率。

7add1d39664840d1ac8f70b932b043a0.png


2. 红黑树和平衡树


二者都是对搜索树进行了平衡处理

  • 平衡树是绝对平衡:左右子树高度差的绝对值小于等于1
  • 红黑树是近似平衡:最长路径不大于最短路径的2倍

红黑树不追求绝对平衡,相对平衡树而言降低了插入和删除时旋转的次数,频繁的插入删除红黑树的性能更优,并且红黑树的实现也较为简单,所以实际运用中红黑树更多。如果插入删除的操作较少且需要频繁的查找,那么平衡树性能更优。


三. 红黑树插入操作实现


1. 基本框架


主要定义里两个类:节点类 + 树的本体,其中前者存储节点节点的相关信息,后者主要实现红黑树的功能,如插入、删除、查找等。


1.1 节点类框架


数据域:颜色(默认为红)、pair键值对

指针域:左孩子和右孩子、父亲

// 枚举定义颜色
enum COLOR
{
  RED,
  BLACK
};
// 节点的定义
template<class k, class v>
struct RBTreeNode
{
  // 构造函数,颜色默认给为红色
  RBTreeNode(const pair<k, v>& kv)
    :_color(RED)
    ,_kv(kv)
    ,_parent(nullptr)
    ,_left(nullptr)
    ,_right(nullptr)
  {}
  COLOR _color;
  pair<k, v> _kv;
  RBTreeNode<k, v>* _parent;
  RBTreeNode<k, v>* _left;
  RBTreeNode<k, v>* _right;
};

为什么颜色默认为红色?

因为红色处理起来更简单,对其他路径的波及较小。如果为黑色,想想看这条路径的黑色节点数量加了一个,那么其他路径都要调整来保证所有路径的黑色节点个数一致;但是如果置为红色,这时只有插入位置的父亲也为红才需要调整,即使调整也只需调整一条路径,比较容易。


1.2 树本体框架


只有一个成员变量就是一个节点的指针,代表树的根节点。也为只有一个成员变量,可以不用写构造函数,我们直接声明时给缺省值即可,就是把它置为nullptr。

// 树的定义
template<class k, class v>
class RBTree
{
public:
  typedef RBTreeNode<k, v> Node;
private:
  Node* _root = nullptr;// 声明时给缺省值
};

2. 第一步:按搜索树性质插入节点

按搜索树的性质来找到插入的位置,然后直接插入:

  • 如果是空树,则则该插入节点就作为整棵树的根,并把颜色改为黑色
  • 非空的话,按照搜索树的性质找到插入的位置和并记录父亲,然后和父亲的key比较来决定作为左孩子还是右孩子。
template<class k, class v>
class RBTree 
{
  public:
    typedef RBTreeNode<k, v> Node;
    bool Insert(const pair<k, v>& kv)
    {
      // 第一步:按搜索树规则插入一个节点
      // 1、空树的话插入节点作为根节点
      // 2、不空的话,按搜索树规则找到插入的位置,然后插入
      if(!_root)
      {
        _root=new Node(kv);
        _root->_color=BLACK;
        return true;
      }
      // 寻找插入的位置
      Node* parent=nullptr;
      Node* cur=_root;
      while(cur)
      {
        parent=cur;
        if(cur->_kv.first == kv.first)
        {
          return false;
        }
        else if(cur->_kv.first < kv.first)
        {
          cur=cur->_right;
        }
        else if(cur->_kv.first > kv.first)
        {
          cur=cur->_left;
        }
      }
      // 找到后插入
      Node* newNode=new Node(kv);
      newNode->_parent=parent;
      if(parent->_kv.first > kv.first)
      {
        parent->_left=newNode;
      }
      else if(parent->_kv.first < kv.first) 
      {
        parent->_right=newNode;
      }
      // 未完待续.....
  private:
    Node* _root=nullptr;
};


3. 第二步:调整节点的颜色


3.1 调整操作


走到了这一步,那么插入节点肯定不是整棵树的根了,因为空树情况在第一步里面已经处理好了,也就是说现在插入的新节点一定有父亲。根据父亲的颜色分两种情况处理:

  1. 情况一:父亲颜色为黑。这种情况就不用调整了,插入结束。
  2. 情况二:父亲颜色为红。需要调整

针对情况二,我们需要知道,这时一定是有祖父节点的,即父亲的父亲一定存在且为黑色,因为父亲的颜色为红不可能是根节点,又因为红色不连续所以祖父为黑。这时我们的调整取决于叔叔,当然叔叔可能存在也可能不存在,我们分情况处理。

约定插入节点为cur,父亲为parent,祖父为gfather,叔叔为uncle,此时:

uncle存在且为红 --》 把parent和uncle的颜色到改为黑,gfather颜色改为红,从gfather开始继续往上调整。

3709d0a112a045309d9654e0c915b80e.png

uncle 不存在 or 存在且为黑 --》依照gfather、parent、cur的关系来旋转处理。

09d436c87060438789719759b7aac429.png

// 拼接到第一步代码后面
// 第二步:调整节点的颜色
// 1、如果父亲颜色为黑就不用调整
// 2、如果父亲节点颜色为红,调整方式由叔叔决定
//    a、叔叔存在且为红 --> 把叔叔和父亲的颜色调整为黑,爷爷颜色调整为红,然后继续往上调整
//    b、叔叔不存在或存在且为黑 --> 看爷爷、父亲、和cur的相对位置来决定用什么旋转,旋转后交换父亲和爷爷的颜色
cur=newNode;
while(parent &&  parent->_color == RED)
{
  // 既然进来了这个循环内部,说明父亲一定是红色,那么一定有爷爷且爷爷颜色为黑
  Node* grandfather = parent->_parent;
  // 确定叔叔的位置
  if(grandfather->_left == parent)
  {
    Node* uncle=grandfather->_right;
    if(uncle && uncle->_color == RED)// 叔叔存在且为红
    {
      parent->_color=uncle->_color=BLACK;
      grandfather->_color=RED;
      cur=grandfather;
      parent=cur->_parent;
    }
    else // 叔叔不存在或者存在且为黑
    {
      if(cur == parent->_right)
      {
        RotateL(parent);
        std::swap(parent,cur);
      }
      RotateR(grandfather);
      parent->_color=BLACK;
      grandfather->_color=RED;
      break;
    }
  }
  else if(grandfather->_right == parent)
  {
    Node* uncle=grandfather->_left;
    if(uncle && uncle->_color==RED)// 叔叔存在且为红
    {
      uncle->_color=parent->_color=BLACK;
      grandfather->_color=RED;
      cur=grandfather;
      parent=cur->_parent;
    }
    else // 叔叔不存在或存在且为黑
    {
      if(cur == parent->_left)
      {
        RotateR(parent);
        std::swap(parent,cur);
      }
      RotateL(grandfather);
      parent->_color=BLACK;
      grandfather->_color=RED;
      break;
    }
  }
}
_root->_color=BLACK;
}
// 左单旋
void RotateL(Node* parent)
{
  Node* subR=parent->_right;
  Node* subRL=subR->_left;
  parent->_right=subRL;
  if(subRL != nullptr)
  {
    subRL->_parent=parent;
  }
  subR->_left=parent;
  Node* pparent=parent->_parent;
  parent->_parent=subR;
  if(pparent == nullptr)
  {
    _root=subR;
    subR->_parent=nullptr;
  }
  else 
  {
    subR->_parent=pparent;
    if(pparent->_left == parent)
    {
      pparent->_left=subR;
    }
    else if(pparent->_right == parent)
    {
      pparent->_right=subR;
    }
  }
}
// 右单旋
void RotateR(Node* parent)
{
  Node* subL=parent->_left;
  Node* subLR=subL->_right;
  parent->_left=subLR;
  if(subLR != nullptr)
  {
    subLR->_parent=parent;
  }
  subL->_right=parent;
  Node* pparent=parent->_parent;
  parent->_parent=subL;
  if(pparent == nullptr)
  {
    _root=subL;
    subL->_parent=nullptr;
  }
  else 
  {
    subL->_parent=pparent;
    if(pparent->_left == parent)
    {
      pparent->_left=subL;
    }
    else if(pparent->_right == parent) 
    {
      pparent->_right=subL;
    }
  }


3.3 调整总结


73322b03c8c3472f886904ff54b76bb1.png

4. 完整代码

#pragma once
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using std::pair;
// 枚举定义颜色
enum COLOR
{
  RED,
  BLACK
};
// 节点的定义
template<class k, class v>
struct RBTreeNode
{
  // 构造函数,颜色默认给为红色
  RBTreeNode(const pair<k, v>& kv)
    :_color(RED)
    ,_kv(kv)
    ,_parent(nullptr)
    ,_left(nullptr)
    ,_right(nullptr)
  {}
  COLOR _color;
  pair<k, v> _kv;
  RBTreeNode<k, v>* _parent;
  RBTreeNode<k, v>* _left;
  RBTreeNode<k, v>* _right;
};
// 树的定义
template<class k, class v>
class RBTree 
{
  public:
    typedef RBTreeNode<k, v> Node;
    // 插入一个节点
    bool Insert(const pair<k, v>& kv)
    {
      // 第一步:按搜索树规则插入一个节点
      // 1、空树的话插入节点作为根节点
      // 2、不空的话,按搜索树规则找到插入的位置,然后插入
      if(!_root)
      {
        _root=new Node(kv);
        _root->_color=BLACK;
        return true;
      }
      // 寻找插入的位置
      Node* parent=nullptr;
      Node* cur=_root;
      while(cur)
      {
        parent=cur;
        if(cur->_kv.first == kv.first)
        {
          return false;
        }
        else if(cur->_kv.first < kv.first)
        {
          cur=cur->_right;
        }
        else if(cur->_kv.first > kv.first)
        {
          cur=cur->_left;
        }
      }
      // 找到后插入
      Node* newNode=new Node(kv);
      newNode->_parent=parent;
      if(parent->_kv.first > kv.first)
      {
        parent->_left=newNode;
      }
      else if(parent->_kv.first < kv.first) 
      {
        parent->_right=newNode;
      }
      // 第二步:调整节点的颜色
      // 1、如果父亲颜色为黑就不用调整
      // 2、如果父亲节点颜色为红,调整方式由叔叔决定
      //    a、叔叔存在且为红 --> 把叔叔和父亲的颜色调整为黑,爷爷颜色调整为红,然后继续往上调整
      //    b、叔叔不存在或存在且为黑 --> 看爷爷、父亲、和cur的相对位置来决定用什么旋转,旋转后交换父亲和爷爷的颜色
      cur=newNode;
      while(parent &&  parent->_color == RED)
      {
        // 既然进来了这个循环内部,说明父亲一定是红色,那么一定有爷爷且爷爷颜色为黑
        Node* grandfather = parent->_parent;
        // 确定叔叔的位置
        if(grandfather->_left == parent)
        {
          Node* uncle=grandfather->_right;
          if(uncle && uncle->_color == RED)// 叔叔存在且为红
          {
            parent->_color=uncle->_color=BLACK;
            grandfather->_color=RED;
            cur=grandfather;
            parent=cur->_parent;
          }
          else // 叔叔不存在或者存在且为黑
          {
            if(cur == parent->_right)
            {
              RotateL(parent);
              std::swap(parent,cur);
            }
            RotateR(grandfather);
            parent->_color=BLACK;
            grandfather->_color=RED;
            break;
          }
        }
        else if(grandfather->_right == parent)
        {
          Node* uncle=grandfather->_left;
          if(uncle && uncle->_color==RED)// 叔叔存在且为红
          {
            uncle->_color=parent->_color=BLACK;
            grandfather->_color=RED;
            cur=grandfather;
            parent=cur->_parent;
          }
          else // 叔叔不存在或存在且为黑
          {
            if(cur == parent->_left)
            {
              RotateR(parent);
              std::swap(parent,cur);
            }
            RotateL(grandfather);
            parent->_color=BLACK;
            grandfather->_color=RED;
            break;
          }
        }
      }
      _root->_color=BLACK;
    }
 private:
    // 左单旋
    void RotateL(Node* parent)
    {
      Node* subR=parent->_right;
      Node* subRL=subR->_left;
      parent->_right=subRL;
      if(subRL != nullptr)
      {
        subRL->_parent=parent;
      }
      subR->_left=parent;
      Node* pparent=parent->_parent;
      parent->_parent=subR;
      if(pparent == nullptr)
      {
        _root=subR;
        subR->_parent=nullptr;
      }
      else 
      {
        subR->_parent=pparent;
        if(pparent->_left == parent)
        {
          pparent->_left=subR;
        }
        else if(pparent->_right == parent)
        {
          pparent->_right=subR;
        }
      }
    }
    // 右单旋
    void RotateR(Node* parent)
    {
      Node* subL=parent->_left;
      Node* subLR=subL->_right;
      parent->_left=subLR;
      if(subLR != nullptr)
      {
        subLR->_parent=parent;
      }
      subL->_right=parent;
      Node* pparent=parent->_parent;
      parent->_parent=subL;
      if(pparent == nullptr)
      {
        _root=subL;
        subL->_parent=nullptr;
      }
      else 
      {
        subL->_parent=pparent;
        if(pparent->_left == parent)
        {
          pparent->_left=subL;
        }
        else if(pparent->_right == parent) 
        {
          pparent->_right=subL;
        }
      }
    }
    Node* _root=nullptr;
};
相关文章
|
7月前
|
C++
c++的学习之路:27、红黑树
c++的学习之路:27、红黑树
54 4
|
7月前
|
测试技术 C++
C++进阶--红黑树
C++进阶--红黑树
|
7月前
|
编译器 C++ 容器
【C++学习手札】基于红黑树封装模拟实现map和set
【C++学习手札】基于红黑树封装模拟实现map和set
|
7月前
|
存储 关系型数据库 数据库
【数据结构】—红黑树(C++实现)
【数据结构】—红黑树(C++实现)
|
7月前
|
C++ 容器
【C++】红黑树模拟实现STL中的map与set
【C++】红黑树模拟实现STL中的map与set
|
4月前
|
关系型数据库 C++ 容器
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——红黑树
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——红黑树
37 0
|
5月前
|
Java C++ Python
【C++】手撕红黑树
【C++】手撕红黑树
28 1
|
7月前
|
Java C语言 C++
从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现(上)
从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现
57 4
|
7月前
|
C语言
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现(下)
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现
49 3
|
6月前
|
关系型数据库 C++
【c++】红黑树
【c++】红黑树
24 0