紅黑樹Java語言實作
- 紅黑樹的用途
- 紅黑樹的定義
- 紅黑樹高效的原因
- 紅黑樹的插入
- 1. 最簡單的情況——插入根節點
- 2. 也很簡單的情況——新節點的父親是黑色的
- 3. 新節點的父親是紅色的
- 3.1 新節點的叔叔是紅色的
- 3.2 新節點的叔叔是黑色的
- 3.2.1 LL形式
- 3.2.2 LR形式
- 3.2.3 RR形式
- 3.2.4 RL形式
- 紅黑樹 vs AVL樹
- 紅黑樹Java實作
紅黑樹的用途
用于快速查找元素，或者說快速根據關鍵字查詢值，和散串列不同，散串列是利用散列函式建立單向映射實作快速查找，紅黑樹屬于二叉查找樹，它使得樹的深度保持在O[ log(n) ]，查找次數不多于最大深度，從而實作快速查找，
紅黑樹的定義
- 樹中有兩種顏色的節點，紅色和黑色（顧名思義）
- 所有終端節點為黑色，終端節點（又稱葉子節點）就是null節點
- 根節點是黑色
- 不能有兩個連續的紅色節點（即每個紅色節點都有2個黑色節點）
- 從根節點到終端節點路徑上的黑色節點個數相同
紅黑樹高效的原因
上述4、5最重要，找到終端可謂是最糟糕的情況了，即便的最壞的情況下，黑色節點都相同，那么路徑最長的情況下是紅黑相間的情況下，最短情況是全部是黑色，顯然，到終端最長路徑不超過最短路徑的2倍，因此能夠保證樹的深度是O[ log(n) ]的（本人未證明），從而保證了效率，
紅黑樹的插入
首先要宣告一下，除了插入根節點之外，新插入的節點初始的顏色都是紅色的（后來可能會調整顏色）
1. 最簡單的情況——插入根節點
只需保證根節點為黑色，非常簡單，，，
2. 也很簡單的情況——新節點的父親是黑色的
沒有任何負面影響，因為即保證了紅色節點不連續，又不影響根節點到終端的黑色節點個數，原來是（黑）父親+（黑）孩子，現在是（黑）父親+（紅）新節點+（黑色）新節點的兒子
3. 新節點的父親是紅色的
這時候就出現了紅色節點連續的情況了，需要調整
3.1 新節點的叔叔是紅色的
把爺爺變成黑色，父親和叔叔變成紅色，首先在從太爺爺到終端的黑色節點個數不變，其次這個區域沒有紅黑相間的情況，但是爺爺和太爺爺之間可能會出現2個連續紅色的情況，把爺爺設為新節點（current），繼續運行插入規律（上調），
3.2 新節點的叔叔是黑色的
3.2.1 LL形式
這時候新的節點和父親出現了紅色相鄰的情況，這時候對爺爺進行右單旋，并且爺爺和父親交換顏色，注意的是可能會丟失父親的右孩子，它本來就是介于父親和爺爺的值，正好彌補了爺爺的左孩子，這樣依舊保證了紅黑樹性質，因為父親是黑色的，不需要上調，
3.2.2 LR形式
- 先說一種一步到位的方法，就是讓父親和爺爺成為新節點的左兒子和右兒子，同時新節點的左子樹接到父親的右子樹，新節點的右子樹接到爺爺的左子樹，新節點和爺爺顏色交換，新節點設為黑色，
- 顯然結果不存在連續的紅色節點，根節點到終端的黑色節點數也保持不變，
- 新節點的左子樹本身大于父親小于新節點，新節點的右子樹小于爺爺大于新節點，旋轉后依然保持二叉搜索樹的性質
- 再說一種兩步到位的方法，先對父親左單旋，注意新節點的左子樹接到父親的右子樹上，否則會丟失節點！這樣就轉換成了3.2.1 LL形式（對爺爺右單旋），從編程的角度來說還是一步到位更有效率！
3.2.3 RR形式
是LL的鏡像對稱模式，一切取反即可，不再累述
3.2.4 RL形式
是LR的鏡像對稱模式，一切取反即可，不再累述
紅黑樹 vs AVL樹
- 總結來說，AVL樹插入效率小于紅黑樹，AVL查詢效率大于紅黑樹
- AVL可以保證左右子樹高度差絕對值不大于1并且是一顆二叉搜索樹
- 插入時，AVL樹平衡性強，更容易引起不平衡觸發耗時的旋轉操作，紅黑樹只有在父親是紅色時才能觸發旋轉操作，“容納\忍耐”能力強一些，因此損耗更低，
- 查詢時候，AVL可以保證左右子樹高度差絕對值不大于1，紅黑樹平衡性更差，所以深度略大，查詢效率略低一些，
- 平均來說，紅黑樹性能>AVL性能
- AVL樹介紹，參考我以前的博客：AVL樹理解、證明
紅黑樹Java實作
參考我的實作：https://github.com/ghostorsoul/red_black_tree
代碼決議未完待續，，，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/81025.html
標籤：其他
上一篇：3D CV 論文調研