数据结构(13)——平衡二叉树(红黑树)

2024-09-04 20:12

本文主要是介绍数据结构(13)——平衡二叉树(红黑树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

欢迎来到博主的专栏——数据结构
博主ID:代码小号

文章目录

    • 红黑树
      • 红黑树节点之间的关系
      • 红黑树的插入
        • uncle节点为红色
        • uncle节点是黑色或者没有uncle节点

红黑树

平衡二叉树最出名的除了AVL树之外就是红黑树(RBTree),所谓红黑树,即拥有以下特性的平衡二叉树

(1)每个节点要么是红色,要么是黑色
(2)根节点必须是黑色
(3)红色节点的子节点必须是黑色
(4)每条路径上的黑色节点个数相同。

红黑树中所谓的路径,并非是从根节点到叶节点经过的所有节点,而是从根节点到NULL节点之间的路径。

以下图为例,该红黑树具有的路径有:
在这里插入图片描述

ok,从上图我们也可以看出,红黑树节点至少有5个对象,分别是指向左右子树的指针,指向父节点的指针,值,以及颜色。那么红黑树节点的定义应该如下:

enum colour
{RED,BLACK
};
template<class key,class value>
struct RBtreeNode
{pair<key, value> _kv;//值RBtreeNode<key, value>* _right;//右子树RBtreeNode<key, value>* _left;//左子树RBtreeNode<key, value>* _parent;//父节点colour _col;//颜色
};

为什么说红黑树也是平衡二叉树?它又是如何做到平衡的呢?

假设一颗红黑树路径的黑色节点为4个,那么可能最短路径为:
在这里插入图片描述
最长路径为:
在这里插入图片描述

由此可得,在一颗路径黑色节点个数为N的红黑树中。最短路径*2>=最长路径。假设在最短路径上进行插入,时间复杂度为O(logN),在最短路径上进行插入的时间复杂度为O(log2N),那么也就说明红黑树即使是在最差的情况下,也能保持插入和查找的对数级的时间复杂度,效率还是很不错的。

由于红黑树的插入与删除与搜索二叉树逻辑相同,只是多了调整平衡二叉树的操作,因此博主不多赘述插入,删除的相关操作,重点讲解如何调整红黑树。

平衡二叉树的旋转操作,博主已在AVL树文章中讲解,甚至用的是与AVL树一样的旋转代码,因此也不多赘述。

红黑树节点之间的关系

假设在红黑树的某部分子树的形状如下:
在这里插入图片描述
假如当前节点cur为红,那么parent只能是黑,grandfather和uncle的颜色不确定。
在这里插入图片描述
如果parent为红,那么grandfather只能是黑色,记住这个结论,很重要。
在这里插入图片描述

假如grandfather是黑色,parent和uncle是红色,将grandfather转换成红色,parent和uncle都变成黑色,该路径下的黑色节点的个数不变。
在这里插入图片描述
这里说明了一个性质,那就是红黑树之间的节点的颜色其实是可以按照一定规律改变的。

红黑树的插入

uncle节点为红色

这里不讨论如何插入,只讲解如何保持红黑树的规则。

首要要考虑一个问题,新插入的节点是红色好还是黑色好?结论是插入的节点是红色比较好,因为我们可以假设插入节点为红色。那么会遇到两种情况
(1)插入在黑色节点之后,符合红黑树的特性
(2)插入在红色节点之后,不符合红黑树不允许红色节点连续的特性

如果插入节点为黑色,那么插入的路径的黑色节点一定会比其他路径多(因为红黑树要求每个路径的黑色节点相同,插入黑色节点会打破这个平衡)。两害相较取其轻,所以插入的节点视为红色,如果不符合特性再进行修改。

RBtreeNode(const pair<key,value>& kv):_kv(kv),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED)
{}

当我们插入红色节点时,可能会出现以下情况。
(1)插入在黑色节点之后:
红色节点插入在黑色节点之后是符合红黑树规则的,而且每个路径的黑色节点也没有改变,因此种情况是合法的,不用处理
(2)插入在红色节点之后
红黑树的特性是没有连续的红色节点,因此出现这种情况就需要对红黑树进行处理了。

假设插入的节点为cur,其父节点parent是红色节点,那么parent的父节点一定是黑色的,因为红色的节点不能相连,那么我们姑且将其称为祖父(grandfather)节点吧。

在这里插入图片描述

grandfather的右子树存不存在未知,我们先假设祖父节点存在右子树,那么祖父节点一定会只存在一个红色节点。称该节点为叔叔(uncle)节点。为什么叔叔节点一定会是红色呢?因为parent是红色的是确定的条件,因为如果parent是黑色的节点,插入这个红色的cur节点不会构成非法操作,也就不需要处理了,因此引发处理红黑树的条件一定是插入节点的父节点一定是红色的。

那么在这种情况下,uncle节点一定会是红色的,因为如果uncle节点是黑色的,那么祖父节点的左右子树的路径上的黑色节点数量就不一致了。这显然违反了红黑树的规定。
在这里插入图片描述
那么祖父的右边一定只有一个节点呢?因为uncle是红色的,那么uncle的子节点一定是黑色的,那么还是遇到了那个问题,祖父节点的左右子树的路径上黑色节点个数不相同,违反了红黑树的规则。因此如果cur插入在红色节点之后,且祖父节点存在右树时,有且只有这么一种请况:
在这里插入图片描述
那么该怎么处理呢?首先这个情况非法的原因就是parent和cur是连续的红色节点,那么将其改变成黑白相间即可。但无论是parent或者cur变成黑色节点,都会破坏红黑树在路径上的黑色个数。那么我们就不能单独修改某个节点,而是要一起改。其实方法在上面博主已经给出了,博主这里直接截图吧。

在这里插入图片描述
我们让parent和uncle改成黑色,grandfather变成红色,就能解决问题。
在这里插入图片描述
代码如下:

我们先写出检查红黑树的代码:

void keep_balance(Node* parent,Node* cur)
{while (parent != nullptr && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent)//父节点在左{}else//父节点在右{}}_root->_col = BLACK;
}

现在grandfather的节点变成红色节点了。那么grandfather的父节点是可能出现红色节点,或者黑色节点的,如果grandfather的父节点是黑色节点,那就说明不需要调整了,已经符合了红黑树的操作。如果grandfather的父节点也是红色节点,那么由于出现了红色节点,那么我们需要对grandfather和grandfather的父节点进行调整。
在这里插入图片描述

以此类推,直到根节点。如果根节点变红,由于红黑树规定根节点不能是红色,因此需要将根节点变黑。
在这里插入图片描述
将根节点变黑相当于给红黑树的所有路径都加了一个黑节点,因此将根节点变黑这个操作在任何情况下都是合法的。所以我们可以直接在程序的最后让根节点变成黑色。

if (grandfather->_left == parent)//uncle节点在grandfather的左子节点
{Node* uncle = grandfather->_right;if(uncle!=nullptr&&uncle->_col==RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}
}
uncle节点是黑色或者没有uncle节点

前面提到的条件是uncle节点是红色的情况,但是uncle节点可能会出现没有或者是黑色这两种情况。

当我们插入cur节点时,如果和parent同样都是红色,就要进行调整,此时uncle节点一定是没有,或者是红色的,不可能存在uncle节点是黑色的情况。
在这里插入图片描述
这是因为,如果uncle节点是黑色,就不符合每个路径的黑色节点个数相同的特性。
在这里插入图片描述
因此只能是uncle节点不存在。如果出现这种情况,我们就要使用旋转的方式将子树进行旋转了。因为很明显子树已经不平衡了,左子树有两个节点,而右子树没有节点,因此需要旋转。旋转也分为左单旋,右单旋,右左单旋和左右单旋,这方面的操作与AVL树的旋转无异,因此博主不再赘述。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
如果是在向上更新节点的时候,就会遇到uncle是黑色的情况。比如:
在这里插入图片描述

此时的cur节点是由于红黑树向上更新节点颜色时变成红色的,此时也需要旋转。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

整体的平衡代码如下:

void keep_balance(Node* parent,Node* cur)
{while (parent != nullptr && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent)//父节点在左{Node* uncle = grandfather->_right;if(uncle!=nullptr&&uncle->_col==RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else {if (parent->_left == cur){rotateR(grandfather);//右单旋parent->_col = BLACK;grandfather->_col = RED;}else{rotateLR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//父节点在右{Node* uncle = grandfather->_left;if (uncle != nullptr && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_right == cur){rotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else if (parent->_left == cur){rotateRL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;
}

这篇关于数据结构(13)——平衡二叉树(红黑树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

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

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

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)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据,每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明: 1. 列表 (List) 列表是一种可变的有序集合,可以存放任意类型的数据。列表中的元素可以通过索

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo