数据结构中的平衡搜索树 --- 红黑树 （如何旋转与变色）

2024-03-14 06:04
文章标签 数据结构 搜索 红黑树 旋转 平衡 变色

本文主要是介绍数据结构中的平衡搜索树 --- 红黑树 （如何旋转与变色），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

红黑树的概念

红黑树的性质

红黑树节点的定义

红黑树的插入

1. 按照二叉搜索的树规则插入新节点

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

红黑树的概念

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

红黑树的性质

  • 1. 每个结点不是红色就是黑色
  • 2. 根节点是黑色的 
  • 3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 
  • 4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  • 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

红黑树节点的定义

enum Color
{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;Color _col; //节点颜色RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)  //默认红色{}
};

为什么构造函数中的节点默认给的是红色？ 通过红黑树的性质能总结出：

性质3 - 代表着不能出现连续的红色节点

性质4 - 每条路径上都有相同数量的黑色节点

        这时会发现违反性质3比违反性质4的代价要更小，而事实上也的确是这样做的，可能会有疑问，这样还是红黑树嘛，其实新增节点之后是需要通过变色来达到红黑树的结构的。（如下）

示例：

此时我们会发现，最后的结构是符合红黑树的：没有出现连续的红色节点；每条路径上的黑色节点数量相同。

红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;   //记录cur的父节点，方便进行链接while (cur){if (kv.first < cur->_kv.first)  //插入的值小于存储的值{parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first) //插入的值大于存储的值{parent = cur;cur = cur->_right;}else{return false; //相等，插入失败}}//注意：新增的节点构造是红色，所以这里不用给颜色cur = new Node(kv);  if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent; //...调整颜色return true;}protected:Node* _root = nullptr;
};
2. 检测新节点插入后，红黑树的性质是否造到破坏

注意：关于旋转处理可以参考AVL树的旋转处理

        因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定：1.grandfather->_left = parent;  grandfather->_right = uncle; (父节点在左，叔节点在右）
grandfather为黑，parent为红，cur（新增节点）为红
① uncle节点存在且为红色  ----》 parent , uncle 改黑，grandfather改红，继续向上调整

② uncle节点不存在 or  存在且为黑  - 单旋

③ uncle节点不存在 or  存在且为黑  - 双旋


 

约定：2.grandfather->_left = uncle;  grandfather->_right = parent; （叔节点在左，父节点在右） 

（参考上面）

具体代码演示：

        //旋转+更改颜色while (parent && parent->_col == RED){//记录祖先节点Node* grandfather = parent->_parent;//父节点是祖先节点的左子树if (grandfather->_left == parent){Node* uncle = grandfather->_right;//①uncle节点存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent; //注意需要重新计数parent}else {//②uncle不存在 or 存在且为黑 ->  变色 + 旋转if (cur == parent->_left) {//单旋RotateR(grandfather); parent->_col = BLACK;grandfather->_col = RED;}else{//双旋RotateL(parent); RotateR(grandfather);parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}else if (grandfather->_right == parent) //父节点是祖先节点的右子树{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent; }else{if (cur == parent->_right){//单旋RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//双旋RotateR(parent);RotateL(grandfather);parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}else{assert(false); }}//结尾做保险处理，无论什么情况，根节点置成黑_root->_col = BLACK;

附上红黑树(测试是否是红黑树）部分代码：

                                                                                                RBTree.h

#pragma once
#include <iostream>
#include <assert.h>
#include <string>using namespace std;enum Color
{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;Color _col; //节点颜色RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)  //默认红色{}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;public:void InOrder(){_InOrder(_root);cout << endl;}//检查是否是红黑树bool IsBalance(){//检查1：根节点颜色if (_root && _root->_col != BLACK){cout << "根节点为红" << endl;return false;}//检查2：是否存在连续红色节点//检查3：每条路径上的黑色节点是否相同return _Check(_root, 0);}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;   //记录cur的父节点，方便进行链接while (cur){if (kv.first < cur->_kv.first)  //插入的值小于存储的值{parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first) //插入的值大于存储的值{parent = cur;cur = cur->_right;}else{return false; //相等，插入失败}}//注意：新增的节点构造是红色，所以这里不用给颜色cur = new Node(kv);  if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent; //旋转+更改颜色while (parent && parent->_col == RED){//记录祖先节点Node* grandfather = parent->_parent;//父节点是祖先节点的左子树if (grandfather->_left == parent){Node* uncle = grandfather->_right;//①uncle节点存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent; //注意需要重新计数parent}else {//②uncle不存在 or 存在且为黑 ->  变色 + 旋转if (cur == parent->_left) {//单旋RotateR(grandfather); parent->_col = BLACK;grandfather->_col = RED;}else{//双旋RotateL(parent); RotateR(grandfather);parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}else if (grandfather->_right == parent) //父节点是祖先节点的右子树{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent; }else{if (cur == parent->_right){//单旋RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//双旋RotateR(parent);RotateL(grandfather);parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}else{assert(false); }}//结尾做保险处理，无论什么情况，根节点置成黑_root->_col = BLACK;return true;}protected:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}bool _Check(Node* root, int BlackNums){if (root == nullptr){cout <<BlackNums << endl;return true;}//这里是传值返回if (root->_col == BLACK)++BlackNums;//root与root的子树不好判断，因为节点不一定有子树，但是一定有父节点if (root->_col == RED &&root->_parent && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return _Check(root->_left, BlackNums)&& _Check(root->_right, BlackNums);}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;//提前记录祖先节点Node* pparent = parent->_parent;subR->_left = parent;parent->_parent = subR;//值得注意的是，parent节点不一定为根节点，也就是旋转的可能是一棵子树而不是整棵树if (pparent == nullptr) //意味着parent节点是根节点{_root = subR;_root->_parent = nullptr;}else{//判断parent 在 祖先节点的左还是右if (pparent->_right == parent){pparent->_right = subR;}else{pparent->_left = subR;}subR->_parent = pparent;  //更改subR的父节点}}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;//提前记录祖先节点Node* pparent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{//判断parent 在 祖先节点的左还是右if (pparent->_right == parent){pparent->_right = subL;}else{pparent->_left = subL;}subL->_parent = pparent;  //更改subR的父节点}}protected:Node* _root = nullptr;
};void Test_RBTree1()
{int arr1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int arr2[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t1;for (auto e : arr1){t1.Insert(make_pair(e, e));cout << e << "插入:" << t1.IsBalance() << endl;  //插入进行检查}t1.InOrder();cout << t1.IsBalance() << endl;
}

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

这篇关于数据结构中的平衡搜索树 --- 红黑树 （如何旋转与变色）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

C# ComboBox下拉框实现搜索方式

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这
阅读更多...
Qt QWidget实现图片旋转动画

Qt QWidget实现图片旋转动画

《QtQWidget实现图片旋转动画》这篇文章主要为大家详细介绍了如何使用了Qt和QWidget实现图片旋转动画效果,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、效果展示二、源码分享本例程通过QGraphicsView实现svg格式图片旋转。.hpjavascript
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
poj 2187 凸包or旋转qia壳法

poj 2187 凸包or旋转qia壳法

题意： 给n（50000）个点，求这些点与点之间距离最大的距离。 解析： 先求凸包然后暴力。 或者旋转卡壳大法。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <s
阅读更多...
hdu 4517 floyd+记忆化搜索

hdu 4517 floyd+记忆化搜索

题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
hdu4277搜索

hdu4277搜索

给你n个有长度的线段，问如果用上所有的线段来拼1个三角形，最多能拼出多少种不同的？ import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2