一毯辅、紅黑樹(shù)
- 性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是黑色摩渺，要么是紅色处铛。
- 性質(zhì)2：根節(jié)點(diǎn)是黑色熟吏。
- 性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。
- 性質(zhì)4：每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色娶吞。
- 性質(zhì)5：任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)垒迂。
- 性質(zhì)5.1：如果一個(gè)結(jié)點(diǎn)存在黑子結(jié)點(diǎn)，那么該結(jié)點(diǎn)肯定有兩個(gè)子結(jié)點(diǎn)
紅黑樹(shù)能自平衡妒蛇，它靠的是什么机断？三種操作：左旋、右旋和變色绣夺。
- 左旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))吏奸，其右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，右子結(jié)點(diǎn)的左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的右子結(jié)點(diǎn)乐导，左子結(jié)點(diǎn)保持不變苦丁。如圖3。
- 右旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))物臂，其左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)旺拉，左子結(jié)點(diǎn)的右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的左子結(jié)點(diǎn)，右子結(jié)點(diǎn)保持不變棵磷。如圖4蛾狗。
- 變色：結(jié)點(diǎn)的顏色由紅變黑或由黑變紅。
1)仪媒、30張圖帶你徹底理解紅黑樹(shù)
2)沉桌、五分鐘搞懂什么是紅黑樹(shù)
3)、紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)剖析
4)算吩、漫畫(huà)算法：什么是紅黑樹(shù)留凭？（適合初學(xué)紅黑樹(shù)小白簡(jiǎn)單易懂）
二、AVL樹(shù)
- 本質(zhì)上還是一棵二叉搜索樹(shù)
- 帶有平衡條件：每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差的絕對(duì)值（平衡因子）最多為1偎巢。
也就是說(shuō)蔼夜，AVL樹(shù)，本質(zhì)上是帶了平衡功能的二叉查找樹(shù)（二叉排序樹(shù)压昼，二叉搜索樹(shù)）求冷。
1)、徹底搞懂AVL樹(shù)
2)窍霞、淺析AVL樹(shù)
三匠题、Trie樹(shù)
Trie，又經(jīng)常叫前綴樹(shù)但金，字典樹(shù)等等韭山。它有很多變種，如后綴樹(shù)，Radix Tree/Trie钱磅，PATRICIA tree巩踏，以及bitwise版本的crit-bit tree。
1)续搀、Trie（前綴樹(shù)/字典樹(shù)）及其應(yīng)用
2)、數(shù)據(jù)結(jié)構(gòu)與算法（十一）Trie字典樹(shù)
3)菠净、Trie樹(shù)
四禁舷、B樹(shù)
B+樹(shù)是B樹(shù)的一種變形形式，B+樹(shù)上的葉子結(jié)點(diǎn)存儲(chǔ)關(guān)鍵字以及相應(yīng)記錄的地址毅往，葉子結(jié)點(diǎn)以上各層作為索引使用牵咙。一棵m階的B+樹(shù)定義如下:
- 每個(gè)結(jié)點(diǎn)至多有m個(gè)子女;
- 除根結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)至少有[m/2]個(gè)子女，根結(jié)點(diǎn)至少有兩個(gè)子女;
- 有k個(gè)子女的結(jié)點(diǎn)必有k個(gè)關(guān)鍵字攀唯。
B+樹(shù)的查找與B樹(shù)不同洁桌，當(dāng)索引部分某個(gè)結(jié)點(diǎn)的關(guān)鍵字與所查的關(guān)鍵字相等時(shí),并不停止查找，應(yīng)繼續(xù)沿著這個(gè)關(guān)鍵字左邊的指針向下侯嘀，一直查到該關(guān)鍵字所在的葉子結(jié)點(diǎn)為止另凌。
1)、b+樹(shù)圖文詳解
2)戒幔、B+樹(shù)的原理
3)吠谢、B樹(shù)、B-樹(shù)诗茎、B+樹(shù)工坊、B*樹(shù)介紹
4)、B樹(shù)和B+樹(shù)原理及在索引中的應(yīng)用
五敢订、各種樹(shù)結(jié)構(gòu)的用途簡(jiǎn)介
1)王污、AVL樹(shù)，紅黑樹(shù)楚午，B樹(shù)昭齐，B+樹(shù)，Trie樹(shù)應(yīng)用場(chǎng)景簡(jiǎn)介
2)醒叁、AVL樹(shù)與紅黑樹(shù)（R-B樹(shù)）的區(qū)別與聯(lián)系
3)司浪、深入理解紅黑樹(shù)與B+樹(shù)應(yīng)用場(chǎng)景
