C++进阶——红黑树

发布时间:2026/11/20 1:57:07

C++进阶——红黑树 一、红黑树的概念红黑树是一棵二叉搜索树他的每个节点增加一个数据来存储颜色可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会超出其他路径2倍的长度1.1 红黑树的规则每个节点不是红色就是黑色根节点是黑色的如果一个节点是红的他的孩子节点就是黑色的这意味着任意一条路径不能出现连续的红色节点对任意一个节点从该节点到其所有NULL节点的简单路径上均包含相同数量的黑色节点当我们能时刻满足这四条规则时我们就能确保树上没有一条路径会超出其他路径2倍的长度。1.2 红黑树的效率假设N是红黑树树中结点数量h是最短路径长度则2^h-1N2^(2*h)-1,由此推出h大约为logN也就意味着红黑树增删查改最坏也就是走最长路径2*logN那么时间复杂度还是OlogN红黑树的表达相对AVL树要抽象一些AVL树通过控制高度差直观地控制了平衡。红黑树通过4条规则的约束实现了近似平衡它们的效率都是同一档次但红黑树插入节点时旋转次数更少二、红黑树的实现2.1 红黑树的结构enum Color { RED, BLACK }; templateclass K,class V struct RBTreeNode { pairK, V _kv; Color _col; RBTreeNodeK, V* _parent; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNode(const pairK,V kv) :_kv(kv) ,_parent(nullptr) ,_left(nullptr) ,_right(nullptr) { } }; templateclass K,class V class RBTree { typedef RBTreeNodeK, V Node; public: RBTree(Node* rootnullptr) :_root(root) { } private: Node* _root; };2.2 红黑树的插入2.2.1 节点插入的大概过程插入一个值按二叉搜索树规则插入插入后只需观察是否符合红黑树的四条规则如果是空树插入新增节点是黑色节点。如果不是空树选中节点必须是红色节点若插入黑色节点会破坏规则4非空树插入后新增节点的父节点如果是黑色就未破坏规则插入结束若父节点是红色的则违反规则3。据下图c是红色p是红色g必为黑色2.2.2 情况1变色若c、p、u均为红色节点g为黑色节点就将p、u变黑g变红再将g变为新的c向上更新2.2.3 情况2单旋变色c、p为红g为黑u不存在或u为黑u不存在c必为新增节点因为若c为原来的g节点那么它因为孩子节点变色而变红原来是黑色节点但u的分支后面没有黑色节点了不满足每条分支黑色节点数量相等u存在且为黑c一定不是新增节点2.2.4 情况3双旋变色c、p为红g为黑u不存在或存在为黑2.3 红黑树的验证规则1枚举颜色类型天然保证了颜色只有黑色和红色规则2可直接验证规则3前序遍历检查遇到红色节点就查孩子不太方便可反过来检查父节点颜色前序遍历遍历时用形参记录当前节点到根黑色节点数量直到空节点再选任意一条路径黑色节点作为参考值依次比较三、全部实现代码#pragma once #includeiostream #includecassert using namespace std; enum Color { RED, BLACK }; templateclass K,class V struct RBTreeNode { pairK, V _kv; Color _col; RBTreeNodeK, V* _parent; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNode(const pairK,V kv) :_kv(kv) ,_parent(nullptr) ,_left(nullptr) ,_right(nullptr) { } }; templateclass K,class V class RBTree { typedef RBTreeNodeK, V Node; public: RBTree(Node* rootnullptr) :_root(root) { } bool Insert(const pairK, V kv) { Node* newnode new Node(kv); newnode-_col RED; if (_root nullptr) { newnode-_col BLACK; _root newnode; return true; } Node* pcur _root; Node* parent pcur; while (pcur) { parent pcur; if (pcur-_kv.first kv.first) pcur pcur-_right; else if (pcur-_kv.first kv.first) pcur pcur-_left; else { delete newnode; return false; } } //开始插入 pcur newnode; pcur-_parent parent; if (parent-_kv.first kv.first) parent-_left pcur; else parent-_right pcur; while (parent parent-_col ! BLACK) { Node* g parent-_parent; Node* u nullptr; if (g) { if (parent g-_left)u g-_right; else u g-_left; if (u u-_col RED g-_col BLACK)//情况1p、c、u、都是红色g为黑色 { parent-_col BLACK; u-_col BLACK; g-_col RED; pcur g; parent g-_parent; } else if (parentg-_leftpcurparent-_left)//情况2单旋变色 { RotateR(parent); parent-_col BLACK; g-_col RED; break; } else if (parent-_right pcur g-_right parent) { RotateL(parent); parent-_col BLACK; g-_col RED; break; } else if (parent-_rightpcurg-_leftparent)//情况三双旋变色 { RotateL(pcur); RotateR(pcur); pcur-_col BLACK; g-_col RED; break; } else if (parent-_left pcur g-_right parent) { RotateR(pcur); RotateL(pcur); pcur-_col BLACK; g-_col RED; break; } } } _root-_col BLACK; return true; } void Print(Node* root) { if (root nullptr) return; Print(root-_left); cout root-_kv.first : root-_kv.second ; Print(root-_right); } Node* root() { return _root; } Node* Find(const K key) { Node* pcur _root; while (pcur) { if (pcur-_kv.first key) pcur pcur-_left; else if (pcur-_kv.first key) pcur pcur-_right; else return pcur; } return nullptr; } bool Isrbtree(Node* root) { if (_root nullptr)return true; if (root-_col ! BLACK)return false; int refnum 0; Node* cur root; while (cur ! nullptr) { if (cur-_col BLACK)refnum; cur cur-_left; } return Preorder(root,0,refnum); } private: bool Preorder(Node* root, int num, const int ref) { if (root nullptr) { return num ref; } if (root-_col RED root-_parent-_col ! BLACK) { cout 出现连续红色节点 endl; return false; } if (root-_col BLACK) return Preorder(root-_left, num 1, ref) Preorder(root-_right, num 1, ref); if (root-_col RED) return Preorder(root-_left, num, ref) Preorder(root-_right, num, ref); } void RotateR(Node* cur) { Node* parent cur-_parent; Node* grandpa parent-_parent; parent-_left cur-_right; parent-_parent cur; if (cur-_right) cur-_right-_parent parent; if (grandpa) { if (grandpa-_right parent) grandpa-_right cur; else grandpa-_left cur; } else _root cur; cur-_parent grandpa; cur-_right parent; } void RotateL(Node* cur) { Node* parent cur-_parent; Node* grandpa parent-_parent; parent-_right cur-_left; parent-_parent cur; if (cur-_left) { cur-_left-_parent parent; } if (grandpa) { if (grandpa-_right parent) grandpa-_right cur; else grandpa-_left cur; } else _root cur; cur-_parent grandpa; cur-_left parent; } Node* _root; };
延伸阅读

更多相关文章

2026/11/20 2:13:36

3个坑揭秘:旅游类网站开发设计报告与建站报价避坑指南

3个坑揭秘:旅游类网站开发设计报告与建站报价避坑指南 改个需求建站公司拖一周,这不仅是体验差,更是安全隐患。很多老板拿到一份厚厚的旅游类网站开发设计报告,看着精美,实则漏洞百出。更坑的是, 建站报价…

2026/11/19 7:48:25

AD9361多片同步:内部本振与外部本振的相位误差实战选型指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/20 2:31:17

南通低压电工证报名点到期换证流程

低压电工证报名点在哪?考前押题怎么拿?别再被坑了 你急需特种作业证才能上岗找工作,但南通低压电工证报名点在哪?考前押题怎么拿?这些问题直接关系到你的工作机会和收入水平。别再被那些打着“包过”旗号的培训机构忽悠了,先搞清楚流程和关键点,才是正…

2026/11/20 2:31:17

都匀电工证培训哪个好?工地太忙根本没时间复习考试,良心建议来了

都匀电工证培训哪个好?工地太忙根本没时间复习考试,良心建议来了 工地太忙根本没时间复习考试,这是很多电工从业者的痛点。特别是在洛阳房建工程这类工期紧、任务重的项目里,电工不仅要负责线路铺设、设备维护,还要应对突发的电路故障,根本抽不出时间去…

2026/11/20 2:31:17

电工证多久不能复审?含金量决定你能否上岗

电工证多久不能复审?含金量决定你能否上岗 不知道去哪报名怕被中介坑?很多小伙伴在考电工证的时候都遇到过这种困扰。特别是像我们这种一线作业人员, 电工证含金量 高低直接决定了能不能干工地、进厂子,甚至能不能拿到工资。今天我来跟大家聊聊,…

2026/11/20 2:31:17

深圳盐田电工证哪里考 良心建议:外省证怎么转过来最稳妥

深圳盐田电工证哪里考 良心建议:外省证怎么转过来最稳妥 之前考的证在外省能不能转过来?这是很多在深圳盐田打工的电工朋友最关心的问题。今天我就从一个干了10年应急管理工作的人角度,跟大家聊聊 深圳盐田电工证哪里考…

2026/11/20 2:26:17

工地太忙根本没时间复习考试?电工证有安装电工保姆级教程来了

工地太忙根本没时间复习考试?电工证有安装电工保姆级教程来了 工地太忙根本没时间复习考试?电工证有安装电工的小伙伴越来越多,但很多人对证书有效期、年审要求、报名材料这些细节一头雾水。特别是第一次报考的新人,比如驻马店的张师傅,他就是一边赶工期…

2026/11/19 22:14:34

电工证考试口诉怎么准备值不值得考

电工证考试口诉怎么准备值不值得考 实操考试心里没底怕挂科,这是大多数准备考电工证的人心里最真实的感受。尤其是面对【电工证考试口诉】环节,很多人不知道该怎么准备,甚至担心自己说不好就被淘汰。其实,只要掌握方法, 值不值得考…

2026/11/18 21:55:23

桑植县考电工证千万别踩坑!报名全流程教你避坑

桑植县考电工证千万别踩坑!报名全流程教你避坑 你是不是也遇到过这种情况:想考个电工证,但不知道从哪儿下手,怕被中介坑,怕花冤枉钱,更怕考了证还不能用?别急,这正是你该看这篇文章的原因。在桑植县考电工证,确实有很多人被坑过,但只要你知道流程、…

2026/11/20 0:00:30

电力电缆制作特种证过期了怎么复审?郑州报考避坑指南全解析

电力电缆制作特种证过期了怎么复审?郑州报考避坑指南全解析 证书过期了不知道怎么复审延期?作为一名在郑州从事电力电缆制作特种作业多年的项目管理员,我亲身经历过证书过期后被责令停工的尴尬场面。那天,我在平顶山某工地进行电缆敷设作业时,被当地应急…

2026/11/20 0:00:30

葫芦岛考低压电工证过期怎么复审?考前押题帮你稳过

葫芦岛考低压电工证过期怎么复审?考前押题帮你稳过 证书过期了不知道怎么复审延期,耽误工作还影响收入?别急,今天就给你讲讲葫芦岛考低压电工证的有效期、复审流程,还有考前押题怎么用,保证你少走弯路。 低压电工证有效期与复审规则…

2026/11/20 0:00:30

济阳从哪里学电工证良心建议:怕考不过白交培训费?看完这篇全明白

济阳从哪里学电工证良心建议:怕考不过白交培训费?看完这篇全明白 你是不是也担心,花了钱去学电工证,结果考试还是不过,白白浪费时间和金钱?特别是济阳这边,培训机构多得是,但真正靠谱的又有几个?今天我就来给你掏心窝子,讲讲济阳从哪里学电工证的良…

2026/11/18 12:37:05

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

在智慧养宠时代,基于视觉的宠物身份识别技术正逐步从实验室走向家庭应用。然而,与配合度高的人类不同,宠物是典型的“非合作生物识别对象”——它们不会主动配合摄像头调整姿态,更无法控制光照环境。实际应用中,我们常…

2026/11/19 17:18:32

SSM电子书店源码全解析:结构、原理、部署与排错实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

还想了解更多?直接咨询顾问

免费诊断 + 免费方案 + 透明报价。

全国咨询热线400-8866-253
免费获取方案
☎咨询二维码 ☎ ↑