一、樹

1-1、樹的基本概念

1、樹的節點

2、二叉樹

3、樹的高度

1-2、二叉查找樹

普通二叉樹沒有規律，不方便查找，沒什么作用。

1、基本概念

2、添加節點

此時，該方式添加形成的二叉查找樹，根節點就是第一個節點。

3、查找節點

4、二叉樹的遍歷

• 前序遍歷
• 中序遍歷
• 后序遍歷
• 層序遍歷?

①前序遍歷

②中序遍歷（最常用）

獲取到的數據是從小到大的！所以，這種遍歷方式是最常見的！

③后序遍歷

④層序遍歷

5、二叉查找樹的弊端?

此時，查詢效率太低了！

一棵樹想要提高查詢效率，要樹的左、右高度差不多！——平衡二叉樹。

1-3、平衡二叉樹

1、平衡二叉樹的旋轉機制

目的：在構建二叉樹的時候，保持平衡。?

①、左旋

【示例1】：

左旋步驟1：（簡單）

【示例2】：

左旋步驟2：（復雜）

②、右旋

【示例1】：

右旋步驟1：（簡單）

【示例2】：

右旋步驟2：（復雜）

?

?

③、平衡二叉樹需要旋轉的四種情況

1、左左：一次右旋

?

?

2、左右：先局部左旋，再整體右旋

步驟一：局部左旋

步驟二：整體右旋

3、右右：一次左旋

4、右左：先局部右旋，再整體左旋

步驟一：局部右旋

步驟二：整體左旋

小結：

?1-4、小結-樹的演變

1-5、紅黑樹

?1、紅黑規則

2、構建紅黑樹

添加節點時，默認節點是紅色的，因為效率高！（按照紅黑規則調整的次數少！）

旋轉的時候，先把葉子nil結點去掉，直接轉，轉完再把nil節點加上即可！

【示例】：

?【步驟一】：添加第一個節點

?【步驟二】：添加第二個節點

非根，父節點是黑色，不做調整。

?【步驟三】：添加第三個節點

?【步驟四】：添加第四個節點

非根，父紅，叔叔紅色：

?

?【步驟五】：添加第五個節點

非根，父節點是黑色，不做調整。

?

?【步驟六】：添加第六個節點

?

3、紅黑樹的性能

紅黑樹的增、刪、改、查，性能都比較好！

在構建紅黑樹的過程中，調整次數多的是改變顏色（只是改變節點里面存儲顏色的變量的值），旋轉的操作（旋轉操作比較耗時！），對比平衡二叉樹，少太多了！