【C++ RB树】

2024-03-16 13:12
文章标签 c++ rb

本文主要是介绍【C++ RB树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

    • 红黑树
      • 红黑树的概念
      • 红黑树的性质
      • 红黑树节点的定义
      • 红黑树的插入
      • 代码实现
      • 总结

红黑树

AVL树是一颗绝对平衡的二叉搜索树，要求每个节点的左右高度差的绝对值不超过1，这样保证查询时的高效时间复杂度O( l o g 2 N ) log_2 N) log2​N)，但是要维护其绝对平衡，旋转的次数比较多。因此，如果一颗树的结构经常修改，那么AVL树就不太合适，所以就有了红黑树。

红黑树的概念

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

红黑树的性质

  1. 每个节点不是红色就是黑色
  2. 根节点是黑色的
  3. 不存在连续的红色节点
  4. 任意一条从根到叶子的路径上的黑色节点的数量相同
    根据上面的性质，红黑树就可以确保没有一条路径会比其他路径长出两倍，因为每条路径上的黑色节点的数量相同，所以理论上最短边一定都是黑色节点，最长边一定是一黑一红的不断重复的路径。

红黑树节点的定义

	enum Color{RED,BLACK};template<class K, class V>struct RBTreeNode{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;pair<K, V> _kv;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){}};

插入新节点的颜色一定是红色，因为如果新节点的颜色是黑色，那么每条路径上的黑色节点的数量就不相同了，处理起来就比较麻烦，所以宁愿出现连续的红色节点，也不能让某一条路径上多出一个黑色节点。

红黑树的插入

1.根据二叉搜索树的规则插入新节点

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* curr = _root;Node* parent = nullptr;while (curr){if (curr->_kv.first < kv.first){parent = curr;curr = curr->_right;}else if (curr->_kv.first > kv.first){parent = curr;curr = curr->_left;}else{return false;}}curr = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = curr;elseparent->_left = curr;curr->_parent = parent;
........

2.测新节点插入后，红黑树的性质是否造到破坏

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* curr = _root;Node* parent = nullptr;while (curr){if (curr->_kv.first < kv.first){parent = curr;curr = curr->_right;}else if (curr->_kv.first > kv.first){parent = curr;curr = curr->_left;}else{return false;}}curr = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = curr;elseparent->_left = curr;curr->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;curr = grandfather;parent = curr->_parent;}else{if (curr == parent->_left){//      g//   p     u//cRotatoR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p     u//    cRotatoL(parent);RotatoR(grandfather);curr->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;curr = grandfather;parent = curr->_parent;}else{if (curr == parent->_right){//      g   //   u     p//           cRotatoL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g   //   u     p//        cRotatoR(parent);RotatoL(grandfather);curr->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}
void RotatoL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent)ppnode->_left = subR;elseppnode->_right = subR;subR->_parent = ppnode;}
}
void RotatoR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent)ppnode->_left = subL;elseppnode->_right = subL;subL->_parent = ppnode;}
}

代码实现

#pragma once
#include <utility>namespace lw
{enum Color{RED,BLACK};template<class K, class V>struct RBTreeNode{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _col;pair<K, V> _kv;RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_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* curr = _root;Node* parent = nullptr;while (curr){if (curr->_kv.first < kv.first){parent = curr;curr = curr->_right;}else if (curr->_kv.first > kv.first){parent = curr;curr = curr->_left;}else{return false;}}curr = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = curr;elseparent->_left = curr;curr->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;curr = grandfather;parent = curr->_parent;}else{if (curr == parent->_left){//      g//   p     u//cRotatoR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   p     u//    cRotatoL(parent);RotatoR(grandfather);curr->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;curr = grandfather;parent = curr->_parent;}else{if (curr == parent->_right){//      g   //   u     p//           cRotatoL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g   //   u     p//        cRotatoR(parent);RotatoL(grandfather);curr->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotatoL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent)ppnode->_left = subR;elseppnode->_right = subR;subR->_parent = ppnode;}}void RotatoR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent)ppnode->_left = subL;elseppnode->_right = subL;subL->_parent = ppnode;}}void InOrder(){_InOrder(_root);}bool IsBalance(){if (_root && _root->_col == RED)return false;Node* left = _root;int count = 0;while (left){if (left->_col == BLACK)count++;left = left->_left;}return check(_root, 0, count);}private:bool check(Node* root, int count, int refBlackNumber){if (root == nullptr){if (count == refBlackNumber)return true;elsereturn false;}if (root->_col == RED && root->_parent->_col == RED)return false;if (root->_col == BLACK)count++;return check(root->_left, count, refBlackNumber)&& check(root->_right, count, refBlackNumber);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " : " << root->_kv.second << endl;_InOrder(root->_right);}Node* _root = nullptr;};
}

总结

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2​N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

这篇关于【C++ RB树】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/815605。

相关文章

c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...
C++ Log4cpp跨平台日志库的使用小结

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
c++中的set容器介绍及操作大全

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》：本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方
阅读更多...
解析C++11 static_assert及与Boost库的关联从入门到精通

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识：传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决
阅读更多...
C++11委托构造函数和继承构造函数的实现

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函
阅读更多...
C++11作用域枚举(Scoped Enums)的实现示例

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2