二叉树与红黑树见解

article/2025/10/1 6:13:06

目录

  • 一、红黑树简介
  • 二、 红黑树的特性
  • 三、红黑数的应用
  • 四、红黑树的原理实现
    • 4.1 识别红黑树
    • 4.2 红黑树节点的旋转
    • 4.3 插入节点
      • 4.3.1分情况讨论：
      • 4.3.2 代码示例
    • 4.4删除节点
      • 相关引用

一、红黑树简介

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作1。

大家应该都学过平衡二叉树(AVLTree)，了解到AVL树的性质，其实平衡二叉树最大的作用就是查找,AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。AVL树的效率就是高在这个地方。如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理, 那么创建一颗平衡二叉树的成本其实不小. 这个时候就有人开始思考，并且提出了红黑树的理论，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。那么红黑树到底比AVL树好在哪里？

二、 红黑树的特性

在讲解红黑树性质之前，先简单了解一下几个概念：

parent：父节点
sibling：兄弟节点
uncle：叔父节点（ parent 的兄弟节点）
grand：祖父节点（ parent 的父节点）

首先，红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。它同时满足以下特性：

节点是红色或黑色
根是黑色
如果一个节点是红色，那么它的子节点必须是黑色。
从一个节点到NULL指针的每一条路径必须包含相同数目的黑色节点

在这里插入图片描述
补齐NULL节点的样子
在这里插入图片描述

三、红黑数的应用

主要就是利用红黑树的键值对（key-value）查找效率高（内存管理）和中序遍历时是顺序的

  1. STL中的map——>红黑树的封装
  2. Nginx中的应用
  3. 定时器（查找效率高）
  4. 进程的调度CFS：n个进程用红黑树来存储，这个进程集合在调度的时间，查找最小的值来调度
  5. 内存管理：内存中的内存块用红黑树存起来，而一块内存表述方式：1. 起始位置加内存长度，2. 起始位置和终止位置。存储方式用起始位置当做key,用一个指针指向key，分配一个内存块就往红黑树上加一个节点

四、红黑树的原理实现

4.1 识别红黑树

根据上面的性质，我们来判断一下下面这课树是不是红黑树
在这里插入图片描述
上面这棵树首先很容易就能知道是满足性质1-3条的，关键在于第4条性质，可能乍一看好像也是符合第4条的，但实际就会陷入一个误区，直接将图上的最后一层的节点看作叶子节点，这样看的话每一条从根节点到叶子结点的路径确实都经过了3个黑节点。
但实际上，在红黑树中真正被定义为叶子结点的，是那些空节点，如下图。
在这里插入图片描述
这样一来，路径1有4个黑色节点（算上空节点），路径2只有3个黑色节点，这样性质4就不满足了，所以这棵树并不是一个红黑树节点。

4.2 红黑树节点的旋转

这个记忆方法特别好记：左旋就是把右孩子往上提，右旋就是把左孩子往上提
在这里插入图片描述
这是左旋
这是右旋
右旋
这是左旋的具体细节

在这里插入图片描述

4.3 插入节点

4.3.1分情况讨论：

这里插入的是红色节点。（如果插入的节点，它的父节点是黑色的就直接成立，不做旋转）。

  1. 爸爸红，叔叔红，爸爸是左孩子（在这里，我们把父节点，叔节点和祖父节点全部变一下颜色就好了。）
    在这里插入图片描述
    2.1爸爸红，叔叔黑，爸爸是左孩子，当前结点是左孩子（先让爷爷和爸爸变一下颜色，在以爷爷为中心右旋。保证子树也是红黑树）
    在这里插入图片描述
  2. 2爸爸红，叔叔黑，爸爸是左孩子，而且当前结点是右孩子，z使我们要检查的节点，y是叔叔（我们先让爸爸123左旋，在此结果上继续检查123节点，这样就变成2…1那种情况了）
    在这里插入图片描述
    （和2.1相同，先让爷爷和爸爸变一下颜色，在以爷爷为中心右旋。保证子树也是红黑树）
    如果爸爸是右孩子也是上面的两种情况。

4.3.2 代码示例

理解了以上部分就可以看下面插入节点的代码

//定义红黑树的相关内容
#define RED     0
#define BLACK   1
typedef int KEY_TYPE;//红黑树的节点
typedef struct _rbtree_node {           //rbtreeunsigned char color;struct rbtree_node *parent;struct rbtree_node *left;struct rbtree_node *right;// endKEY_TYPE key;           //节点的键// value//
} rbtree_node;//红黑树根和叶子结点
struct rbtree {rbtree_node *root;rbtree_node *nil; // NULL 叶子结点
};

下面的是旋转节点的代码，一定要配合前面的图来看。

// rotate 
void rbtree_left_rotate(rbtree *T, rbtree_node *x) {// NULL --> T->nilif (x == T->nil||x->right== T->nil) return ;       // 容错设置// 第一个方向rbtree_node *y = x->right;x->right = y->left;                 //前提y不是NULL节点if (y->left != T->nil) {y->left->parent = x;}// 2y->parent = x->parent;if (x->parent == T->nil) {          //x就是根节点T->root = y;} else if (x == x->parent->left) {  //x是他老爸的左孩子x->parent->left = y;} else {                            //x是他老爸的右孩子x->parent->right = y;}// 3y->left = x;x->parent = y;
}// x --> y, y -->x 
// left --> right, right --> leftvoid rbtree_right_rotate(rbtree *T, rbtree_node *y) {// NULL --> T->nilif (y == T->nil||y->left == T->nil) return ;// 1rbtree_node *x = y->left;y->left = x->right;if (x->right != T->nil) {x->right->parent = y;}// 2x->parent = y->parent;if (y->parent == T->nil) {T->root = x;} else if (y == y->parent->right) {y->parent->right = x;} else {y->parent->left = x;}// 3x->right = y;y->parent = x;
}

以下是插入节点的代码。一定要配合那三种情况来看

 //T表示这个树的根节点，z表示插入的节点,从下往上调整
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {      // z->color == RED// z->parent->color == RED// z--> REDwhile (z->parent->color == RED) { // z红色，z爸爸红色if (z->parent == z->parent->parent->left) {             //z的爸爸是左孩子rbtree_node *y = z->parent->parent->right;          //z的叔叔if (y->color == RED) {              //1.爸爸红，叔叔红，爸爸是左孩子z->parent->color = BLACK;       //爸爸黑z->parent->parent->color = RED; //爷爷红y->color = BLACK;               //叔叔黑z = z->parent->parent;          //继续检查爷爷} else {                            // 2.爸爸红，叔叔黑，爸爸是左孩子if (z = z->parent->right) {     // 2.1 爸爸红，叔叔黑，爸爸是左孩子，自己是右孩子z = z->parent;              // z指向爸爸rbtree_left_rotate(T, z);   //以z的爸爸为中心左旋，z现在在左下z红，z的爸爸红}z->parent->color = BLACK;       // 2.2 爸爸红，叔叔黑，爸爸是左孩子，自己是左孩子z->parent->parent->color = RED;rbtree_right_rotate(T, z->parent->parent);  //以z的爷爷为中心右旋，}} else{                                 //z的爸爸是右孩子rbtree_node *y = z->parent->parent->left;          //z的叔叔if (y->color == RED) {              //1.爸爸是右孩子，爸爸红，叔叔红z->parent->color = BLACK;       //爸爸黑z->parent->parent->color = RED; //爷爷红y->color = BLACK;               //叔叔黑z = z->parent->parent;          //继续检查爷爷} else {                            // 2.爸爸是右孩子，爸爸红，叔叔黑if (z = z->parent->left) {     // 2.1 爸爸红，叔叔黑，爸爸是左孩子，自己是右孩子z = z->parent;              // z指向爸爸rbtree_right_rotate(T, z);   //以z的爸爸为中心左旋，z现在在左下z红，z的爸爸红}z->parent->color = BLACK;       // 2.2 爸爸红，叔叔黑，爸爸是左孩子，自己是左孩子z->parent->parent->color = RED;rbtree_left_rotate(T, z->parent->parent);  //以z的爷爷为中心右旋，}}}
}void rbtree_insert(rbtree *T, rbtree_node *z) {rbtree_node *y = T->nil;rbtree_node *x = T->root;while (x != T->nil) {y = x;              //y始终是x的爸爸，除特殊情况外if (z->key < x->key) {x = x->left;} else if (x->key < z->key ) {x = x->right;} else { //Exist    //相等的情况要具体分析，这里选择退出exit(-1);       //如果是定时器的话可以加一个很小的值}}z->parent = y;if (y == T->nil) {T->root = z;        //插入z前红黑树没有元素} else if (z->key < y->key) {y->left = z;} else {y->right = z;}// z --> z->color = RED;z->left = T->nil;z->right = T->nil;// 
}

4.4删除节点

**这个我也不太会，我就直接复制了别人的思路，大家可以一起学习一下，以下是引用内容2

原文链接：https://blog.csdn.net/chenlong_cxy/article/details/121481859**

红黑树的删除要比插入更加难以理解，但是只要仔细一点也还行。

第一步：找到实际待删除的结点

找结点的过程与二叉搜索树寻找待删除结点的方法一样，若找到的待删除结点的左右子树均不为空，则需要使用替换法进行删除。因此我们最终需要删除的都是左右子树至少有一个为空的结点。

找到实际待删除结点后，先不删除该结点，否则调整红黑树时不容易控制，找到实际待删除结点后立即进行红黑树的调整。

第二步：调整红黑树

调整红黑树之前，我们先判断一下本次结点的删除是否会破坏了红黑树的性质，若破坏了我们才需要对红黑树进行调整。

若实际删除的结点是红色结点，那么本次删除操作不会破坏红黑树的性质，因此我们不需要对红黑树进行调整。反之，若删除的结点是黑色结点，我们就需要对红黑树进行调整，因为黑色结点的删除将会使得一些路径中黑色结点的数目减少，此时便破坏了红黑树的性质四。

我们先来说最简单的一种情况，即待删除结点只有一个孩子为空的情况。

在这种情况下，待删除结点要么是只有左孩子，要么是有只右孩子，但不管是左孩子还是右孩子，这个孩子一定是红色的，因为若这个孩子是黑色的，那么此时图示长蓝色路径的黑色结点数目比短蓝色路径的黑色结点数目多，不符合红黑树的性质。
转载
又因为红黑树当中不允许出现连续的红色结点，因此在这种情况下实际上就只有图示两种实际情况，这时我们直接将待删除结点的那个红孩子变成黑色就行了，因为在后面实际删除结点时会将这个孩子连接到删除结点的父结点下面，连接后相当于我们删除的是一个红色结点，红黑树调整完成。

下面再来说比较复杂的情况，即待删除结点的左右孩子均为空。

我们以待删除结点是其父结点的左孩子为例，分为以下四种情况：

图示说明：若parent结点为白色，表明parent结点可能是红色结点也可能是黑色结点。若bL或bR结点为白色，表明其可能是红色结点或黑色结点甚至该结点不存在。bL和bR结点为黑色时，表明他们可能是黑色结点或该结点不存在。

情况一：brother为红色。
转载当待删除结点的brother为红色时，我们先以parent为旋转点进行一次左单旋，再将brother的颜色变为黑色，将parent的颜色变为红色，此时我们再对待删除结点cur进行情况分析，情况一就转换成了情况二、三或四。

情况二：brother为黑色，且其左右孩子都是黑色结点或为空。
转载在该情况下，我们直接将brother的颜色变成红色，此时根据parent的颜色决定红黑树的调整是否结束，若parent的颜色是红色，则我们将parent变为黑色后即可结束红黑树的调整；若parent的颜色原本就是黑色，则我们需要将parent结点当作下一次调整时的cur结点进行情况分析，并且情况二在下一次调整时可能会是情况一、二、三、四当中的任何一种。

情况三：brother为黑色，且其左孩子是红色结点，右孩子是黑色结点或为空。
转载出现该情况时，我们先以brother为旋转点进行一次右单旋，再将brother结点变为红色，将brotherLeft变为黑色，此时我们再对待删除结点cur进行情况分析，情况三就转换成了情况四。

情况四：brother为黑色，且其右孩子是红色结点。
在这里插入图片描述经过情况四的处理后，红黑树就一定调整结束了。在情况四当中，我们先以parent为旋转点进行一次左单旋，然后将parent的颜色赋值给brother，再将parent的颜色变为黑色，最后将brotherRight变为黑色，此时红黑树的调整便结束了。

说明一下：待删除结点是其父结点的右孩子时的四种情况与上面四种情况类似，这里就不列举出来了。若待删除结点没有父结点，即待删除结点是根结点时，在找到该结点时就进行了删除，这里不用考虑，具体看代码。

这里有必要对各种情况的切换进行说明，你可能会担心调整红黑树时在这四种情况当中一直来回切换而不能跳出，下面我们来对此进行分析：

转载
首先，进入情况四后红黑树就一定调整结束了。其次，进入情况三后，下次也一定会进入情况四，红黑树的调整也会结束。所以情况三和情况四是没有问题的，你们最纠结的只能是情况一和情况二了。

情况一又会切换为情况二、三、四，因此只要情况二能够有办法退出，那么所有情况就都能退出了。

在情况二当中我们说，如果parent的颜色是红色，那么我们将parent变为黑色后就可以结束红黑树的调整，那会不会每次进入情况二时parent的颜色都不是红色，而一直是黑色的呢？

当然有可能，但是我们若一直往上进行调整时，那么总会调整到红黑树的根结点，当调整到根结点后我们便不用进行调整了，此时根结点虽然是黑色的，但是不影响，这仅仅意味着每条从根到叶子的路径上包含的黑色结点的个数都增加了一个，此时也没有破坏红黑树的性质，也就完成了红黑树的调整，因此在调整过程中不会出现一直在这四种情况来回切换而不能跳出的问题。

第三步：进行结点的实际删除

在红黑树调整完毕后，我们就可以进行结点的删除了，删除结点的方式很简单，若待删除结点有左孩子或右孩子，我们将其左孩子或右孩子连接到待删除结点父结点的下面即可，之后便可以将待删除结点删除了。
代码的话，我就放一下我看到比较符合面向对象的一份模板吧，我自己也还在学习中，有啥问题可以一起探讨哦。如果侵权联系我删除哟3

原文链接：https 😕/blog.csdn.net/hahahahahaha5/article/details/122507258**

#include <iostream>
#include <iomanip>using namespace std;#define RED 0               //红色结点
#define BLACK 1             //黑色结点template<class T>
class RbTreeNode{
public:unsigned int color;T key;RbTreeNode* left;RbTreeNode* right;RbTreeNode* parent;RbTreeNode(const int& value = RED, T c = -1, RbTreeNode<T>* l = NULL, RbTreeNode<T>* r = NULL, RbTreeNode<T>* p = NULL) :color(value), key(c), left(l), right(r), parent(p) {}
};template<class T>
class RbTree
{
private:RbTreeNode<T>* Root;public:RbTreeNode<T>* nil;RbTree();~RbTree();//前中后序遍历void preOrder();void inOrder();void postOrder();//查找红黑树树x中键值为key的结点RbTreeNode<T>* ssearch(T key);//查找最小结点，并返回值为根结点T minimum();//查找最大结点，并返回值为根结点T maximum();//将结点（key为键值）插入红黑树中void iinsert(T key);//删除结点（key为键值）void ddelete(T key);//销毁红黑树void destroy();//打印红黑树void print();private://前中后序遍历void preOrder(RbTreeNode<T>* tree) const;void inOrder(RbTreeNode<T>* tree) const;void postOrder(RbTreeNode<T>* tree) const;//查找红黑树x中键值为key的结点RbTreeNode<T>* ssearch(RbTreeNode<T>* x, T key) const;//查找最小结点，并返回值为根结点RbTreeNode<T>* minimum(RbTreeNode<T>* x);//查找最大结点，并返回值为根结点RbTreeNode<T>* maximum(RbTreeNode<T>* x);//找结点x的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。RbTreeNode<T>* predecessor(RbTreeNode<T>* x);//找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。RbTreeNode<T>* successor(RbTreeNode<T>* x);//左旋void Left_rotation(RbTreeNode<T>*& root, RbTreeNode<T>* x);//右旋void Right_rotation(RbTreeNode<T>*& root, RbTreeNode<T>* y);//红黑树插入修正void iinsert_fixup(RbTreeNode<T>*& root, RbTreeNode<T>* x);//将结点x插入到红黑树中void iinsert(RbTreeNode<T>*& r, RbTreeNode<T>*& x);//红黑树删除修正void delete_fixup(RbTreeNode<T>*& root, RbTreeNode<T>* x);//移植操作void Rb_transplant(RbTreeNode<T>*& root, RbTreeNode<T>*& u, RbTreeNode<T>*& v);//删除红黑树中的结点（键值为key）void ddelete(RbTreeNode<T>*& root, RbTreeNode<T>* x);//销毁红黑树void destroy(RbTreeNode<T>*& tree);//打印红黑树void print(RbTreeNode<T>* tree, T key, int d);};template<class T>
RbTree<T>::RbTree()
{nil = new RbTreeNode<T>(BLACK, -1, nil, nil, nil);Root = nil;
}template<class T>
RbTree<T>::~RbTree()
{destroy(Root);delete nil;
}//前序遍历
template<class T>
void RbTree<T>::preOrder(RbTreeNode<T>* tree) const{if (tree != nil)    {cout << tree->key << " ";preOrder(tree->left);preOrder(tree->right);}
}template<class T>
void RbTree<T>::preOrder(){preOrder(Root);
}//中序遍历
template<class T>
void RbTree<T>::inOrder(RbTreeNode<T>* tree) const{if (tree != nil)    {inOrder(tree->left);cout << tree->key << " ";inOrder(tree->right);}
}template<class T>
void RbTree<T>::inOrder(){inOrder(Root);
}//后序遍历
template<class T>
void RbTree<T>::postOrder(RbTreeNode<T>* tree) const{if (tree != nil)    {postOrder(tree->left);postOrder(tree->right);cout << tree->key << " ";}
}template<class T>
void RbTree<T>::postOrder(){postOrder(Root);
}template<class T>
RbTreeNode<T>* RbTree<T>::ssearch(RbTreeNode<T>* x, T key) const{if (x == nil || x->key == key)    {return x;}if (key < x->key)    {return ssearch(x->left, key);}else{return ssearch(x->right, key);}
}template<class T>
RbTreeNode<T>* RbTree<T>::ssearch(T key){return ssearch(Root, key);
}//查找最小结点，并返回值为根结点
template<class T>
RbTreeNode<T>* RbTree<T>::minimum(RbTreeNode<T>* tree){if (tree == nil)    {return nil;}while (tree->left != nil)    {tree = tree->left;}return tree;
}template<class T>
T RbTree<T>::minimum()
{RbTreeNode<T>* p = minimum(Root);if (p != nil)    {return p->key;}return T(NULL);
}//查找最大结点，并返回值为根结点
template<class T>
RbTreeNode<T>* RbTree<T>::maximum(RbTreeNode<T>* tree){if (tree == nil)    {return nil;}while (tree->right != nil)    {tree = tree->right;}return tree;
}template<class T>
T RbTree<T>::maximum(){RbTreeNode<T>* p = maximum(Root);if (p != nil)    {return p->key;}return T(NULL);
}//找结点x的前驱结点即，查找"红黑树中数据值小于该结点"的"最大结点"。
template<class T>
RbTreeNode<T>* RbTree<T>::predecessor(RbTreeNode<T>* x)
{// 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。if (x->left != nil)    {return maximum(x->left);}// 如果x没有左孩子。则x有以下两种可能：// 1. x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。// 2. x是"一个左孩子"，则查找"x的父结点，并且该父结点要为右孩子"，找到的这个"父结点的父结点"就是"x的前驱结点"。RbTreeNode<T>* p = x->parent;while (x != p->right && p)    {x = p;p = p->parent;}return p;
}//找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
template<class T>
RbTreeNode<T>* RbTree<T>::successor(RbTreeNode<T>* x){// 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。if (x->right != nil)    {return minimum(x->right);}// 如果x没有右孩子。则x有以下两种可能：// 1. x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。// 2. x是"一个右孩子"，则查找"x的父结点，并且该父结点要为左孩子"，找到的这个"父结点的父结点"就是"x的后继结点"。RbTreeNode<T>* p = x->parent;if (p->left != x && p)    {x = p;p = p->parent;}return p;
}//左旋示意图(对结点x进行左旋)：
//     px                              px
//     /                               /
//    x                               p
//   /  \      --(以x的左旋)-->      / \        （颜色不变）
//  lx   p                          x  rp
//      / \                        / \
//     lp  rp                     lx lptemplate<class T>
void RbTree<T>::Left_rotation(RbTreeNode<T>*& root, RbTreeNode<T>* x)
{RbTreeNode<T>* p = x->right;x->right = p->left;if (p->left != nil){p->left->parent = x;}p->parent = x->parent;if (x->parent == nil){root = p;}else{if (x->parent->left == x){x->parent->left = p;}else{x->parent->right = p;}}x->parent = p;p->left = x;
}// 右旋示意图(对结点y进行右旋)：
//            py                               py
//           /                                /
//          y                                p
//         /  \      --(右旋)-->            /  \
//        p   ry                           lp   y
//       / \                                   / \
//      lp  rp                                rp  rytemplate<class T>
void RbTree<T>::Right_rotation(RbTreeNode<T>*& root, RbTreeNode<T>* y){RbTreeNode<T>* p = y->left;y->left = p->right;if (p->right != nil){p->right->parent = y;}p->parent = y->parent;if (y->parent != nil){if (y->parent->left = y){y->parent->left = p;}else{y->parent->right = p;}}else{root = p;}p->right = y;y->parent = p;
}//红黑树插入修正函数// 在向红黑树中插入结点之后(失去平衡)，再调用该函数；
// 目的是将它重新塑造成一颗红黑树。/*
总共有四种情景：
1：红黑树为空树时  ——>  把插入结点作为根节点，并把颜色设置为黑色。
2：插入结点的key已存在  ——>  把插入结点设为当前结点的颜色，更新当前结点的值为插入结点的值。
3：插入结点的父结点为黑色结点  ——>  直接插入。
4：插入结点的父结点为红色结点4.1：叔叔结点存在且为红色结点  ——>  将父亲结点和叔叔结点设为黑色，祖父结点设为红色，将祖父结点设为插入结点。4.2：叔叔结点不存在或为黑色结点，并且插入结点的父亲结点是祖父结点的左孩子结点4.2.1：插入结点是其父亲结点的左孩子结点  ——>  将父亲结点设为黑色，将祖父结点设为红色，对祖父结点进行右旋。4.2.2：插入结点是其父亲结点的右孩子结点  ——>  对父亲结点进行左旋，将父亲结点设为插入结点得到4.2.1，进行4.2.1的操作。4.3：叔叔结点不存在或为黑色结点，并且插入结点的父亲结点是祖父结点的右孩子结点4.3.1：插入结点是其父亲结点的右孩子结点  ——>  将父亲结点设为黑色，将祖父结点设为红色，对祖父结点进行左旋。4.3.2：插入结点是其父亲结点的左孩子结点  ——>  对父亲结点进行右旋，将父亲结点设为插入结点得到4.3.1，进行4.3.1的操作。
*/template<class T>
void RbTree<T>::iinsert_fixup(RbTreeNode<T>*& root, RbTreeNode<T>* x){RbTreeNode<T>* parent;RbTreeNode<T>* gparent;while ((parent = x->parent) && parent->color == RED) {       //父结点存在且为红色gparent = parent->parent;if (gparent->left == parent)       //父结点为祖父结点的左孩子{RbTreeNode<T>* uncle = gparent->right;//4.1：叔叔结点存在且为红色结点  ——>  将父亲结点和叔叔结点设为黑色，祖父结点设为红色，将祖父结点设为插入结点if (uncle && uncle->color == RED){parent->color = BLACK;uncle->color = BLACK;gparent->color = RED;x = gparent;continue;}//4.2.2：插入结点是其父亲结点的右孩子结点  ——>  对父亲结点进行左旋，将父亲结点设为插入结点得到4.2.1，进行4.2if (parent->right == x){RbTreeNode<T>* t;Left_rotation(root, parent);t = parent;parent = x;x = t;}//4.2.1：插入结点是其父亲结点的左孩子结点  ——>  将父亲结点设为黑色，将祖父结点设为红色，对祖父结点进行右旋。parent->color = BLACK;gparent->color = RED;Right_rotation(root, gparent);}else         //父结点为祖父结点的右孩子{RbTreeNode<T>* uncle = gparent->left;//4.1：叔叔结点存在且为红色结点  ——>  将父亲结点和叔叔结点设为黑色，祖父结点设为红色，将祖父结点设为插入结if (uncle && uncle->color == RED){parent->color = BLACK;uncle->color = BLACK;gparent->color = RED;x = gparent;continue;}//4.3.2：插入结点是其父亲结点的左孩子结点  ——>  对父亲结点进行右旋，将父亲结点设为插入结点得到4.3.1，进行4.3.1的操作。if (x == parent->left){RbTreeNode<T>* t;Right_rotation(root, parent);t = parent;parent = x;x = t;}//4.3.1：插入结点是其父亲结点的右孩子结点  ——>  将父亲结点设为黑色，将祖父结点设为红色，对祖父结点进行左旋。parent->color = BLACK;gparent->color = RED;Left_rotation(root, gparent);}}root->color = BLACK;
}//将结点x插入到红黑树中
template<class T>
void RbTree<T>::iinsert(RbTreeNode<T>*& r, RbTreeNode<T>*& x){RbTreeNode<T>* y = nil;RbTreeNode<T>* z = r;while (z != nil)    {y = z;if (x->key < z->key)        {z = z->left;}else{z = z->right;}}x->parent = y;if (y == nil)    {                  //树里面没有元素r = x;}else if (x->key < y->key)    {      //树里面只有一个元素y->left = x;}else    {y->right = x;}x->left = nil;x->right = nil;iinsert_fixup(r, x);
}template<class T>
void RbTree<T>::iinsert(T key){RbTreeNode<T>* z = nil;if ((z = new RbTreeNode<T>(RED, key, nil, nil, nil)) == nil){return;}iinsert(Root, z);
}/*
三种删除结点的情景我们以下将删除结点称为z，替代z位置的结点称为y(y为z的后继结点或z结点本身)1：如果y是叶子结点，则直接删除即可。
2：如果y只有一个孩子，则将父结点的指针指向它的孩子。
3：如果y有两个孩子，则可以找它的后继，将值覆盖过来，之后情况转变成删除后继结点，回到1和2。当删除结点后，若待删除结点为红色时，红黑树性质仍然保持
1：树中的黑高没有改变。
2：不存在两个相邻的红结点。因为待删除结点在树中占据了删除结点的位置，考虑到删除结点的颜色，树中待删除结点的新位置不可能有两个相邻的红结点。另外，如果，待删除结点不是删除结点的右孩子，则待删除结点的原右孩子代替待删除结点。如果待删除结点是红色，则它的右孩子一定是黑色，因此用右孩子来代替不可能使两个红结点相邻。
3：如果待删除结点是红色，就不可能是根结点，所以根结点仍旧为黑色。这样当待删除结点为黑色结点时进行修复
约定：  x ——> 代替y位置的结点p ——> x的父结点w ——> x的兄弟结点wl ——> w的左子结点wr ——> w的右子结点1：x是p的左子结点1.1：w是红色结点  ——>  w设为黑色，p设为红色，对p左旋，得到1.2进行处理1.2：w是黑色结点1.2.1：wr是红结点，wl任意颜色  ——>  w设为p颜色，p设为黑色，wr设为黑色，对p进行左旋1.2.2：wr是黑结点，wl是红结点  ——>  w设为红色，wl设为黑色，对w进行右旋，得到1.2.1处理1.2.3：wr与wl都为黑结点  ——>  w设为红色，p作为新的代替待删除结点的结点，重新进行修复处理
2：x是p的右子结点2.1：w是红结点  ——>  w设为黑色，p设为红色，对p右旋，得到2.2进行处理2.2：w是黑结点2.2.1：wl是红结点，wr任意颜色  ——>  w设为p颜色，p设为黑色，wl设为黑色，对p进行右旋2.2.2：wl是黑结点，wr是红结点  ——>  w设为红色，wr设为黑色，对w进行左旋，得到2.2.1处理2.2.3：wr与wl都为黑结点  ——>  w设为红色，p作为新的代替待删除结点的结点，重新进行修复处理
*/template<class T>
void RbTree<T>::delete_fixup(RbTreeNode<T>*& root, RbTreeNode<T>* x){while (x != root && x->color == BLACK)    {if (x == x->parent->left)               //1：x是p的左子结点{RbTreeNode<T>* w = x->parent->right;//1.1：w是红色结点  ——>  w设为黑色，p设为红色，对p左旋，得到1.2进行处理if (w->color == RED){w->color = BLACK;x->parent->color = RED;Left_rotation(root, x->parent);w = x->parent->right;}//1.2：w是黑色结点//1.2.3：wr与wl都为黑结点  ——>  w设为红色，p作为新的代替待删除结点的结点，重新进行修复处理if (w->left->color == BLACK && w->right->color == BLACK){w->color = RED;x = x->parent;}else{//1.2.2：wr是黑结点，wl是红结点  ——>  w设为红色，wl设为黑色，对w进行右旋，得到1.2.1处理if (w->right->color == BLACK){w->color = RED;w->left->color = BLACK;Right_rotation(root, w);w = x->parent->right;}//1.2.1：wr是红结点，wl任意颜色  ——>  w设为p颜色，p设为黑色，wr设为黑色，对p进行左旋w->color = x->parent->color;x->parent->color = BLACK;w->right->color = BLACK;Left_rotation(root, x->parent);x = root;}}else          //2：x是p的右子结点{RbTreeNode<T>* w = x->parent->left;//2.1：w是红结点  ——>  w设为黑色，p设为红色，对p右旋，得到2.2进行处理if (w->color == RED){w->color = BLACK;x->parent->color = RED;Right_rotation(root, x->parent);w = x->parent->left;}//2.2：w是黑结点//2.2.3：wr与wl都为黑结点  ——>  w设为红色，p作为新的代替待删除结点的结点，重新进行修复处理if (w->left->color == BLACK && w->right->color == BLACK){w->color = RED;x = x->parent;}else{//2.2.2：wl是黑结点，wr是红结点  ——>  w设为红色，wr设为黑色，对w进行左旋，得到2.2.1处理if (w->left->color == BLACK){w->color = RED;w->right->color = BLACK;Left_rotation(root, w);w = x->parent->left;}//2.2.1：wl是红结点，wr任意颜色  ——>  w设为p颜色，p设为黑色，wl设为黑色，对p进行右旋w->color = x->parent->color;x->parent->color = BLACK;w->left->color = BLACK;Right_rotation(root, x->parent);x = root;}}}x->color = BLACK;
}template<class T>
void RbTree<T>::Rb_transplant(RbTreeNode<T>*& root, RbTreeNode<T>*& u, RbTreeNode<T>*& v){if (u->parent == nil){root = v;}else if (u == u->parent->left){u->parent->left = v;}else u->parent->right = v;v->parent = u->parent;
}template<class T>
void RbTree<T>::ddelete(RbTreeNode<T>*& root, RbTreeNode<T>* z){     //删除z节点RbTreeNode<T>* y = z;         //替代z位置的结点称为yRbTreeNode<T>* x = z;         //代替y位置的结点int color = y->color;if (z->left == nil)              //如果删除结点为叶子结点直接删除 或没有左孩子时让父指针指向右孩子{x = z->right;Rb_transplant(root, z, z->right);}else if (z->right == nil)           //如果删除结点为叶子结点直接删除 或没有右孩子时让父指针指向左孩子{x = z->left;Rb_transplant(root, z, z->left);}else                               //删除结点有两个孩子{y = successor(z);            //y变为删除结点的后继结点color = y->color;x = y->right;if (y->parent == z)            //y恰好为删除结点的孩子结点{x->parent = y;}else                            //y不为删除结点的孩子结点{Rb_transplant(root, y, y->right);           //先将y的父指针指向右孩子（将x变为y的位置）y->right = z->right;y->right->parent = y;               //y与删除结点的右孩子连接}Rb_transplant(root, z, y);                 //将删除结点父指针指向yy->left = z->left;y->left->parent = y;                    //y与删除结点的左孩子连接y->color = z->color;}if (color == BLACK)             //y为黑色结点需要进行修复{delete_fixup(root, x);}
}template<class T>
void RbTree<T>::ddelete(T key){RbTreeNode<T>* z = nil;if ((z = ssearch(key)) == nil)    {return;}ddelete(Root, z);
}template<class T>
void RbTree<T>::print(RbTreeNode<T>* tree, T key, int d){if (tree != nil)    {if (d == 0){cout << setw(2) << tree->key << " is root";if (tree->color == 0){cout << "（RED" << "）" << endl;}else{cout << "（BLACK" << "）" << endl;}}else{cout << setw(2) << tree->key << " is " << setw(2) << key << "'s" << setw(12) << (d == 1 ? "right child" : "left child");if (tree->color == 0){cout << "（RED" << "）" << endl;}else{cout << "（BLACK" << "）" << endl;}}print(tree->left, tree->key, -1);print(tree->right, tree->key, 1);}
}template<class T>
void RbTree<T>::print()
{if (Root != nil){print(Root, Root->key, 0);}
}template <class T>
void RbTree<T>::destroy(RbTreeNode<T>*& tree)
{if (tree == nil){return;}if (tree->left != nil){destroy(tree->left);}if (tree->right != nil){destroy(tree->right);}delete tree;
}template <class T>
void RbTree<T>::destroy()
{destroy(Root);
}int main()
{int a, n;RbTree<int>* tree = new RbTree<int>();cout << "请输入结点个数：";cin >> n;cout << "请输入结点的键值：";for (int i = 1; i <= n; i++){cin >> a;tree->iinsert(a);}cout << "\n前序遍历：";tree->preOrder();cout << "\n中序遍历：";tree->inOrder();cout << "\n后序遍历：";tree->postOrder();cout << endl;cout << "最小值：" << tree->minimum() << endl;cout << "最大值：" << tree->maximum() << endl;cout << "整棵树：" << endl;tree->print();int x;cout << "\n请输入要删除的结点的结点值：";cin >> x;tree->ddelete(x);cout << "\n删除" << x << "结点后整棵树：";tree->print();tree->destroy();return 0;
}

————————————————

相关引用

  1. CSDN博主「小七mod」原文链接：https://blog.csdn.net/cy973071263/article/details/122543826 ↩︎

  2. 原文链接：https://blog.csdn.net/chenlong_cxy/article/details/121481859 ↩︎

  3. 原文链接：https 😕/blog.csdn.net/hahahahahaha5/article/details/122507258 ↩︎


http://chatgpt.dhexx.cn/article/MGM2JGkV.shtml

相关文章

什么是红黑树（内存最优的二叉树）

什么是红黑树（内存最优的二叉树）

一.红黑树定义 红黑树(Red Black Tree) 是一种自平衡二叉查找树&#xff0c;是在计算机科学中用到的一种数据结构&#xff0c;典型的用途是实现关联数组。 它是在1972年由Rudolf Bayer发明的&#xff0c;当时被称为平衡二叉B树(symmetric binary B-trees)。后来&#xff0c;在1…
阅读更多...
【二叉树进阶】红黑树（Red Black Tree） - 平衡二叉搜索树

【二叉树进阶】红黑树（Red Black Tree） - 平衡二叉搜索树

文章目录 一、红黑树的概念二、红黑树的性质2.1 红黑树和AVL树效率对比 三、红黑树的结构&#xff08;KV模型&#xff09;四、红黑树的插入4.1 插入节点4.2 平衡化操作&#xff08;难点&#xff09;4.2.1 情况一4.2.2 情况二4.2.3 情况三 4.3 总结 五、红黑树的验证六、红黑树的…
阅读更多...
MySQL 慢查询日志导入 Elasticsearch 可视化查询分析

MySQL 慢查询日志导入 Elasticsearch 可视化查询分析

当应用程序后台 SQL 查询慢的时候我们一般第一时间会查看数据库慢查询记录&#xff0c;但是慢查询记录是原始文本&#xff0c;直接查询搜索分析比较费时费力&#xff0c;虽然业界有针对 MySQL 慢查询分析的命令行工具&#xff08;比如&#xff1a;pt-query-digest&#xff09;&…
阅读更多...
MySQL 慢查询日志如何查看及配置

MySQL 慢查询日志如何查看及配置

简介 MySQL 慢查询日志是排查问题 SQL 语句&#xff0c;以及检查当前 MySQL 性能的一个重要功能。 查看是否开启慢查询功能&#xff1a; 说明&#xff1a; slow_query_log 慢查询开启状态 slow_query_log_file 慢查询日志存放的位置&#xff08;这个目录需要MySQL的运行帐号的…
阅读更多...
MySQL高级篇——聊聊MySQL的慢查询日志

MySQL高级篇——聊聊MySQL的慢查询日志

文章目录&#xff1a; 1.数据库服务器的优化步骤 2.查看系统性能参数 3.定位执行慢的 SQL&#xff1a;慢查询日志 4.查看 SQL 执行成本&#xff1a;SHOW PROFILE 1.数据库服务器的优化步骤 当我们遇到数据库调优问题的时候&#xff0c;该如何思考呢&#xff1f;这里把思考…
阅读更多...
清理mysql慢查询日志_MySQL清理慢查询日志slow_log的方法

清理mysql慢查询日志_MySQL清理慢查询日志slow_log的方法

一、清除原因 因为之前打开了慢查询，导致此表越来越大达到47G，导致磁盘快被占满，使用xtrabackup进行备份的时候文件也超大。 mysql> show variables like log_output%; Connection id: 1694401091 Current database: mysql +---------------+-------+ | Variable_name | …
阅读更多...
mysql 慢查询日志的设置与优化

mysql 慢查询日志的设置与优化

目录 1 引言 2 慢查询日志配置 3 分析工具 1 引言 MySQL数据中有记录慢查询的一种手段。并且是MySQL自带的。可用来排查那些查询sql语句执行得慢。从而给开发者提供一个调优得依据。 MySQL 慢查询的相关参数解释&#xff1a; slow_query_log &#xff1a;是否开启慢查…
阅读更多...
如何开启mysql慢查询日志？

如何开启mysql慢查询日志？

1、查看mysql的慢查询日志是否开启 show variables like %query%; 可以看到slow_query_log的值是OFF&#xff0c;也就是mysql默认是不启用慢查询日志的。 这里还有个long_query_time&#xff0c;默认是10秒&#xff0c;也就是超过了10秒即为慢查询。 log_queries_not_using_…
阅读更多...
MySQL慢查询日志详解

MySQL慢查询日志详解

本次代码执行环境的mysql版本是 &#xff1a;5.6.37-log 1.慢查询日志概念(也叫慢日志):在 MySQL 中执行时间超过指定时间的 SQL 语句 2.常见的几个相关的变量 (可以直接去mysql下的配置文件my.cnf文件中去改,我下面是直接在SQLyog中进行操作) 默认情况下慢查询日志是关闭的…
阅读更多...
MySQL 慢查询日志 使用方法浅析 日志定位与优化技巧

MySQL 慢查询日志 使用方法浅析 日志定位与优化技巧

目录 前言 1、如何开启使用慢查询日志&#xff1f; 1.1 开启慢查询日志 1.2 设置慢查询阈值 1.3 确定慢查询日志的文件名和路径 1.3.1 查询MySQL数据目录 1.3.2 查询慢查询日志文件名 1.3.3 查询全局设置变量 1.3.4 查询单个变量命令 1.3.5 其他注意事项 2、如何定位并优…
阅读更多...
mysql慢查询日志在哪里

mysql慢查询日志在哪里

如何查找MySQL中查询慢的SQL语句 你是指慢查询日志吗&#xff1f; 在my.ini中加上下面两句话 log-slow-queriese:\mysql5.5\mysql_slow_query.log long_query_time10 前面一句是设置慢查询日志存放路径&#xff0c;第二句是指多少秒以上算慢查询&#xff0c;上面的语句&#xf…
阅读更多...
MySQL慢查询日志分析

MySQL慢查询日志分析

&#xff08;1&#xff09;慢查询日志 MySQL提供了慢SQL的日志记录功能&#xff0c;我们可以通过设置一些属性来记录系统使用过程中慢查询的执行日志。使用MySQL慢查询日志对有效率问题的SQL进行监控。 查看属性 【1】查看MySQL是否开启慢查询日志记录功能 show variables l…
阅读更多...
MySQL优化之慢日志查询

MySQL优化之慢日志查询

目录 一、慢查询日志(slow_query_log)概念二、慢查询日志实践1. 打开慢查询日志开关2. 设置合理的、业务可以接受的慢查询时间上限long_query_time3. 压测执行各种业务4. 查看慢查询日志5. 用explain分析这些耗时的sql语句&#xff0c;从而针对性优化 三、show profiles查看sql…
阅读更多...
MySQL日志（一）—— 慢查询日志slow log

MySQL日志（一）—— 慢查询日志slow log

一、慢查询日志&#xff08;slow log&#xff09; 慢查询日志&#xff0c;就是查询超过一定的时间没有返回结果的时候&#xff0c;MySQL会将执行的SQL记录到日志中&#xff0c;这个日志&#xff0c;就称为慢查询日志。通过分析慢查询日志&#xff0c;可以快速找出执行慢的SQL语…
阅读更多...
【OpenCv3】 VS C++ （五）：SLIC超像素分割算法

【OpenCv3】 VS C++ （五）：SLIC超像素分割算法

下一节地址&#xff1a;https://blog.csdn.net/qq_40515692/article/details/102788157 OpenCv专栏&#xff1a;https://blog.csdn.net/qq_40515692/article/details/102885061 超像素&#xff08;SuperPixel&#xff09;&#xff0c;就是把原本多个像素点&#xff0c;组合成一…
阅读更多...
superpixels(超像素）

superpixels(超像素）

superpixels(超像素&#xff09; 1.理解&#xff1a; 超像素不是在普通的像素基础上继续微观细分&#xff0c;超像素是一系列像素的集合&#xff0c;这些像素具有类似的颜色、纹理等特征&#xff0c;距离也比较近。其中超像素比较常用的一种方法是SLIC Semantic Segmentatio…
阅读更多...
Seeds超像素分割

Seeds超像素分割

#%% SEED超像素分割 import cv2 import numpy as np import imageio # print(dir(cv2.ximgproc))img imageio.imread(rE:\Vaihingen\data\orginalimages\top_mosaic_09cm_area31.tif)[:,:,::-1] converted_img cv2.cvtColor(img, cv2.COLOR_BGR2HSV)# print(type(img_feature…
阅读更多...
Python实现超像素分割

Python实现超像素分割

目录 一、什么是超像素&#xff1f;二、超像素具有哪些特点&#xff1f;三、Simple Linear Iterative Clustering (SLIC)算法实现步骤四、SLIC算法代码实现五、效果展示和分析六、基于超像素的边缘检测代码七、基于超像素的边缘检测效果展示与分析八、思维扩展参考资料注意事项…
阅读更多...
基于Matlab的SLIC超像素分割算法分析

基于Matlab的SLIC超像素分割算法分析

SLIC超像素分割算法分析 1&#xff1a;导入原始照片&#xff0c;初始化聚类中心&#xff0c;按照设定的超像素个数&#xff0c;在图像内均匀的分配聚类中心。假设图片总共有 N 个像素点&#xff0c;预分割为 s 个相同尺寸的超像素&#xff0c;那么每个超像素的大小为N/ s &…
阅读更多...
超像素分割算法————综述

超像素分割算法————综述

参考&#xff1a;超像素—学习笔记 什么是超像素&#xff1f;评价标准&#xff1f;SLIC、SEED、ETPS算法 比较的指标&#xff1a;图像边界的粘附性、算法速度、存储效率、分割性能 超像素算法&#xff1a;将像素组合成感知有意义的原子区域( atomic regions)&#xff0c;其可…
阅读更多...
推荐文章

Copyright @ 2022~2023