一，平衡二叉樹插入失衡情況及解決方案

由于各種的插入導致的不平衡，每次調(diào)整都是最小不平衡子樹。
LL：由于在結(jié)點A的 左孩子的左子樹 插入結(jié)點導致失衡。

??右單旋：①將A的 左孩子B 向右上旋轉(zhuǎn) 代替A成為根節(jié)點
??????②將A結(jié)點 向右下旋轉(zhuǎn) 成為B的 右子樹 的根節(jié)點
??????③B的原來 右子樹 成為A的 左子樹。

RR：由于在結(jié)點A的 右孩子的右子樹 插入結(jié)點導致失衡。

??左單旋：①將A的 右孩子B 向左上旋轉(zhuǎn) 代替A成為根節(jié)點
??????②將A結(jié)點 左下旋轉(zhuǎn) 成為B的 左子樹 的根節(jié)點
??????③B的原來 左子樹 成為A的 右子樹。

LR：由于在結(jié)點A的 左孩子的右子樹 插入結(jié)點導致失衡。

先左旋后右旋：先讓A的左孩子B的右子樹的根節(jié)點C左上旋提升到B位置，在讓C右上旋提升到A位置。

RL：由于在結(jié)點A的 右孩子的左子樹 插入結(jié)點導致失衡。

先右旋后左旋：先讓A的右孩子B的左子樹的根節(jié)點C右上旋提升到B位置，在讓C左上旋提升到A位置。

二，平衡二叉樹刪除步驟

①刪除結(jié)點(方法同二叉排序樹)
??1.如果刪除的是葉子結(jié)點，直接刪除。
??2.如果刪除的結(jié)點只有一顆子樹，則用子樹頂替刪除位置。
??3.如果刪除的結(jié)點有兩顆子樹，則直接前驅(qū)(或直接后繼)結(jié)點頂替，并轉(zhuǎn)為對直接前驅(qū)（或直接后繼）的刪除。
②一路向北(上)找到最小不平衡子樹，找不到就結(jié)束。
③找到最小不平衡子樹下，“個頭最大”的兒子和孫子。
④根據(jù)孫子位置，調(diào)整平衡(孫子相對于爺位置LL,RR,LR,RL)。
??1.如果孫子在LL，兒子右單旋。
??2.如果孫子在RR，兒子左單旋。
??3.如果孫子在LR，孫子先左旋后右旋。
??4.如果孫子在RL，孫子先右旋后左旋。
⑤如果不平衡向上傳導，繼續(xù)②。

三，平衡二叉樹刪除實例

1.RR型

1.RL型

1.平衡向上傳導