【分享】红黑树的性质与实现思路

村长发表于 2021-12-13 21:57:51

①红黑树(RBT)的Search,Insert,Delete操作的时间复杂度与平衡二叉树(AVL Tree)相同，皆是O(㏒2n)

②平衡二叉树适用以查为主，很少插入/删除的场景
红黑树适用于频繁插入、删除的场景，实用性更强http://cdn.u1.huluxia.com/g4/M03/03/73/rBAAdmGY5WeAJtlYAADcruwpcbM78.jpeg
            ●图一

③红黑树相比普通二叉查找树相比，有以下要求
㈠每个结点或是红色或是黑色的
㈡根节点是黑色的
㈢叶节点（外部结点、NULL结点、失败结点）均是黑色的
      （注：此处的叶节点跟普通二叉树的叶子结点不同，需要注意，红黑树的叶节点只是一个空指针）
㈣不存在两个相邻的红结点（即红结点的父节点和孩子结点均为黑色）
㈤对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同
这五个点简单来说就是：
         左根右，根叶黑，不红红，黑路同http://cdn.u1.huluxia.com/g4/M03/03/73/rBAAdmGY5WiAXEbDAAAg97EAorQ423.png
         ●图二
   如图二，图二不满足㈣，它就不是一个红黑树

④结点的黑高：（即bh参数）指从某结点出发（不含该结点)到达任一空结点的路径上黑结点总数

例如：图一17号的bh值就为2

⑤红黑树的插入：
   先查找，确定插入位置(原理同二叉排序树)，插入新结点
   新结点是根--染为黑色
   新结点非根--染为红色（原因：保证黑路同这一特性）
   若插入新结点后依然满足红黑树定义，则插入结束
   若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义
   如何调整:看新结点叔叔的脸色

   例：图一中27是新结点的话，27的叔叔就是27的父亲（25)的左兄弟（15)

   如果叔叔是黑色:旋转+染色
   ●LL型:右单旋，父换爷+染色
   ●RR型:左单旋，父换爷+染色
   ●LR型:左、右双旋，儿换爷+染色
   ●RL型:右、左双旋，儿换爷+染色
   注：LL,RR,LR,RL为新结点所处的位置，例27号的位置就为RR
   如果叔叔是红色：染色+变新
   ●叔父爷染色，爷变为新结点

叔叔为黑色，且为LL型时交换例子如下：http://cdn.u1.huluxia.com/g4/M02/03/80/rBAAdmGY64yAFch9AADiHJbe0po434.jpg
叔叔为红色，违反不红红时情况如图http://cdn.u1.huluxia.com/g4/M01/03/99/rBAAdmGY9liAIwiEAAHNWoopMs4522.jpg
叔叔为黑色，违反不红红，且为RR时情况如图http://cdn.u1.huluxia.com/g4/M02/03/8F/rBAAdmGY8jaAS7-HAALSgAGcdKg496.jpg
叔叔为黑色，违反不红红，且为LR时情况如图：
RL情况跟LR具体情况相同。http://cdn.u1.huluxia.com/g4/M01/03/99/rBAAdmGY9lmAUitXAADnhVObWRo479.jpg

⑥从根节点到叶节点的最长路径不大于最短路径的2倍

⑦有n个内部节点的红黑树高度h≤2㏒2(n+1)

千面萌萌 发表于 2021-12-14 10:52:48

我是个凑数的。。。

无量科技 发表于 2021-12-14 14:55:42

回个帖子，下班咯~

liqiang24 发表于 2021-12-14 22:05:14

路过帮顶嘿嘿

伴我多久 发表于 2021-12-14 22:24:19

LZ帖子不给力，勉强给回复下吧

天镜盗梦 发表于 2021-12-15 08:34:30

顶起顶起顶起

68079330 发表于 2021-12-15 09:21:19

站位支持

梦影发表于 2021-12-15 11:16:09

看帖要回，回帖才健康，在踩踩，楼主辛苦了！

半度微凉 发表于 2021-12-15 12:49:10

前排顶，很好！

yichong 发表于 2021-12-16 09:09:08

顶起出售广告位

页: [1] 2

村长黑科技's Archiver

【分享】红黑树的性质与实现思路