如何实现一棵红黑树

2024-08-25 00:04
文章标签 实现 红黑树 一棵

本文主要是介绍如何实现一棵红黑树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1.什么是红黑树

2.红黑树的实现

2.1红黑树的插入

新插入的结点应该是什么颜色的呢？

插入情况的分析

​编辑插入代码如下所示

2.2红黑树的查找

2.2检测红黑树

1.什么是红黑树？

红黑树是一棵接近平衡的二叉搜索树。由于AVL树在频繁大量改变数据的情况下，需要进行很多的旋转，会降低效率，因此，需要新的方案解决AVL树的不足，于是，有大佬发明了红黑树；红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是red或black。 通过对各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。着色方式限制如下：

  • 每个结点不是红色就是黑色，但根节点必须是黑色的。
  • 如果一个节点是红色的，则它的两个孩子结点是黑色的（没有连续的红色结点）。
  • 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（每条路径都包含相同数量的黑色结点）。
  • 注意：红黑树中的路径不是走到叶子结点，而是走到空。

为什么满足上述条件就可以保证最长路径不超过最短路径的2倍呢？极端条件下，最短路径为全黑，最长路径必须是一黑一红交替连接；此时，最长路径正好等于最短路径的2倍。

对比AVL树：AVL树高度很接近log_N，红黑树高度很接近2log_N，所以红黑树的查询效率比AVL树略差，但是几乎可以忽略不计，因为log_N足够小，所以他们之间查找的效率微乎其微。

2.红黑树的实现

（本文旨在了解红黑树，重点实现红黑树的插入）

2.1红黑树的插入

新插入的结点应该是什么颜色的呢？

红黑树的插入过程中需要保持红黑树的性质，所以，插入之前，每条路径上的黑色结点的数量是相等的，如果新插入的结点是黑色的，必然会破坏每条路径上黑色结点的数量相等的条件，需要调整；

如果插入红色结点呢？如果插入结点的父亲是黑色的，则没有破坏红黑树的性质，如果插入结点的父亲是红色的，则破坏了不能出现连续的红色结点的性质，需要调整。

总结一下就是，如果插入的结点是黑色的， 那么每次都需要调整，如果插入的结点是红色的，只有父结点是红色的，才需要调整；所以我们选择新增结点的颜色是红色的。

插入情况的分析

因为我们插入的结点的颜色是红色的，也就是上图中的cur结点，因为，插入之前的树是满足红黑树的性质的，所以，如果出现矛盾的话，p的颜色一定是红色的， g的结点一定是黑色的；此时，只剩下u结点的情况是不确定的，所以我们只需要分析u节点的情况。

情况一：u节点存在且为红色。处理方式为变色，p和u变黑g变红，如果g是根，把g变黑即可，如果g不是根，把g当成c，继续往上处理。如下图所示：

情况二：u不存在/u存在且为黑。在该情况下，又可以细分出四种情况。

  • p为g的左孩子，c为p的左孩子，以p为旋转中心进行右单旋调整。如下图所示：

  • p为g的右孩子，c为p的右孩子，以p为旋转中心进行左单旋调整。如下图所示：

  • p为g的左孩子，c为p的右孩子，以p为旋转中心进行左单旋，再以g为旋转中心进行右单旋，最后将cur变黑，将g变红。如下图所示：

  • p为g的右孩子，c为p的左孩子，以p为旋转中心进行右单旋，再以g为旋转中心进行左单旋，最后将cur变黑，将g变红。如下图所示：

插入代码如下所示

旋转操作和AVL树是相同的，此处不做讲解，不会的读者推荐阅读AVL树中有详细讲解

    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->_right = cur;}else{parent->_left = cur;}cur->_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;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色if (cur == parent->_left){//       g//    p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//       g//    p     u//      cRotateL(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{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

2.2红黑树的查找

在红黑树查找一个值和在AVL树中查找一个值是相同的。代码如下所示：

    Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}

2.2检测红黑树

如何检测我们实现的红黑树是否正确呢？我们只需要检测该树是否满足红黑树的性质，也就是一下三点：

  • 1.根是黑色的
  • 2.没有连续的红色结点
  • 3.每条路径上的黑色结点的数量相等

检测策略：先求出一条路径上黑色结点的数量作为标准值，然后依次求每一条路径上黑色结点的数量，与标准值比较。代码如下：

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);}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);}

这篇关于如何实现一棵红黑树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

C#使用yield关键字实现提升迭代性能与效率

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭
阅读更多...
Python实现高效地读写大型文件

Python实现高效地读写大型文件

《Python实现高效地读写大型文件》Python如何读写的是大型文件,有没有什么方法来提高效率呢,这篇文章就来和大家聊聊如何在Python中高效地读写大型文件,需要的可以了解下... 目录一、逐行读取大型文件二、分块读取大型文件三、使用 mmap 模块进行内存映射文件操作（适用于大文件）四、使用 pand
阅读更多...
python实现pdf转word和excel的示例代码

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1，PDF转Word2，PDF转Excel三、前端页面效果展示总结一
阅读更多...
Python xmltodict实现简化XML数据处理

Python xmltodict实现简化XML数据处理

《Pythonxmltodict实现简化XML数据处理》Python社区为提供了xmltodict库,它专为简化XML与Python数据结构的转换而设计,本文主要来为大家介绍一下如何使用xmltod... 目录一、引言二、XMLtodict介绍设计理念适用场景三、功能参数与属性1、parse函数2、unpa
阅读更多...
C#实现获得某个枚举的所有名称

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi
阅读更多...
Go语言实现将中文转化为拼音功能

Go语言实现将中文转化为拼音功能

《Go语言实现将中文转化为拼音功能》这篇文章主要为大家详细介绍了Go语言中如何实现将中文转化为拼音功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 有这么一个需求：新用户入职 创建一系列账号比较麻烦，打算通过接口传入姓名进行初始化。想把姓名转化成拼音。因为有些账号即需要中文也需要英
阅读更多...
C# 读写ini文件操作实现

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中，常将INI文件作为配置文件，用于存储应用程序的
阅读更多...
C#实现获取电脑中的端口号和硬件信息

C#实现获取电脑中的端口号和硬件信息

《C#实现获取电脑中的端口号和硬件信息》这篇文章主要为大家详细介绍了C#实现获取电脑中的端口号和硬件信息的相关方法,文中的示例代码讲解详细,有需要的小伙伴可以参考一下... 我们经常在使用一个串口软件的时候，发现软件中的端口号并不是普通的COM1，而是带有硬件信息的。那么如果我们使用C#编写软件时候，如
阅读更多...
Python使用qrcode库实现生成二维码的操作指南

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log
阅读更多...
Go语言使用Buffer实现高性能处理字节和字符

Go语言使用Buffer实现高性能处理字节和字符

《Go语言使用Buffer实现高性能处理字节和字符》在Go中,bytes.Buffer是一个非常高效的类型,用于处理字节数据的读写操作,本文将详细介绍一下如何使用Buffer实现高性能处理字节和... 目录1. bytes.Buffer 的基本用法1.1. 创建和初始化 Buffer1.2. 使用 Writ
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2