紅黑樹-隨手筆記

所謂的樹形結構就是各個元素之間具有分層關係的數據結構，常用一棵倒置的樹來表示邏輯關係。

所謂的根節點就是樹的最頂端的節點，

繼續往下分爲子節點，

當不斷細分直到不再有子節點時爲葉子節點。

紅黑樹性質定義:

1 根結點是黑的

2 每個結點是紅的或是黑的

3 每個葉子結點是黑的

4 如果一個結點是紅的，則它的二個兒子都是黑的

5 每個結點，從該結點到其子孫結點的所有路徑 上的包含相同的數目的黑結點

紅黑樹左右旋轉是爲了追求黑高的平衡

判斷左旋還是右旋，看哪條腿長，就向對向旋轉