深入解析红黑树(RB-Tree):原理、操作及应用

2024-03-18 08:12

本文主要是介绍深入解析红黑树(RB-Tree):原理、操作及应用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、红黑树的特点与性质
  • 二、红黑树的实现
    • 1、实现红黑树的插入操作
    • 2、红黑树的验证方法
      • a. Check 函数
      • b. IsBalance 函数

红黑树作为一种自平衡的二叉搜索树,在计算机科学领域中占据着重要的地位。它的设计旨在在维持树的平衡性的同时,保证各种操作的时间复杂度始终稳定在较低水平。红黑树的灵活性和高效性使得它成为众多编程语言和系统实现中不可或缺的数据结构之一。本文将带领读者深入探究红黑树的结构与原理。(c++实现)

一、红黑树的特点与性质

  • 红黑树的定义与性质

红黑树是一种特殊的自平衡二叉查找树,它通过颜色和一系列性质来确保树的平衡,从而实现高效的查找、插入和删除操作。在红黑树中,每个节点都被赋予红色或黑色的颜色,并且这些颜色与树的五个基本性质一起工作,共同维持树的平衡。

红黑树是具有着色性质的二叉搜索树:

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点是黑色。
  3. 每个叶子节点(通常称为NIL或空节点)是黑色。在大多数实现中,叶子节点不实际存储,而是用NIL或空指针表示。
  4. 如果一个节点是红色的,则它的两个子节点都是黑色的(即,不能有两个相邻的红色节点)。
  5. 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点。

这些性质共同确保了红黑树的平衡性。特别是性质5,它树确保没有一条路 径会比其他路径长出两倍。这种平衡性保证了红黑树在查找、插入和删除操作中的时间复杂度都是O(log n),其中n是树中节点的数量。着色法则的一个推论是,红黑树的高度最多是 2log(n+1) 。因此,查找保证是一种对数级别的操作。

在这里插入图片描述

有 n 个节点的红黑树的高度最多是 2log(n+1),这是为什么呢?

首先我们来我们考虑一个问题,根节点为黑高为 h 的红黑树,内部节点个数至少有多少个?(黑高:从某节点出发(不含该节点)到达任意一叶节点的路径上黑节点的总数。)

内部节点上最少的情况就是总共 h 层黑节点的满树形态。若根节点黑高为 h,内部节点数最少有 2h-1 个。因此,若红黑树总高度为 h ,则根节点的黑高肯定是大于等于 h/2 的,因此内部节点数 n >= 2h/2-1,由此推出 h <= 2log(n+1) 。

  • 红黑树与AVL树的对比

红黑树同AVL树类似,也是一种自平衡的二叉搜索树,它通过颜色和一系列性质来维护树的平衡性。与AVL树不同的是,红黑树并不追求完全的平衡,而是允许局部的不平衡,这使得红黑树在插入或删除节点时的旋转操作次数较少,降低了操作的复杂性。同时,红黑树的查找、插入和删除操作的时间复杂度也能保持在O(log n)。由于红黑树的这种特性,它在需要频繁进行插入和删除操作的应用场景中表现得更好。

总的来说,红黑树在平衡性、操作复杂性和性能之间找到了一个较好的平衡点,使得它在许多实际应用中成为了一个优秀的选择。而AVL树虽然具有严格的平衡性,但由于其操作的复杂性以及在实际应用中的效率问题,使得它的使用范围相对较小。普通二叉搜索树虽然简单,但在数据动态变化的情况下,其性能可能会受到影响。因此,在选择使用哪种树形结构时,需要根据具体的应用场景和需求进行权衡。 关于AVL树的内容,大家可以点击这里。


二、红黑树的实现

  • 定义红黑树节点的结构体

在此我们定义一个模板结构体RBTreeNode,它是红黑树中的一个节点。红黑树是一种自平衡的二叉搜索树,其中每个节点都带有颜色属性(红色或黑色)。Colour的枚举类型,它有两个值:REDBLACK。这个枚举类型用于表示红黑树中节点的颜色:

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), _col(RED){}
};

_left_right_parent都初始化为nullptr,表示新节点最初没有子节点或父节点。 _kv初始化为传入的键值对kv_col初始化为RED,表示新创建的节点默认是红色的。

为什么要默认是红色呢?

红黑树的困难在于将一个新的值插入到树中,通常把新的值作为树叶放到树中。如果插入时把该节点作为黑色,那么一定违反性质5,因为会建立一条更长的黑节点的路径。因此,该节点必须涂成红色。因此我们在构造函数里将其颜色初始化为红色。

template<class K,class V>
class RBTree {typedef RBTreeNode<K, V> Node;
public://...
private:Node* _root = nullptr;
};

1、实现红黑树的插入操作

在找到插入位置时,如果父节点是黑的,插入完成,因为插入红色节点不会违反性质5。如果它的父节点已经是红色的,那么我们得到连续红色节点,这就违反性质4。在这种情况下,我们必须调整该树以确保性质4满足(且不引起性质5被破坏)。因此我们在插入时需要的基本操作是节点颜色的改变以及树的旋转:

bool Insert(const pair<K, V>& kv) ;

  1. 找到插入位置:我们遍历红黑树,找到新节点应该插入的位置。这通常是通过比较新节点的键与当前节点的键来完成的,直到找到一个空位置(即叶子节点的子节点位置)为止。在这个过程中,我们还记录了新节点的父节点,以便后续操作。

  2. 插入新节点:一旦找到插入位置,我们将新节点插入到树中。这涉及到将新节点的父节点指针指向之前记录的父节点,并根据新节点的键值更新父节点的左子节点或右子节点指针。

    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;}elsereturn false;
    }cur = new Node(kv);
    if (parent->_kv.first < kv.first)parent->_right = cur;
    elseparent->_left = cur;
    cur->_parent = parent;
    
  3. 修复红黑树性质:插入新节点后,红黑树可能不再满足其性质。因此,我们需要进行一系列操作来修复这些性质。这主要包括检查新节点的父节点和叔叔节点的颜色,并根据需要执行旋转和重新着色操作。关于旋转操作我们在AVL树中已进行描述,若仍存疑,可以点击此处,或给我留言。

    • 检查父节点颜色:如果新节点的父节点是黑色,那么插入操作不会破坏红黑树的任何性质,因此无需进行任何修复操作。如下图插入10或20,不会破坏红黑树性质:

      在这里插入图片描述

    • 父节点和叔叔节点均为红色:如果新节点的父节点是红色,并且其叔叔节点(父节点的兄弟节点)也是红色,那么我们需要将父节点和叔叔节点都重新着色为黑色,并将祖父节点(父节点的父节点)着色为红色。然后,我们将祖父节点作为新的当前节点,继续向上检查,直到根节点或遇到黑色父节点为止。如图所示:

      在这里插入图片描述

      分为两种对称情况,图示为插入30。若插入3,同理即可。代码实现如下:

      while (parent && parent->_col == RED) { if (parent == grandparent->_left) {Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else {//....}}else {Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else {//...}}
      } 
      

      此段代码用于处理父节点和叔叔节点都为红色的情况:

      parent 是新插入节点的父节点,grandparentparent 的父节点,_col 是节点的颜色(RED 或 BLACK)的属性,_left_right 是指向左右子节点的指针。

      这段代码的逻辑是这样的:

      1. while (parent && parent->_col == RED):这个循环会持续进行,直到 parent 为空(即已经到达根节点)或者 parent 的颜色为黑色。
      2. if (parent == grandparent->_left):判断 parent 是否是 grandparent 的左子节点。
      3. Node* uncle = grandparent->_right;:如果是左子节点,则叔叔节点(uncle)是 grandparent 的右子节点。
      4. if (uncle && uncle->_col == RED):如果叔叔节点存在且为红色,那么执行以下操作:
        • parent->_col = uncle->_col = BLACK;:将父节点和叔叔节点的颜色都改为黑色。
        • grandparent->_col = RED;:将祖父节点的颜色改为红色。
        • cur = grandparent;parent = cur->_parent;:更新 cur 为祖父节点,并将 parent 更新为 cur 的父节点,以便在下一次循环中继续向上检查。
      5. 如果叔叔节点不存在或者不是红色,代码进入 else 块,这里通常包含一些旋转和颜色调整的逻辑,我们将在下面继续讨论。

      我们给出抽象图,注意对称情况,我们不在赘述:

      在这里插入图片描述

      如果这次更新完后,祖父节点作为了新节点。它的父节点为红,则继续向上更新。

    • 父节点为红色,叔叔节点不存在或为黑色:在这种情况下,我的当前的节点称为新节点(下文统一称其为新节点),因此该节点可能是由其子树变化得来,也有可能是新插入的节点。我们需要进行旋转操作。具体的旋转方式取决于新节点是父节点的左孩子还是右孩子。如果新节点是父节点的左孩子,并且父节点是其祖父节点的左孩子,则对祖父节点进行右旋;如果新节点是父节点的右孩子,并且父节点是其祖父节点的右孩子,则对祖父节点进行左旋。旋转后,我们将原父节点的颜色更改为黑色,并将祖父节点的颜色更改为红色。如图所示:
      在这里插入图片描述

      分为两种对称情况,图示为插入2。若插入55,同理即可。

      如果新节点是父节点的右孩子,并且父节点是其祖父节点的左孩子,则先对父亲节点进行右旋,再最祖父节点进行左旋。如果新节点是父节点的左孩子,并且父节点是其祖父节点的右孩子,则先对父亲节点进行左旋,再最祖父节点进行右旋。旋转后,我们将原祖父节点的颜色更改为红色,并将新节点的颜色更改为黑色。如图所示:

      在这里插入图片描述

      同样分为两种对称情况,图示为插入4。若插45,先右单旋父节点,再左单旋祖父节点。

      ⚠️需要注意的是:

      如果叔叔节点如果不存在,那么新节点一定是新插入的节点

      因为如果新节点不是新插入节点,那么父亲节点和新节点一定由一个节点的颜色是黑色的,不满足性质5:每条路径黑色节点个数相同。

      如果叔叔节点存在,根据判断条件,叔叔是黑色的那么新节点原来的颜色肯定是黑色。变为红色的原因是因为新节点的子树在调整过程中改变了新节点的颜色。

      代码实现如下:

     while (parent && parent->_col == RED) {Node* grandparent = parent->_parent;if (parent == grandparent->_left) {Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED) {//... 叔叔存在且为红}else {//情况二:叔叔不存在 或者 存在但为黑色//旋转+变色if (cur == parent->_left) {//       g//    p    u// cRotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else {//       g//    p    u//		cRotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else {Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED) {//... 情况一:叔叔存在且为红}else {// 情况二:叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right) {RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else {//		g//   u     p//      cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}
    }
  4. 如果当前节点cur是其父节点的左孩子,并且父节点是祖父节点的左孩子,则执行右旋操作RotateR(grandparent)。这会将父节点移动到祖父节点的右子树,并相应地更新子节点的父节点指针。旋转后,将父节点变为黑色,祖父节点变为红色。

  5. 如果当前节点cur是其父节点的右孩子,并且父节点是祖父节点的左孩子,则首先执行左旋操作RotateL(parent),将当前节点cur移动到父节点的左子树。接着执行右旋操作RotateR(grandparent),将父节点移动到祖父节点的右子树。旋转后,将当前节点cur变为黑色,祖父节点变为红色。

类似地,当父节点是祖父节点的右孩子时,执行相反的操作:

  1. 如果当前节点cur是其父节点的右孩子,并且父节点是祖父节点的右孩子,则执行左旋操作RotateL(grandparent)
  2. 如果当前节点cur是其父节点的左孩子,并且父节点是祖父节点的右孩子,则首先执行右旋操作RotateR(parent),接着执行左旋操作RotateL(grandparent)

我们分别给出新节点与父亲在不同方向的抽象图和相同方向的抽象图,注意对称情况:

在这里插入图片描述

如果新节点是父节点的右孩子,并且父节点是其祖父节点的左孩子,则先对父亲节点进行右旋,再最祖父节点进行左旋。如果新节点是父节点的左孩子,并且父节点是其祖父节点的右孩子,则先对父亲节点进行左旋,再最祖父节点进行右旋。

在这里插入图片描述

如果新节点是父节点的左孩子,并且父节点是其祖父节点的左孩子,则对祖父节点进行右旋;如果新节点是父节点的右孩子,并且父节点是其祖父节点的右孩子,则对祖父节点进行左旋。

此次旋转完后,我们就结束循环,此时可以确保树仍然满足红黑树的定义。

  1. 确保根节点为黑色:在所有修复操作完成后,我们还需要确保根节点是黑色的。如果根节点在修复过程中被着色为红色,我们需要将其重新着色为黑色。在找到插入位置时,如果父节点是黑的,插入完成,因为插入红色节点不会违反性质5。如果它的父节点已经是红色的,那么我们得到连续红色节点,这就违反性质4。在这种情况下,我们必须调整该树以确保性质4满足(且不引起性质5被破坏)。因此我们在插入时需要的基本操作是节点颜色的改变以及树的旋转:

    _root->_col = BLACK;
    

通过执行上述步骤,我们可以确保在插入新节点后,红黑树仍然保持其平衡性质,并且能够有效地支持查找、删除等后续操作。红黑树的插入操作在平均情况下的时间复杂度为O(log n),其中n为树中节点的数量。

插入的完整代码如下:

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;}elsereturn false;}cur = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent && parent->_col == RED) {Node* grandparent = parent->_parent;if (parent == grandparent->_left) {Node* uncle = grandparent->_right;//情况一  :叔叔存在且为红if (uncle && uncle->_col == RED) {//先变色 后向上处理parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else {//情况二:叔叔不存在 或者 存在但为黑色//旋转+变色if (cur == parent->_left) {//       g//    p    u// cRotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else {//       g//    p    u//		cRotateL(parent);RotateR(grandparent);cur->_col = BLACK;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 {// 情况二:叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right) {RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else {//		g//   u     p//      cRotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

2、红黑树的验证方法

红黑树也是一种特殊的二叉搜索树,因此我们可以先获取二叉树的中序遍历序列,来判断该二叉树是否满足二叉搜索树的性质:

void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << endl;_InOrder(root->_right);
}
void InOrder() { _InOrder(_root); } 

我们也要检测其是否满足红黑树的性质,我们需要两个函数:

a. Check 函数

Check 函数用于递归地检查红黑树的性质是否得到满足。它接受三个参数:当前节点 cur、从根节点到当前节点路径上的黑色节点数 blackNum 和从根节点到最左侧路径上的黑色节点数 refBlackNum

  1. 空节点检查:如果当前节点为空(cur == nullptr),则检查从根节点到该路径的黑色节点数 blackNum 是否与最左侧路径的黑色节点数 refBlackNum 相等。如果不相等,则输出错误信息并返回 false
  2. 连续红色节点检查:如果当前节点为红色且其父节点也为红色,则违反了红黑树的性质(性质 4),输出错误信息并返回 false
  3. 黑色节点计数:如果当前节点为黑色,则增加 blackNum 的计数。
  4. 递归检查子节点:递归调用 Check 函数检查当前节点的左子树和右子树,只有当左右子树都返回 true 时,当前节点才返回 true
bool Check(Node* cur, int blackNum, int refBlackNum) {if (cur == nullptr) {if (refBlackNum != blackNum) {cout << "黑色节点的数量不相等" << endl;return false;}cout << "黑色节点的数量:" << blackNum << endl;return true;}if (cur->_col == RED && cur->_parent->_col == RED) {cout << cur->_kv.first << "存在连续的红色节点" << endl;return false;}if (cur->_col == BLACK)++blackNum;return Check(cur->_left, blackNum, refBlackNum)&& Check(cur->_right, blackNum, refBlackNum);
}

b. IsBalance 函数

IsBalance 函数用于检查整棵红黑树是否平衡。

  1. 根节点颜色检查:如果根节点存在且为红色,则直接返回 false,因为根节点必须是黑色(性质 2)。
  2. 计算最左侧路径黑色节点数:从根节点开始,沿着最左侧路径遍历树,计算遇到的黑色节点数,存储在 refBlackNum 中。
  3. 调用 Check 函数:从根节点开始,调用 Check 函数递归地检查整棵树是否满足红黑树的性质。传递的初始黑色节点数 blackNum 为 0,参考黑色节点数 refBlackNum 为之前计算得到的值。
bool IsBalance(){if (_root && _root->_col == RED)return false;int refBlackNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refBlackNum++;cur = cur->_left;}return Check(_root, 0, refBlackNum);
}

如果 Check 函数返回 true,则说明红黑树平衡,IsBalance 函数也返回 true;否则,返回 false

本文代码置于:RBtree · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)

这篇关于深入解析红黑树(RB-Tree):原理、操作及应用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/821724

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2