紅黑樹與AVL平衡二叉樹

紅黑樹:

特性

1. 根節點始終為黑節點
2. 從根節點開始到葉子節點所經過的黑節點數始終相同
3. 新節點為紅色，空節點為黑色
4. 父節點與父節點之間不能同時為紅色

平衡原則：

旋轉原則：

    顔色變化：

1. 紅紅旋轉顔色不變。
2. 紅黑旋轉，旋轉後的父節點變黑色，子節點變紅色。
3. 黑紅旋轉，旋轉後的父節點變紅色，子節點變黑色。

    結構變化：

1. 左旋轉：3層節點間旋轉，第二層節點變主節點，第一層節點成第二層節點的左節點，第三層的右節點為第二層節點的右節點，當第三層有左節點時，會成為第一層節點的右節點。如圖1
2. 右旋轉：3層節點間旋轉，第二層節點變主節點，第一層節點成第二層節點的右節點，第三層的左節點為第二層節點的左節點，當第三層有右節點時，會成為第一層節點的左節點。如圖2

圖1

圖2

插入節點時：

插入節點顔色變化，插入節點為紅節點，父節點如果為紅色，則判斷父節點的兄弟節點是否為紅色，如果父節點的兄弟節點為紅色，在判斷父節點的父節點是否黑色，是則父節點與父節點的兄弟節點與父父節點互換顔色，如果父節點的兄弟節點為黑色，則父節點與父父節點旋轉。在判斷從互換後父父父節點開始以上操作。直到為父節點為黑色。

1. 父節點沒有兄弟節點，需要旋轉一至兩次使之平衡

删除節點時：

1. 如果有子節點的話，首先從左子節點尋找是否存在，存在的話，在判斷是左子節點是否存在子節點，如果存在擷取最右邊的子節位置指針做為删除節點的指針(删除節點并沒有删除)，并删除最右邊節點，如果左子節點不存在子節點的話，直接指向左子節點的指針，并删除左子節點，如果左子節不存在，則父節點指向右節點，删除目前節點。

删除節點，顔色變換：

1. 如果删除的節點有黑色兄弟節點并有2個黑侄子節點(葉子節點下預設有2個空節點)，父節點與子節點顔色互換
2. 如果删除的節點為紅色，則不需要操作
3. 如果删除的節點目前節點，父節點指向右節點的時候，子節點變黑色

AVL平衡二叉樹

實作完全平衡的二叉樹

平衡原則：

平衡原則：

結構變化：與紅黑樹類似

插入節點時：每次插入節點時都會向上每個統計每個節點的位置做到左節點的位置與右節點的位置差不大于1實作完全平衡

删除操作與紅黑樹類似，AVL樹删除後，會與每個節點做一次位置統計。

總結：

紅黑樹，查詢效率相對較低，添、删效率高于AVL樹。