红黑树的旋转

2024-09-07 11:52
文章标签 红黑树 旋转

本文主要是介绍红黑树的旋转,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

红黑树的基本性质

红黑树与普通的二叉搜索树不同,它在每个节点上附加了一个额外的属性——颜色,该颜色可以是红色黑色。通过引入这些颜色,红黑树能够维持以下 5 个基本性质,以确保树的平衡性:

  1. 每个节点是红色或黑色
  2. 根节点是黑色
  3. 所有叶子节点(NIL 节点)是黑色
  4. 如果一个节点是红色的,那么它的两个子节点都是黑色的(即,红色节点不能有红色子节点)。
  5. 从任一节点到其每个叶子节点的所有路径上都包含相同数量的黑色节点

 红黑树节点结构

template<class K>
struct RBtree_Node
{RBtree_Node<K>* _parent;RBtree_Node<K>* _right;RBtree_Node<K>* _left;color _color;K _value;RBtree_Node(const K& value):_parent(nullptr),_right(nullptr),left(nullptr),_color(RED),_value(value){}};

红黑树与AVL树不同使用 颜色作为判断旋转或者变色的条件,也就是 红色节点的子节点不能为红色 ,每一条路径上黑色节点个数相同(这个大家刚开始看可能不理解怎么保持,每一条路径上黑色节点个数相同,没事,往下看),我们可以使用 枚举类型将我们需要的颜色封装起来,这里的颜色就是一个标识符,我们使用符号,或者是任意数字都是可以的

enum color
{RED,BACK
};

 红黑树的旋转变色

变色

uncle节点存在并为红色

这里的cur节点一定是新插入的节点,这里的cur无论是作为parent的左节点还是右节点都是无所谓的, 因为并不存在旋转问题,我们只需要遵循好红黑树的性质规则,更新节点颜色即可,同时更新parent节点和cur节点,因为pparent节点颜色改变了,我们就可以把pparent节点红色节点作为新插入节点进行上层树的更新,保持红黑树性质

if (uncle && uncle->_colour == RED)
{//更换颜色parent->_colour = uncle->_colour = BLACK;grandfather->_colour = RED;//更新节点cur = grandfather;parent = cur->_parent;
}

 旋转变色(单方向的节点)

 uncle存在但为黑色

 cur可以作为插入节点,也可能是因为插入而导致自己从黑色变成的红色,他的子节点一定为黑色(我们可以参考上面变色的情况),所以并不违反所有路径上黑色节点数量相等的情况,这也就是黑色节点怎么往下更新变多,同时路径上黑色节点数量相等的原因!

uncle不存在

 ​​​​​​

因为没有uncle节点,所以cur节点一定是新插入的 (如果不是新插入的,其子节点一定存在黑黑色节点,但是右树并没有额外的黑色节点,这样每一条路径上的黑色节点并不相同),类似于AVL树旋转一下

  旋转变色(变折的节点)

 uncle存在但为黑色

 只是将变折的节点方向改成单向的,没有其他特色,甚至方向反转一下就是右左情况的

 uncle不存在

我在这里列举不同情况的两个方向的反折,都是一样的 

 具体代码

循环条件及变色
while (parent && parent->_colour == RED)
{//      g//   p     u//cNode* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_colour == RED){//更换颜色parent->_colour = uncle->_colour = BLACK;grandfather->_colour = RED;cur = grandfather;parent = cur->_parent;}else{//单旋//       g//    p// c//双旋//       g//    p//       cif (cur == parent->_left){RotateR(grandfather);grandfather->_colour = RED;parent->_colour = BLACK;}else{RotateL(parent);RotateR(grandfather);grandfather->_colour = RED;cur->_colour = BLACK;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_colour == RED){//更换颜色parent->_colour = uncle->_colour = BLACK;grandfather->_colour = RED;cur = grandfather;parent = cur->_parent;}else{//单旋//  g//     p//        c//双旋// g//    p// cif (cur == parent->_right){RotateL(grandfather);grandfather->_colour = RED;parent->_colour = BLACK;}else{RotateR(parent);RotateL(grandfather);grandfather->_colour = RED;cur->_colour = BLACK;}break;}}}
终止代码解释
while (parent && parent->_colour == RED)

为什么如果parent是红色节点就要继续呢,或者旋转变色后就可以退出?

在变色情况下 cur还是红色,他的parent如果还是红色,不满足性质4 需要继续变色,或者旋转变色,同理在旋转变色情况下,cur变成了黑色 ,这时候cur的parent无论是什么颜色都不会影响,同时,每一条路径上的黑色节点没有变换,符合所有性质

左右旋转函数代码 
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;subR->_left = parent;Node* Parent = parent->_parent;parent->_parent = subR;subR->_parent = Parent;if (Parent == nullptr){_root = subR;}else{if (Parent->_left == parent){Parent->_left = subR;}else{Parent->_right = subR;}}}void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) subLR->_parent = parent;subL->_right = parent;Node* Parent = parent->_parent;parent->_parent = subL;subL->_parent = Parent;if (Parent == nullptr){_root = subL;}else{if (Parent->_left == parent){Parent->_left = subL;}else{Parent->_right = subL;}}
}

红黑树与AVL树的区别

红黑树和AVL树都是自平衡二叉搜索树,它们的主要目的是通过保持树的平衡来优化查找、插入和删除操作的时间复杂度。

为什么需要自平衡搜索树呢?

如果我们一直在二叉树中输入较大的值,我们会发现,树慢慢成为了链表,远远没有达到我们想要的搜索时间复杂度O(logn)

红黑树与AVL树的区别

AVL树严格的控制树左右高度差小于2,也就是严格保持搜索树处于接近于满二叉树的情况,使时间复杂度极限接近于O(logn),但是这样会导致插入时,树的旋转开销较大,但是红黑树,保持树的黑色节点相同,在保持树的高度差的同时,减少了旋转的情况,

 可以总结为:

  • 红黑树适合频繁插入和删除的场景,因其在操作过程中旋转次数少,性能较为稳定。
  • AVL树则更适合查找频繁、插入删除较少的场景,提供了更好的查找性能,但在频繁更新时旋转次数较多,性能较低。

C++库函数中 map set也是使用红黑树实现的 ,我们也开始将自己写的红黑树封装出 自己的map set

ps:具体代码可见:study/c++_study/RBtree/RBtree/RBtree.h at main · zjsnh/study (github.com)

这篇关于红黑树的旋转的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1144989

相关文章

poj 2187 凸包or旋转qia壳法

题意: 给n(50000)个点,求这些点与点之间距离最大的距离。 解析: 先求凸包然后暴力。 或者旋转卡壳大法。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <s

Android 10.0 mtk平板camera2横屏预览旋转90度横屏拍照图片旋转90度功能实现

1.前言 在10.0的系统rom定制化开发中,在进行一些平板等默认横屏的设备开发的过程中,需要在进入camera2的 时候,默认预览图像也是需要横屏显示的,在上一篇已经实现了横屏预览功能,然后发现横屏预览后,拍照保存的图片 依然是竖屏的,所以说同样需要将图片也保存为横屏图标了,所以就需要看下mtk的camera2的相关横屏保存图片功能, 如何实现实现横屏保存图片功能 如图所示: 2.mtk

二维旋转公式

二维旋转公式 ros的tf工具包可以很方便的实现任意坐标系之间的坐标转换。但是,如果只是想简单的测试想法,而又不想编写过于庞杂的代码,考虑自己写二维旋转的函数。而与二维旋转问题对偶的另一个问题便是二维坐标系旋转变换。这两个问题的形式基本一样,只是旋转的角度相差一个负号。就是这个容易搞混,所以做个笔记,以备查用。 1. 二维旋转公式(算法) 而(此文只针对二维)旋转则是表示某一坐标点 ( x

算法复杂度 —— 数据结构前言、算法效率、时间复杂度、空间复杂度、常见复杂度对比、复杂度算法题(旋转数组)

目录 一、数据结构前言 1、数据结构 2、算法 3、学习方法 二、 算法效率 引入概念:算法复杂度  三、时间复杂度 1、大O的渐进表示法 2、时间复杂度计算示例  四、空间复杂度 计算示例:空间复杂度 五、常见复杂度对比 六、复杂度算法题(旋转数组) 1、思路1 2、思路2 3、思路3 一、数据结构前言 1、数据结构         数据结构(D

计算几何之向量旋转

实际做题中我们可能会遇到很多有关及计算几何的问题,其中有一类问题就是向量的旋转问题,下面我们来具体探讨一下有关旋转的问题。 首先我们先把问题简化一下,我们先研究一个点绕另一个点旋转一定角度的问题。已知A点坐标(x1,y1),B点坐标(x2,y2),我们需要求得A点绕着B点旋转θ度后的位置。 A点绕B点旋转θ角度后得到的点,问题是我们要如何才能得到A' 点的坐标。(向逆时针方向旋转角度正,

C++笔记19•数据结构:红黑树(RBTree)•

红黑树 1.简介:         红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,因而是接近平衡的。 当搜索二叉树退化为单支树时,搜索效率极低,为了使搜索效率高,建立平衡搜索二叉树就需要"平衡树"来解决。上一篇博客介绍了AVL树,这

yolov8-obb旋转目标检测onnxruntime和tensorrt推理

onnxruntime推理 导出onnx模型: from ultralytics import YOLOmodel = YOLO("yolov8n-obb.pt") model.export(format="onnx") onnx模型结构如下: python推理代码: import cv2import mathimport numpy as npimport onnxr

AVL 树的旋转

什么是 AVL 树? AVL 树是一种自平衡二叉搜索树(Binary Search Tree, BST),以其发明者 G. M. Adelson-Velsky 和 E. M. Landis 的名字命名。它的特点是对于任意一个节点,其左右子树的高度差(平衡因子)不超过 1,这确保了 AVL 树的高度在 O(log n) 的范围内,从而保证了插入、删除和查找操作的时间复杂度都是 O(log n)。

Unity中使用四元数限制旋转

前言         在处理旋转相关的内容的时候,如果使用unity提供的欧拉角描述旋转,会出现一下两种问题 同一旋转的表示不唯一万向节死锁         绕轴90°旋转与绕轴90°+360°旋转的表现是一致的         当某个特定轴达到某个特殊值时,绕一个轴旋转可能会覆盖另一个轴的旋转从而失去一维自由度Unity中x轴达到90度时,会产生万向节死锁。x轴为90度,此时调节y或z轴

pico手柄和人物模型手部旋转同步,实现手柄控制手臂手部位置移动、手部旋转和手指的操作了

这里的主要内容就是下述代码; // 获取左手控制器的旋转(四元数表示)Quaternion aRotationQuaternion = leftHandController.rotation;// 计算旋转差值(四元数表示)Quaternion rotationDifference = Quaternion.Euler(0, -90, -90);// 应用差值到左手控制器的旋转并获取新的四元数