一、前言

根据王道讲解和网上资料,总结的红黑树相关知识点和考点。

可能考:红黑树的性质、插入、删除(选择题,代码可能不考,略复杂)

二、红黑树

(一)定义

1. 红黑树是实质上是一棵自平衡的二叉查找树,有时形态不一定是平衡二叉树

(左子树结点值 < 根结点值 < 右子树结点值)

2. 引入带颜色的节点也是为了方便在进行插入或删除操作时,如果破坏了二叉查找树的平衡性能通过一系列变换保持平衡。

3. 红黑树的查找、插入、删除的时间复杂度均为O(log_2{n})

(注意:AVL的查找、插入、删除的时间复杂度也是均为O(log_2{n})

4. 适用于频繁插入、删除的场景,实用性更强。(对于平衡二叉树AVL,适用以查找为主,很少插入、删除的场景)

(二)性质(5个)

1. 结点是红色或黑色;

2. 根结点是黑色。

3. 叶子结点(也叫外部结点、NULL结点、失败结点)是黑色。

4. 不存在两个相邻的红结点。(即红结点的父结点和子结点都是黑色的)

5. 从任意结点到可达的叶子结点的每个路径包含相同数目的黑色节点。

(三)结论(2个)

结论1:从根到叶结点的最长路径不大于最短路径的2倍。

结论2:有 n 个内部结点的红黑树的高度  h\leqslant 2log_2{(n+1)}

(四)上口诀来理解红黑树的性质

“口诀1”:左根右,根叶黑,不红红,黑路同。(源自王道)

“口诀2”:(这是博主改编的,纯属为了好记,大家可自行选择)

大小左根右,根叶结点黑(性质2+3),父子不红红(性质4),路路同黑数(性质5)。          

(注意:选择题若考选择哪一棵树是红黑树,就用口诀查证,看是否条条符合)

加深理解:

“黑路同”:一条路走到黑,从任意的结点出发,到失败结点,都具有相同的黑结点数。 

例如:下图中,从结点1出发,到左结点NIL的黑结点个数为2;到右子树的结点NIL的黑结点个数都为3;黑色结点数不相同,所以该树不是红黑树。

 补充:根节点黑高为h的红黑树,内部结点数(关键字)至多有 2^{2h}-1 个。

 

(五)结点定义的代码

// 红黑树的结点定义
struct RBnode{
    int key;    // 关键字的值
    RBnode *parent;   // 父节点的指针
    RBnode *lChild;   // 左孩子的指针
    RBnoce *rChild;   // 右孩子的指针
    int color;  // 结点颜色,如可用 0/1 表示 黑/红。也可用枚举型 enum 表示颜色。
};

(六)红黑树的插入

可以结合下面的例子来理解:

 

注意:红黑树的插入,并不用考虑是否满足“左根右,根叶黑,黑路同”的条件。 只需考虑是否破坏了“不红红”的特点,如果父子都是红结点,则按“红叔”、“黑叔”的划分进行下一步。

 

 

 

 

 

 

 

 可以看到上图,插入23结点后,违背了“不红红”,结点23的父亲的兄弟结点是黑色,即黑叔。而结点23是“LR”型,则先进行左单旋,再右单旋,再将结点23(儿子)和结点25(爷爷)染色(即23红变黑,25黑变红)。(右单旋的结果:是儿子辈分升高再升高。)

 

 

 

 

上图插入结点24后,违背“不红红”,则看其叔为结点22,是红色,“红叔”则“染色+变新”,叔父爷染色,爷变新结点。

如下图,但结点20和23违背了 “不红红”,则看结点23的叔为结点40,是黑色。

黑叔:旋转+染色(LR型:左、右双旋,儿换爷+染色)

 

 

 最后一步插入18时,18是重复的关键字,可以插在第一个18结点的左子树,也可插入到右子树中,下面示范的是插入到第一个18结点的右子树。那么第二个18结点,是RL型,其叔是黑色。

黑叔:旋转+染色(RL型:右、左双旋,儿换爷+染色)

(七)总结:

备注:可参考以下网址来学习

 种树:二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林_看,未来的博客-CSDN博客_哈夫曼树和红黑树

Logo

汇聚原天河团队并行计算工程师、中科院计算所专家以及头部AI名企HPC专家,助力解决“卡脖子”问题

更多推荐