【数据结构】手撕红黑树

2024-02-13 21:59
文章标签 数据结构 黑树 撕红

本文主要是介绍【数据结构】手撕红黑树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

 目录

一、红黑树简介

1、红黑树的简介

2、红黑树的性质

二、红黑树的插入（看叔叔的颜色就行）

1、为什么新插入的节点必须给红色？

2、插入红色节点后，判定红黑树性质是否被破坏

2.1情况一：uncle存在且为红

2.2情况二：uncle不存在/存在且为黑（直线）

2.3情况三：uncle不存在/存在且为黑（折线）

2.4总结

3、红黑树插入代码

三、红黑树的平衡检测

四、红黑树整体代码

一、红黑树简介

1、红黑树的简介

        红黑树和AVL树一样，因其逻辑复杂，面试时现场要求手撕就是纯纯刁难面试者。但某大厂面试官曾要求某些求职者现场手撕红黑树（我赌5毛，让面试官撕，他也撕不出来，而且你家员工上班手搓红黑树啊？），随后求职遭遇被发到网上吐槽，这便有了“手撕红黑树”的梗，也让红黑树成为了知名度最高的数据结构。（话虽如此，对于红黑树的性质、插入思想等概念还是需要掌握的）

2、红黑树的性质

        红黑树本质也是一种二叉搜索树。底层结构需要使用二叉搜索树的地方，基本上都会使用红黑树来实现，而AVL树也因此坐上了冷板凳。

        红黑树通过在每个节点上添加一个存储位，用于存储“RED”或“BLACK”。通过节点上红/黑颜色限制，确保最长路径不超过最短路径的两倍，因而它是接近平衡的树形结构。最短路径：全黑；最长路径：一黑一红交替。

        1、红黑树的根节点是黑色的；

        2、没有连续的红色节点（如果某个节点为红色，则它的左右孩子必须是黑色）

        3、无论哪个节点，其每条路径的黑色节点数量相同；

        4、所有的空节点（NIL节点）可以认为是黑色的。

        最优情况：全黑或每条路径都是一黑一红的满二叉树，高度logN

        最差情况：每颗子树左子树全黑，右子树一黑一红。高度2*logN。

        可以发现，最坏情况的时间复杂度和AVL树一样，都是O(logN)，但是红黑树这种近似平衡的结构减少了大量旋转，综合性能优于AVL树。

二、红黑树的插入（看叔叔的颜色就行）

1、为什么新插入的节点必须给红色？

        新节点给红色，可能会违反上面说的红黑树性质2；如果新节点给黑色，必定会违反性质3。

2、插入红色节点后，判定红黑树性质是否被破坏

        情况一调整后可能变成情况一、情况二、情况三。

2.1情况一：uncle存在且为红

        这种情况cur、parent、grandfather都是确定颜色的，唯独uncle的颜色是不确定的。

        可以这么想：cur为红那么就需要将parent变为黑；parent变黑需要控制每条路径上黑节点的数量相同，那么就要把uncle变黑；如果grandfather不是根，需要反转为红，用以控制路径黑节点数量相同。继续向上调整即可。

2.2情况二：uncle不存在/存在且为黑（直线）

        uncle的情况分两种。

uncle不存在，则cur为插入节点，单旋即可。

uncle存在且为黑是第一种情况变过来的。

2.3情况三：uncle不存在/存在且为黑（折线）

        uncle的情况分两种。

uncle不存在，则cur为插入节点，两次单旋即可。

uncle存在且为黑，先掰直

2.4总结

        插入新节点时，父节点为红，看叔叔的颜色。

        1、叔叔存在且为红，变色，向上调整（可能变为三种情况中的任意一种）

        2、叔叔不存在/存在且为黑，直线。单旋+变色

        3、叔叔不存在/存在且为黑，折线，两次单旋+变色

3、红黑树插入代码

bool Insert(const pair<K,V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点给黑色return true;}//_root不为空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);cur->_col = RED;//新插入节点给红色，可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同，必定违反规则。  if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;//维护cur的父指针}else{parent->_left = cur;cur->_parent = parent;}//调整while (parent&&parent->_col == RED){Node* grandfather = parent->_parent;//找到祖父if (grandfather->_left == parent)//如果父亲是祖父的左孩子{Node* uncle = grandfather->_right;//找到叔叔//情况一：叔叔存在且为红if (uncle != nullptr && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//情况二或情况三{if (cur == parent->_left)//情况二，直线{RotateRight(grandfather);//右单旋parent->_col = BLACK;grandfather->_col = RED;}else//情况三，折线{RotateLeft(parent);//左单旋RotateRight(grandfather);//右单旋cur->_col = BLACK;grandfather->_col = RED;}break;}}else//如果父亲是祖父的右孩子{Node* uncle = grandfather->_left;if (uncle != nullptr && uncle->_col == RED){parent->_col =uncle->_col= BLACK;grandfather->_col = RED; cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right)//情况二，直线{//g//  p//    cRotateLeft(grandfather);//左单旋parent->_col = BLACK;grandfather->_col = RED;}else//情况三，折线{//g//  p//c   RotateRight(parent);//右单旋RotateLeft(grandfather);//左单旋cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col=BLACK;return true;
}

三、红黑树的平衡检测

bool Check(Node* root,int blackNum,const int ref)//检查有没有连续红节点
{if (root == nullptr){if (blackNum != ref){cout << "路径上黑节点数量不一致" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则，父子均为红" << endl;return false;}return Check(root->_left, blackNum,ref) && Check(root->_right, blackNum, ref);
}
bool _IsBalance()
{if (_root == nullptr)return true;if (_root->_col != BLACK){return false;}//数一下一条路径黑色节点数量int ref = 0;//统计一条路上黑色节点的数量Node* left = _root;while (left != nullptr){if (left->_col == BLACK){++ref;}left = left->_left;}return Check(_root,0,ref);
}

        1、在_IsBalance中确定号一条路径中黑色节点的数量，作为参数传递给Check函数，Check函数需要在递归至根节点时，统计，每条路径黑色节点数量是否和基准值ref相等。

        2、Check函数中还需要判断：子节点为红，父节点也为红（此时不平衡）

四、红黑树整体代码

#pragma once
#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;
enum Color
{RED,BLACK,
};
template <class K,class V>
struct RBTreeNode
{RBTreeNode(const pair<K,V>& kv):_parent(nullptr),_left(nullptr),_right(nullptr),_kv(kv),_col(RED){}RBTreeNode<K,V>* _parent;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;pair<K, V> _kv;Color _col;
};
template <class K, class V>
class RBTree
{
public:typedef RBTreeNode<K,V> Node;bool Insert(const pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点给黑色return true;}//_root不为空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);cur->_col = RED;//新插入节点给红色，可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同，必定违反规则。  if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;//维护cur的父指针}else{parent->_left = cur;cur->_parent = parent;}//调整while (parent&&parent->_col == RED){Node* grandfather = parent->_parent;//找到祖父if (grandfather->_left == parent)//如果父亲是祖父的左孩子{Node* uncle = grandfather->_right;//找到叔叔//情况一：叔叔存在且为红if (uncle != nullptr && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//情况二或情况三{if (cur == parent->_left)//情况二，直线{RotateRight(grandfather);//右单旋parent->_col = BLACK;grandfather->_col = RED;}else//情况三，折线{RotateLeft(parent);//左单旋RotateRight(grandfather);//右单旋cur->_col = BLACK;grandfather->_col = RED;}break;}}else//如果父亲是祖父的右孩子{Node* uncle = grandfather->_left;if (uncle != nullptr && uncle->_col == RED){parent->_col =uncle->_col= BLACK;grandfather->_col = RED; cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right)//情况二，直线{//g//  p//    cRotateLeft(grandfather);//左单旋parent->_col = BLACK;grandfather->_col = RED;}else//情况三，折线{//g//  p//c   RotateRight(parent);//右单旋RotateLeft(grandfather);//左单旋cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col=BLACK;return true;}void Inorder(){_Inorder(_root);}bool IsBalance(){return _IsBalance();}
private:void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}bool Check(Node* root,int blackNum,const int ref)//检查有没有连续红节点{if (root == nullptr){if (blackNum != ref){cout << "路径上黑节点数量不一致" << endl;return false;}return true;}if (root->_col == BLACK){++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则，父子均为红" << endl;return false;}return Check(root->_left, blackNum,ref) && Check(root->_right, blackNum, ref);}bool _IsBalance(){if (_root == nullptr)return true;if (_root->_col != BLACK){return false;}//数一下一条路径黑色节点数量int ref = 0;//统计一条路上黑色节点的数量Node* left = _root;while (left != nullptr){if (left->_col == BLACK){++ref;}left = left->_left;}return Check(_root,0,ref);}void RotateLeft(Node* parent)//左单旋{Node* grandfather = parent->_parent;Node* cur = parent->_right;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (grandfather->_left == parent)//需要判定parent原来属于grandfather的哪一边grandfather->_left = cur;elsegrandfather->_right = cur;cur->_parent = grandfather;}parent->_right = cur->_left;if (cur->_left != nullptr)cur->_left->_parent = parent;cur->_left = parent;parent->_parent = cur;}void RotateRight(Node* parent)//右单旋{Node* grandfather = parent->_parent;Node* cur = parent->_left;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (grandfather->_left == parent){grandfather->_left = cur;cur->_parent = grandfather;}else{grandfather->_right = cur;cur->_parent = grandfather;}}parent->_parent = cur;parent->_left = cur->_right;if (cur->_right != nullptr)cur->_right->_parent = parent;cur->_right = parent;}
private:Node* _root=nullptr;
};
void TestAVLTree()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//int a[] = { 9,8,7,6,5,4,3,2,1};RBTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.Inorder();//cout << t.IsBalance() << endl;
}

这篇关于【数据结构】手撕红黑树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

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

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 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）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（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
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

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

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

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

四种遍历 #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 内置的一些数据结构

Python 内置的一些数据结构

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

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

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2