撰寫不易，轉載注明出處：https://www.cnblogs.com/lmh15054109/p/14239386.html
在學習紅黑樹之前，需要先理解二叉查找樹（Binary Search Tree），
一、二叉查找樹
二叉查找樹（BST）特性
1. 左子樹上所有節點的值均小于或等于它的根節點的值，
2. 右子樹上所有節點的值均大于或等于他的根節點的值，
3. 左、右子樹也分別為二叉排序樹，
（1）查找
查找一下節點值為10 的節點，
1. 根節點為9,10>9，查看右孩子13，
2. 10<13 ,查看左孩子11，
3. 10 < 11 ，查看左孩子 10，剛好為需要查找的物件，
二叉查找樹利用的正是二分查找的思想，查找所需的最大次數等同于二叉查找樹的高度，
（2）插入
插入節點時，也使用類似的方法，通過一層一層的比較大小，找到新節點適合的位置，然后執行插入，
插入新節點的時候暴露出二叉查找樹的缺陷，
假設現在我們需要依照BST的特性，向初始只有三個節點，根節點為9，左孩子為8，右孩子為12的BST中依次插入7,6,5,4,3，其結果會入上圖所示，
這樣的形態雖然也符合二叉查找樹的特性，但是查詢的性能大打折扣，幾乎變成線性的了，
紅黑樹就較好的解決了二叉查找樹多次插入新節點而導致的不平衡，
二、紅黑樹
（1）紅黑樹的特性
紅黑樹（Red Black Tree）是一種自平衡的二叉查找樹，出了符合BST的基本特性外，還具有其他特性，
規則：
- 節點是紅色或黑色的，
- 根節點是黑色的，
- 每個葉子節點都是黑色的
空節點（NIL節點），- 每個紅色節點的兩個子節點都是黑色的，（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點，）
- 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點，
以上特性保證了紅黑樹的自平衡，紅黑樹從根到葉子的最長路徑不會超過最短路徑的兩倍，
當插入或洗掉節點時，紅黑樹的規則有可能被打破，
例如：向原紅黑樹插入值為21的新節點：
其父節點是紅色的，違反了規則4（每個紅色節點的兩個子節點都是黑色），我們需要進行必要的調整，使之重新符合紅黑樹的規則，
（2）紅黑樹的調整方式
紅黑樹的調整方式有兩種，分別是：變色,旋轉，其中旋轉細分為：左旋轉，右旋轉，
變色：為了符合紅黑樹的規則，嘗試把紅色節點轉變為黑色，或把黑色變為紅色，
（1）由于21,22都為紅色節點，違反了規則4（每個葉子節點到根節點的所有路徑上不能有連續的紅色節點），所以將22變成黑色，
（2）此時從25到其葉子節點違反了規則5，需要將25從黑色變成紅色，
（3）此時，25、27形成了兩個連續的紅色節點，需要將27變為黑色，
左旋轉：逆時針旋轉紅黑樹的兩個節點，使得父節點被自己的
右孩子取代，而自己成為左孩子，
右旋轉：順時針旋轉紅黑樹的兩個節點，使得父節點被自己的
左孩子取代，而自己成為右孩子，
在上述插入節點21的例子中，經過變色形成了17,25兩個連續紅色節點的結果，如果將17變為黑色，將打破規則4，由于根節點能是黑色，所以根節點13不可能變成紅色，
此時將13作為X，17作為Y進行左旋處理，
結果：
根據規則的2（根節點必須是黑色）進行變色，17變為黑色，根據規則5（從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點），13變為紅色，8變為黑色，1,11變為紅色，6變為黑色，
此時，紅黑樹調整貌似已經調整到位，其實不然，根據規則5可知從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點，從17到6到NIL節點的黑色節點個數是4，而其他路徑的黑色個數是3，所以還需要繼續處理，
我們將13看為X，8看為Y，進行右旋轉操作，
結果：
然后進行變色，最終：
插入節點21到紅黑樹中的操作就完成，其中的步驟比較復雜，具體步驟為：
變色 ——>左旋轉——>變色 ——>右旋轉——>變色
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/245504.html
標籤：Java