【喵的算法課】紅黑樹(shù) 插入【11期】
2023-07-11 10:22 作者:Saberlilya | 我要投稿
一、紅黑樹(shù)概念
- 紅黑樹(shù)定義
?
00:16
?
為什么引入平衡樹(shù)或紅黑樹(shù)
?
01:08
?
2.紅黑樹(shù)前身 234樹(shù)
?
01:30
?
234樹(shù)只能有2結(jié)點(diǎn)，3結(jié)點(diǎn)，4結(jié)點(diǎn)3類(lèi)
234樹(shù)插入操作
?
02:35
?
3.紅黑樹(shù)性質(zhì)
?
04:45
?
注意紅黑樹(shù)底層有空的葉結(jié)點(diǎn)
4.紅黑樹(shù)和234樹(shù)等價(jià)
?
06:34
?
二、紅黑樹(shù)插入操作
?
07:18
?1.
?
07:33
?
路徑若是黑色結(jié)點(diǎn)會(huì)很麻煩
2.
?
07:54
?
情況1
?
父結(jié)點(diǎn)黑色4種
08:06
?
情況2
?
其他8種情況。(之后對(duì)圖嘗試操作
08:10
?
3.操作
①
?
09:23
?LL:染色+左旋 RR:染色+右旋
②
?
10:36
?RL:變色，父結(jié)點(diǎn)右旋，祖父結(jié)點(diǎn)左旋
LR:變色，父結(jié)點(diǎn)左旋，祖父節(jié)點(diǎn)右旋
變色注意往想要方向?qū)?yīng)。
③
?
13:23
?
最好選擇插入結(jié)點(diǎn)的祖父結(jié)點(diǎn)，也就是黑色結(jié)點(diǎn)進(jìn)行上溢。
實(shí)際在234樹(shù)提到上一層，在紅黑樹(shù)中無(wú)變化。
1.父結(jié)點(diǎn)，叔父結(jié)點(diǎn)變黑
2.祖父結(jié)點(diǎn)變紅
3.上溢進(jìn)行遞歸
?
15:49
?
標(biāo)簽：
