【数据结构】红黑树

embedded/2024/9/23 0:20:15/

目录

一、红黑树

1.1 基本概念

1.2 红黑树与AVL树的比较

二、结构和操作

2.1 节点定义

2.2 节点的插入操作

2.3 红黑树的迭代器

2.4 红黑树的模拟实现

三、set、 map的模拟实现

一、红黑树

1.1 基本概念

红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 

红黑树满足以下性质：

  1. 节点颜色：每个节点要么是黑色，要么是红色。
  2. 根节点：根节点是黑色。
  3. 颜色限制：如果一个节点是红色的，则它的子节点必须是黑色的（不存在两个连续的红色节点）。
  4. 叶子节点：每个叶子节点（NIL 节点，即空节点）都是黑色的。
  5. 黑节点数量：对于每个节点，从该节点到其后代叶子节点的简单路径上，黑色节点的数量是相同的。

这些性质保证了红黑树的关键特性：任何从根到叶子的路径上，最长的路径不会超过最短路径的两倍长。因此，红黑树是一种高效的自平衡二叉搜索树，适用于需要频繁插入、删除和查找操作的场景。

注：

  1. 最短路径和最长路径不一定会存在。
    最短路径：全黑
    最长路径：一黑一红间隔
  2. 假设每条路径都有N个黑色节点，每条路径的节点数量在[N，2*N]之间。

1.2 红黑树与AVL树的比较

红黑树和AVL树都是自平衡二叉搜索树，但它们在平衡策略和性能方面有所不同。

平衡性：AVL树是严格平衡的，它要求左右子树的高度差不超过1。而红黑树是近似平衡的，它通过染色和旋转来维护平衡，允许最长的路径不会超过最短路径的两倍长。相对而言，红黑树的平衡性要稍弱一些，但仍然能够在大多数情况下保持较好的平衡。

插入和删除操作的效率：由于AVL树是严格平衡的，因此插入和删除操作可能需要进行更多的旋转来调整树的结构，以维持平衡。相比之下，红黑树的插入和删除操作可能需要更少的旋转操作，因为它允许一定程度的不平衡。因此，红黑树在插入和删除操作方面可能具有更好的性能。

查询操作的效率：由于红黑树在插入和删除操作上具有更好的性能，但在查询操作上与AVL树相当。这是因为红黑树的高度相对较大，但仍保持在较小的范围内，使得查询操作的时间复杂度仍然是O(log n)，其中n是树中节点的数量。而AVL树由于严格的平衡性要求，在某些情况下可能会略微优于红黑树。

二、结构和操作

2.1 节点定义

enum Colour
{RED,BLACK
};template <class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};

2.2 节点的插入操作

按照二叉搜索的树规则插入新节点，新节点是红色，有两种情况：
1、插入节点的父亲是黑色，那么就结束了。没有违反任何规则。
2、插入节点的父亲是红色的，那么存在连续的红色节点，违反规则3，需要处理。

设新插入的节点为cur，其父亲节点为p，祖父节点为p，叔叔节点为u，根据各节点颜色的不同可分为以下几种情况：

情况1：cur为红，p为红，g为黑，存在且为红
解决方式：将p，u改为黑，g改为红，然后把g当成cur，继续向上调整。
注意：此处所看到的树，可能是一棵完整的树，也可能是一棵子树

情况二：cur为红，p为红，g为黑，u不存在
解决方案：若p为g的左孩子，cur为p的左孩子，则g进行右单旋转；
相反，p为g的右孩子，cur为p的右孩子，则g进行左单旋转；
p、g变色--p变黑，g变红

情况三：cur为红，p为红，g为黑，u存在且为黑
c为包含一个黑色节点红黑树

解决方案：旋转+变色
若p为g的左孩子，cur为p的左孩子，则g进行右单旋转；
相反，p为g的右孩子，cur为p的右孩子，则g进行左单旋转；
p、g变色--p变黑，g变红

情况四：cur为红，p为红，g为黑，u不存在/u存在且为黑

解决方案：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转;
相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转；
转换成情况二和情况三

2.3 红黑树的迭代器

template <class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _pnode;__TreeIterator(Node* pnode):_pnode(pnode){}Ref operator*(){return _pnode->_data;}Ptr operator->(){return &_pnode->_data;}Self& operator--(){if (_pnode->_left)//左子树不为空，下一节点为左子树的最右节点{Node* cur = _pnode->_left;while (cur->_right){cur = cur->_right;}_pnode = cur;}else//左子树为空，找孩子是父亲右的那个祖先{Node* cur = _pnode;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_pnode = parent;}return *this;}Self& operator++(){if (_pnode->_right){//右子树不为空，下一个节点为右子树的最左节点Node* cur = _pnode->_right;while (cur->_left){cur = cur->_left;}_pnode = cur;}else{//右子树为空，下一个节点为节点为父亲左孩子的那个祖先Node* cur = _pnode;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_pnode = parent;}return *this;}bool operator==(const Self& s){return _pnode == s._pnode;}bool operator!=(const Self& s){return _pnode != s._pnode;}
};

2.4 红黑树的模拟实现

#pragma onceenum Colour
{RED,BLACK
};template <class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};template <class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _pnode;__TreeIterator(Node* pnode):_pnode(pnode){}Ref operator*(){return _pnode->_data;}Ptr operator->(){return &_pnode->_data;}Self& operator--(){if (_pnode->_left)//左子树不为空，下一节点为左子树的最右节点{Node* cur = _pnode->_left;while (cur->_right){cur = cur->_right;}_pnode = cur;}else//左子树为空，找孩子是父亲右的那个祖先{Node* cur = _pnode;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_pnode = parent;}return *this;}Self& operator++(){if (_pnode->_right){//右子树不为空，下一个节点为右子树的最左节点Node* cur = _pnode->_right;while (cur->_left){cur = cur->_left;}_pnode = cur;}else{//右子树为空，下一个节点为节点为父亲左孩子的那个祖先Node* cur = _pnode;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_pnode = parent;}return *this;}bool operator==(const Self& s){return _pnode == s._pnode;}bool operator!=(const Self& s){return _pnode != s._pnode;}
};template<class K, class T, class KeyOfT>//KeyOfT用来区分set和map
class RBTree
{typedef RBTreeNode<T> Node;private:Node* _proot = nullptr;public:typedef __TreeIterator<T, T&, T*> iterator;typedef __TreeIterator<T, const T&, const T*> const_iterator;iterator begin(){Node* cur = _proot;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* cur = _proot;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);}const_iterator end()const{return const_iterator(nullptr);}pair<Node*, bool> Insert(const T& data){if (_proot == nullptr){_proot = new Node(data);_proot->_col = BLACK;return make_pair(_proot, true);}Node* parent = nullptr;Node* cur = _proot;KeyOfT kot;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return make_pair(cur, false);}}//此时cur指向的位置就是新节点要插入的位置cur = new Node(data);Node* newnode = cur;cur->_col = RED;if (kot(data) < kot(parent->_data)){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//插入结束，开始调整//父节点为黑色，不用调整while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//父节点为红色，必有祖父节点if (parent == grandfather->_left){//		g//	p		u//cNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//情况1{uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;//把g看作cur，继续向上更新cur = grandfather;parent = cur->_parent;}else//u不存在 或 u存在且为黑{if (cur == parent->_left){//		g//	p//c//g右单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//	p//	 c//双旋：p左旋，然后g右旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//p为g的右节点{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//	u	   p //		 c//RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_proot->_col = BLACK;return make_pair(newnode, true);}void RotateR(Node* cur){Node* subL = cur->_left;Node* subLR = subL->_right;cur->_left = subLR;if (subLR) subLR->_parent = cur;subL->_right = cur;Node* parent = cur->_parent;cur->_parent = subL;subL->_parent = parent;if (cur == _proot) _proot = subL;if (parent){if (parent->_left == cur)parent->_left = subL;elseparent->_right = subL;}}void RotateL(Node* cur){Node* subR = cur->_right;Node* subRL = subR->_left;cur->_right = subRL;if (subRL) subRL->_parent = cur;subR->_left = cur;Node* parent = cur->_parent;cur->_parent = subR;subR->_parent = parent;if (cur == _proot) _proot = subR;if (parent){if (parent->_left == cur)parent->_left = subR;elseparent->_right = subR;}}void InOrder(){_InOrder(_proot);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data << " ";_InOrder(root->_right);}bool Check(Node* root, int blacknum, const int retVal){if (root == nullptr){if (blacknum != retVal){cout << "存在黑色节点数量不相等的路径" << endl;return false;}return true;}if(root->_col == RED && root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col == BLACK)blacknum++;return Check(root->_left, blacknum, retVal)&& Check(root->_right, blacknum, retVal);}bool IsBalance(){if (_proot == nullptr) return true;if (_proot->_col == RED) return false;int retVal = 0;Node* cur = _proot;while (cur){if (cur->_col == BLACK) retVal++;cur = cur->_left;}int blacknum = 0;return Check(_proot, blacknum, retVal);}int Height(){return _Height(_proot);}int _Height(Node* root){if (root == nullptr) return 0;int LHeight = _Height(root->_left);int RHeight = _Height(root->_right);return LHeight > RHeight ? LHeight + 1 : RHeight + 1;}size_t Size(){return _Size(_proot);}size_t _Size(Node* root){if (root == nullptr) return 0;return _Size(root->_left) + _Size(root->_right) + 1;}Node* Find(const K& key){Node* cur = _proot;while (cur){if (cur->_data < key) cur = cur->_right;else if (cur->_data > key) cur = cur->_left;else return cur;}return nullptr;}};

三、set、 map的模拟实现

set的模拟实现：

注意：为了防止修改迭代器指向的内容，set的iterator迭代器和const_iterator迭代器都设置成const_iterator迭代器。因此begin()和end()都是常量成员函数

#pragma once
#include "RBTree.h"namespace zzx
{template<class K>class set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};}

map的模拟实现：
注：为防止通过迭代器修改key，声明成员变量 _t 为RBTree<K, pair<const K, V>, MapKeyOfT>，对pair中的K用 const 修饰。

#pragma once
#include "RBTree.h"namespace zzx
{template<class K,class V>class map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator end()const{return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}

http://www.ppmy.cn/embedded/11723.html

相关文章

java 学习一

java 学习一

jdk下载地址 配置环境变量
阅读更多...
《剑指 Offer》专项突破版 - 面试题 113、114 和 115 : 详解拓扑排序（C++ 实现）

《剑指 Offer》专项突破版 - 面试题 113、114 和 115 : 详解拓扑排序（C++ 实现）

目录 前言 面试题 113 : 课程顺序 面试题 114 : 外星文字典 面试题 115 : 重建序列 前言 拓扑排序是指对一个有向无环图的节点进行排序之后得到的序列。如果存在一条从节点 A 指向节点 B 的边&#xff0c;那么在拓扑排序的序列中节点 A 出现在节点 B 的前面。一个有向无环…
阅读更多...
OpenHarmony UI动画-lottie

OpenHarmony UI动画-lottie

简介 lottie是一个适用于OpenHarmony的动画库&#xff0c;它可以解析Adobe After Effects软件通过Bodymovin插件导出的json格式的动画&#xff0c;并在移动设备上进行本地渲染。 下载安裝 ohpm install ohos/lottieOpenHarmony ohpm 环境配置等更多内容&#xff0c;请参考如何…
阅读更多...
算法训练营day21

算法训练营day21

一、二叉搜索树的最小绝对差 参考链接530. 二叉搜索树的最小绝对差 - 力扣&#xff08;LeetCode&#xff09; 利用二叉搜索树的性质 中序遍历 获取递增序列&#xff0c;还可以解决其他问题 173. 二叉搜索树迭代器 - 力扣&#xff08;LeetCode&#xff09; 530. 二叉搜索树的…
阅读更多...
TensorRT从了入门到了解(官方文档)-学习笔记

TensorRT从了入门到了解(官方文档)-学习笔记

继续研究如何使用TensorRT 本篇主要阅读TensorRT官方文档 目录 0.简介1.The C++ API1.1 The Build Phase 构建阶段1.1.1 Creating a Network Definition 创建网络定义1.1.2 Importing a Model Using the ONNX Parser 使用ONNX解析器导入模型1.1.3 Building an Engine1.2 Deseri…
阅读更多...
DFS与回溯专题：路径总和问题

DFS与回溯专题：路径总和问题

DFS与回溯专题&#xff1a;路径总和问题 一、路径总和 题目链接&#xff1a; 112.路径总和 题目描述 代码思路 对二叉树进行dfs搜索&#xff0c;递归计算每条路径的节点值之和&#xff0c;当某个节点的左右子节点都为空时&#xff0c;说明已经搜索完成某一条路径&#xff0…
阅读更多...
GPT国内能用吗

GPT国内能用吗

2022年11月&#xff0c;Open AI发布ChatGPT&#xff0c;ChatGPT展现了大型语模型在自然语言处理方面的惊人进步&#xff0c;其生成文本的流畅度和连贯性令人印象深刻&#xff0c;为AI应用打开了新的可能性。 ChatGPT的出现推动了AI技术在各个领域的应用&#xff0c;例如&#x…
阅读更多...
DPDK helloworld 解析

DPDK helloworld 解析

1. 学习目的 计划通过学习 DPDK 官方提供的 demo&#xff0c; 对 DPDK API 的使用有一些了解&#xff0c;helloworld 程序是其中最简单的程序&#xff0c;还是实际上手学习能更快一些。 2. 编译 helloworld 源码 环境变量设置&#xff1a; export RTE_SDK/home//dpdk/dpdk-stab…
阅读更多...
最新文章

Copyright @ 2022~2023