玩转红黑树：算法背后的平衡与旋转技巧

Ne0inhk

— 11 min read
玩转红黑树：算法背后的平衡与旋转技巧

文章目录

前言：红黑树也是一种旋转树，所以本质也是一颗二叉搜索树，红黑树（Red-Black Tree）是一种自平衡的二叉查找树（BST），它通过一组额外的规则确保树的平衡性，从而保证了在最坏情况下的查找、插入和删除操作的时间复杂度为 O(logn)。

红黑树的规则

  1. 节点颜色：每个节点要么是红色的，要么是黑色的。
  2. 根节点是黑色：树的根节点必须是黑色的。
  3. 红色节点的父节点是黑色的：不能有两个连续的红色节点（即红色节点不能相邻）。
  4. 每个叶子节点（NIL节点）是黑色的：虽然叶子节点没有存储数据，但在树的表示中，它们被视为黑色节点。
    (这个规则来源于《算法导论》等书籍上——每一个叶子结点（NIL）都是黑色的)
    在红黑树（Red-Black Tree）中，NIL节点指的是一种虚拟的“空”节点，它是树中的叶子节点。尽管这些节点本身并不存储数据，它们在红黑树的实现中非常重要，主要用来简化树的结构和算法。
  5. 从任何节点到其每个叶子节点的路径上，必须包含相同数量的黑色节点：这一规则确保了从根到叶子路径的平衡性。
  6. 插入时的修正操作：在插入新节点时，可能会破坏红黑树的性质，需要通过旋转和颜色变化来修复树。

红黑树的存储结构

红黑树的结构主要由 节点 和 树的关系 组成。每个节点包含了数据（键值对）、左右子节点指针、父节点指针和颜色。树通过这些指针将节点连接起来，形成一个具有平衡性质的二叉查找树。

  • 树的基本结构：每个节点都连接着左右子节点和父节点，确保树可以通过这些指针进行遍历、插入和删除操作。
  • 颜色：每个节点的颜色（红色或黑色）用于保证红黑树的平衡性。根据红黑树的性质，树的高度限制和搜索效率可以保持在O(logn) 时间复杂度。
// 枚举值表⽰颜⾊ enumColour{ RED, BLACK };// 这⾥我们默认按key/value结构实现 template<classK,classV>structRBTreeNode{// 这⾥更新控制平衡也要加⼊parent指针  pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<classK,classV>classRBTree{typedef RBTreeNode<K, V> Node;public:private: Node* _root =nullptr;};

红黑树插入一个值的大概过程以及代码实现

说明：下图中假设我们把新增结点标识为c(cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为g(grandfather)，p的兄弟标识为u（uncle）。

  1. 插入新节点：按照普通二叉查找树（BST）的方式插入新节点。新节点总是被插入为红色的，以便于稍后进行修复操作。
  2. 修复红黑树性质：插入新节点后，可能会违反红黑树的某些性质，特别是：
    可能会违反“两个红色节点不能相邻”这一规则。
    可能会导致根节点不是黑色的。
boolInsert(const pair<K, V>& kv){if(_root ==nullptr){ _root =newNode(kv); _root->_col = BLACK;returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(kv); cur->_col = RED;if(parent->_kv.first < kv.first){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;//...进行旋转、调整等操作

为了修复这些问题，需要进行颜色调整和树的旋转操作。

红黑树的调整（旋转部分）

红黑树的旋转，底层也是跟AVL树一样，有着右旋、左旋、左右旋、右左旋。不过旋转的次数相对更加少了，

  • 右旋：
voidRotateR(Node* parent){ Node* cur = parent->_left; Node* curright = cur->_right; parent->_left = curright;if(curright){ curright->_parent = parent;} cur->_right = parent; Node* ppnode = parent->_parent; parent->_parent = cur;if(ppnode ==nullptr){ _root = cur; cur->_parent =nullptr;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}
  • 左旋：
voidRotateL(Node* parent){ Node* cur = parent->_right; Node* curleft = cur->_left; parent->_right = curleft;if(curleft){ curleft->_parent = parent;} cur->_left = parent; Node* ppnode = parent->_parent; parent->_parent = cur;if(parent == _root){ _root = cur; cur->_parent =nullptr;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}

红黑树的调整（颜色部分）

  • 情况1只变⾊，不旋转。（u存在且为红）

c为红，p为红，g为⿊，u存在且为红，则将p和u变⿊，g变红。在把g当做新的c，继续往上更新。

在这里插入图片描述

分析：因为p和u都是红⾊，g是⿊⾊，把p和u变⿊，左边⼦树路径各增加⼀个⿊⾊结点，g再变红，相当于保持g所在⼦树的⿊⾊结点的数量不变，同时解决了c和p连续红⾊结点的问题，需要继续往上更新是因为，g是红⾊，如果g的⽗亲还是红⾊，那么就还需要继续处理；
如果g的⽗亲是⿊⾊，则处理结束了；
如果g就是整棵树的根，再把g变回⿊⾊。

情况2，单旋 + 变色。（ u不存在或者u存在且为黑）
c为红，p为红，g为⿊，u不存在或者u存在且为⿊。
u不存在，则c⼀定是新增结点。
u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。

在这里插入图片描述


分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转+变⾊。

如果p是g的左，c是p的左，那么以g为旋转点进⾏右单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

如果p是g的右，c是p的右，那么以g为旋转点进⾏左单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

情况3:，双旋+变色 （u不存在或者u存在且为⿊）
c为红，p为红，g为⿊，u不存在或者u存在且为⿊。
u不存在，则c⼀定是新增结点。
u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。

在这里插入图片描述


分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解
决问题，需要旋转+变⾊。

如果p是g的左，c是p的右，那么先以p为旋转点进⾏左单旋，再以g为旋转点进⾏右单旋，再把c变⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

如果p是g的右，c是p的左，那么先以p为旋转点进⾏右单旋，再以g为旋转点进⾏左单旋，再把c变⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

红黑树的插入代码实现

template<classK,classV>classRBTree{typedef RBTreeNode<K, V> Node;public:boolInsert(const pair<K, V>& kv){if(_root ==nullptr){ _root =newNode(kv); _root->_col = BLACK;returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(kv); cur->_col = RED;if(parent->_kv.first < kv.first){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(grandfather->_left == parent){// g// p u// Node* uncle = grandfather->_right;// uncle存在且为红if(uncle && uncle->_col == RED){// 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续往上处理 cur = grandfather; parent = cur->_parent;}else// uncle不存在，或者存在且为黑{if(cur == parent->_left){// 旋转+变色// g// p u//cRotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// 旋转+变色// g// p u// cRotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else{// g// u p Node* uncle = grandfather->_left;// 叔叔存在且为红，-》变色即可if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续往上处理 cur = grandfather; parent = cur->_parent;}else// 叔叔不存在，或者存在且为黑{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色// g// u p// cif(cur == parent->_right){RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}} _root->_col = BLACK;returntrue;}

红⿊树的查找

按⼆叉搜索树逻辑实现即可，搜索效率为 O(logN)

Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key){ cur = cur->_right;}elseif(cur->_kv.first > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}

检查红黑树是否平衡

这⾥获取最⻓路径和最短路径，检查最⻓路径不超过最短路径的2倍是不可⾏的，因为就算满⾜这个条件，红⿊树也可能颜⾊不满⾜规则，当前暂时没出问题，后续继续插⼊还是会出问题的。所以我们还是去检查4点规则，满⾜这4点规则，⼀定能保证最⻓路径不超过最短路径的2倍。

  1. 规则1枚举颜⾊类型，天然实现保证了颜⾊不是⿊⾊就是红⾊。
  2. 规则2直接检查根即可
  3. 规则3前序遍历检查，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲的颜⾊就⽅便多了。
  4. 规则4前序遍历，遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值，依次⽐较即可。
boolCheck(Node* root,int blackNum,constint refNum){if(root ==nullptr){// 前序遍历⾛到空时，意味着⼀条路径⾛完了 //cout << blackNum << endl;if(refNum != blackNum){ cout <<"存在⿊⾊结点的数量不相等的路径"<< endl;returnfalse;}returntrue;}// 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了 if(root->_col == RED && root->_parent->_col == RED){ cout << root->_kv.first <<"存在连续的红⾊结点"<< endl;returnfalse;}if(root->_col == BLACK){ blackNum++;}returnCheck(root->_left, blackNum, refNum)&&Check(root->_right, blackNum, refNum);}boolIsBalance(){if(_root ==nullptr)returntrue;if(_root->_col == RED)returnfalse;// 参考值 int refNum =0; Node* cur = _root;while(cur){if(cur->_col == BLACK){++refNum;} cur = cur->_left;}returnCheck(_root,0, refNum);}

Read more

前端实战：手把手教你实现浏览器通知功能

前端实战：手把手教你实现浏览器通知功能

前端入门：浏览器通知功能从0到1实现指南 作为前端学习者，你可能见过这样的场景：打开网页版聊天工具，就算把浏览器最小化，桌面也会弹出“新消息”提醒；或者某些网站的活动通知，会直接显示在电脑/手机桌面上。这种功能就是「浏览器桌面通知」，今天我们就从零开始，搞懂它、学会用它。 一、先搞懂3个基础问题 1. 什么是浏览器桌面通知？ 简单说，就是网页能在浏览器窗口外面（比如电脑桌面、手机屏幕）给你发提醒。哪怕浏览器最小化、甚至页面切到后台，只要权限允许，都能收到通知，不用一直盯着网页。 2. 什么时候会用到它？ 常见场景很贴近日常： * 网页版微信/QQ的新消息提醒； * 工作系统的审批提醒、任务到期通知； * 电商网站的订单状态更新（比如“你的快递已发货”）； * 新闻/小说网站的订阅内容更新提醒。 3. 用起来难吗？有什么限制？ 不难！核心就2步：先让用户同意开启通知（申请权限）

By Ne0inhk
【前端】前端面试题

【前端】前端面试题

前端面试题 闭包 1. 定义： 闭包（Closure） 是指一个函数能够访问并记住其外部作用域中的变量，即使外部函数已经执行完毕。闭包由两部分组成： * 一个函数（通常是内部函数）。 * 该函数被创建时所在的作用域（即外部函数的变量环境） functionouter(){let count =0;// 外部函数的变量functioninner(){ count++;// 内部函数访问外部变量 console.log(count);}return inner;}const counter =outer();counter();// 输出 1counter();// 输出 2 2. 闭包的核心原理 * 作用域链：函数在定义时，会记住自己的词法环境（即外部作用域）。当内部函数访问变量时，会沿着作用域链向上查找。 * 变量持久化：闭包使得外部函数的变量不会被垃圾回收，因为内部函数仍持有对它们的引用 3. 闭包的常见用途 3.1 私有变量封装 通过闭包隐藏内部变量，

By Ne0inhk