平衡二叉樹的調(diào)整(詳解LL、RR、LR、RL)

1、平衡二叉樹的調(diào)整（詳解LL、RR、LR、RL）平衡二叉樹（AVL）的定義：任一結(jié)點(diǎn)的左右子樹高度差的絕對(duì)值小于等于1,絕對(duì)值就是平衡因子任一結(jié)點(diǎn)的左右子樹均為AVL樹。平衡二叉樹也可以是一個(gè)空樹平均查找長度（ASL）（查找效率）（ASL=所有查找次數(shù)X喳找次數(shù)為X的結(jié)點(diǎn)數(shù)相加）/總結(jié)點(diǎn)數(shù)JanApr(JunMayAugi(W)SeptiDec，Oct；iiNov例：値）自然月份序列平衡二叉樹的調(diào)整+2X2+3X3+4X5當(dāng)向一棵AVL樹中插入一個(gè)新的結(jié)點(diǎn)，有可能會(huì)破壞樹的平衡，這時(shí)就需要調(diào)整這棵樹，根據(jù)不同的插入位置，一共有四種調(diào)整方法，在調(diào)整的過程中要注意，一定要滿足二叉搜索樹的性質(zhì)插入位置

2、如何調(diào)整插入結(jié)點(diǎn)在發(fā)現(xiàn)者右子樹的右邊RR調(diào)整，右單旋插入結(jié)點(diǎn)在發(fā)現(xiàn)者左子樹的左邊LL調(diào)整，左單旋插入結(jié)點(diǎn)在發(fā)現(xiàn)者左子樹的右邊LR調(diào)整，左右雙旋插入結(jié)點(diǎn)在發(fā)現(xiàn)者右子樹的左邊RL調(diào)整，右左雙旋注，發(fā)現(xiàn)者是第一個(gè)不滿足這棵樹是平衡二叉樹的結(jié)點(diǎn)，如果有多個(gè)結(jié)點(diǎn)同時(shí)不滿足，就選最靠近下面的那個(gè)結(jié)點(diǎn)作為發(fā)現(xiàn)者，右單旋R調(diào)整）插入結(jié)點(diǎn)在發(fā)現(xiàn)結(jié)點(diǎn)的右子樹的右邊破壞者在發(fā)現(xiàn)結(jié)點(diǎn)右子樹的右邊，所以應(yīng)該對(duì)這棵樹進(jìn)行右單旋（RR單旋），讓樹向左邊轉(zhuǎn)，在旋轉(zhuǎn)過程中讓被破壞者的右子樹作為調(diào)整后的跟結(jié)點(diǎn)在調(diào)整過程中發(fā)現(xiàn)8這個(gè)結(jié)點(diǎn)會(huì)有沖突，那么就按照二叉搜索樹的性質(zhì)將8放在5的右邊，調(diào)整結(jié)果如下插入結(jié)點(diǎn)在發(fā)現(xiàn)結(jié)點(diǎn)左子樹的左邊插入2時(shí)發(fā)現(xiàn)4和5同時(shí)為發(fā)現(xiàn)者，這時(shí)就選擇距離插入結(jié)點(diǎn)較近的點(diǎn)作為發(fā)現(xiàn)者。因?yàn)椴迦虢Y(jié)點(diǎn)在發(fā)現(xiàn)者左子樹的左邊，所以應(yīng)該對(duì)這棵樹，讓樹向右邊轉(zhuǎn)，調(diào)整結(jié)果如下左右雙旋（LR雙旋）插入結(jié)點(diǎn)在發(fā)現(xiàn)結(jié)點(diǎn)左子樹的右邊右左雙旋（RL雙旋）插入結(jié)點(diǎn)在發(fā)現(xiàn)結(jié)點(diǎn)右子樹的左邊發(fā)現(xiàn)這棵平衡二叉樹還不平衡，再以3這棵樹右單旋，結(jié)果如下左右雙旋是先右單旋在左單注意：在雙旋過程中，注意不要讓雙旋的名稱誤解了，名稱僅僅是表示