数据结构——红黑树

简介: 数据结构——红黑树



一、概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。(并不是像AVL树那样高度差一定不超过1)。

最长路径长度不超过最短路径长度的 2 倍。

如下图就是一棵红黑树:

 

注:树的路径是从根节点走到NIL节点才算一条路径。


二、红黑树的性质

1、 每个结点不是红色就是黑色。

2、根节点是黑色的

3、如果一个节点是红色的,则它的两个孩子结点是黑色的。(没有连续的红色结点)

4、 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。

5、每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。


三、结点的实现

在结点的实现中,我们要需要一个变量来控制它的颜色,因此我们可以使用枚举来列出两种颜色,再在结点中定义颜色。

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, Colour col = RED)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _col(col)
  {}
};

上面的代码我们在创建结点后,就直接将新节点的颜色默认设置成了红色,那么为什么要默认设置成红色,而不是黑色呢?

首先,如果我们插入黑色结点,将会违背性质4,因为某条路径上一定会多出一个黑色结点,这样就需要去调节所有路径的黑色结点,非常麻烦。

如果我们插入的是红色结点,那么我们就可能违背了性质3,因为如果新插入结点的父亲是黑色那么我们就不需要进行调整。

所以总的来说,新插入结点是红色,红黑树的结构维护起来更加方便。


四、红黑树的插入

一般步骤:

1、按照二叉搜索的树规则插入新节点(即:插入值与结点值比较,小于节点值就往左子树插入,反之往右子树插入)。

2、判断红黑树的结构是否被破坏:

因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何

性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连

在一起的红色节点,此时需要对红黑树分情况来讨论:(cur为当前结点,p为父亲结点,g为祖父结点,u为叔叔结点)。

* 情况一:cur为红,p为红,g为黑,u存在且为红

该情况的处理方式为:将P和U结点变黑,再将g变红。

如果g是根节点,调整完成后,要将g改为黑色,如果g是子树,那么如果g的双亲是红色,就需要然后把g当成cur,继续向上调整。

* 情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑,g/p/cur在同一侧

此时u的情况有两种:

1、如果u结点不存在,则cur一定是新增结点,因为如果cur不是新增结点:则cur和p一定有一个节点时黑色,就不满足每条路径都有相同的黑色结点的性质。

2、如果u结点存在,则其一定是黑色的,那么cur节点原来的颜色一定是黑色,在其子树调整过程中变为了红色。

p为g的左孩子,cur为p的左孩子,则进行右单旋;相反,p为g的右孩子,cur为p的右孩子,则进行左单旋。p变为黑色,g变为红色。

* 情况三:cur为红,p为红,g为黑,u不存在/u存在且为黑,g/p/cur不在同一侧

p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;相反,p为g的右孩子,cur为p的左孩子,则针对p做右单旋转 。旋转之后则转换成了情况二,再继续进行调整即可。

代码实现如下:

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->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    while (parent && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;
      assert(grandfather);
      assert(grandfather->_col == BLACK);
      if (parent == grandfather->_left)
      {
        Node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        // uncle 不存在 + 存在且为黑
        else
        {
          if (cur == parent->_left)
          {
            RotateR(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_right)
          {
            RotateL(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    _root->_col = BLACK;
    return true;
  }

五、完整代码

RBTree.h

#pragma once
#include<iostream>
#include<cassert>
using namespace std;
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, Colour col = RED)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _col(col)
  {}
};
template<class K, class V>
struct 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);
    if (parent->_kv.first > kv.first)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    while (parent && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;
      assert(grandfather);
      assert(grandfather->_col == BLACK);
      if (parent == grandfather->_left)
      {
        Node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        // uncle 不存在 + 存在且为黑
        else
        {
          if (cur == parent->_left)
          {
            RotateR(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_right)
          {
            RotateL(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    _root->_col = BLACK;
    return true;
  }
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
private:
  void RotateL(Node* parent) //左单旋
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* pparent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
    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;
    Node* pparent = parent->_parent;
    parent->_parent = subL;
    subL->_right = parent;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    if (parent == _root)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
        pparent->_left = subL;
      else
        pparent->_right = subL;
      subL->_parent = pparent;
    }
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
      return;
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }
private:
  Node* _root = nullptr;
};
void test()
{
  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));
  }
  t.InOrder();
}

test.cpp

#include"RBTree.h"
int main()
{
  test();
  return 0;
}

运行结果:

目录
相关文章
|
6月前
|
算法 C++
【数据结构与算法】—— 手撕红黑树
【数据结构与算法】—— 手撕红黑树
|
6月前
|
存储 关系型数据库 数据库
【数据结构】—红黑树(C++实现)
【数据结构】—红黑树(C++实现)
|
关系型数据库
|
3月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
102 1
【数据结构】红黑树——领略天才的想法
【数据结构】红黑树——领略天才的想法
|
1月前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
29 0
|
6月前
【数据结构】红黑树的原理及其实现
【数据结构】红黑树的原理及其实现
|
3月前
|
存储 Java 程序员
"揭秘HashMap底层实现:从数组到链表,再到红黑树,掌握高效数据结构的秘密武器!"
【8月更文挑战第21天】HashMap是Java中重要的数据结构,采用数组+链表/红黑树实现,确保高效查询与更新。构造方法初始化数组,默认容量16,负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素,利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制,提升性能。理解这些原理能帮助我们更高效地应用HashMap。
45 0
|
5月前
|
算法 架构师 NoSQL
【数据结构之红黑树】深入原理与实现
意节点的左子树和右子树的层高差不大于1,为了维护树的平衡,我们介绍了树的左右旋转。但是,AVL树维护平衡的代价是比较大的。所以,我们又介绍了红黑树这种数据结构,这是因为红黑树插入的效率相对AVL树是比较高的,在统计意义上来讲红黑树在插入和查找综合上效率是比较高的,这也是为什么红黑树为什么广泛应用在计算机各个方面。
50 2
|
5月前
|
C++
数据结构===红黑树
数据结构===红黑树

热门文章

最新文章