【文章內(nèi)容簡介】 方法 (a)圖 A的左子樹的左子樹上插入 15后，導(dǎo)致失衡，如 (b)圖。為恢復(fù)平衡并保證二叉排序樹的特性，可將 A改為 B的右子， B原來的右子改為 A的左子，圖 169。,即以 B為軸，對 A做一次順時針旋轉(zhuǎn)。 40 25 60 20 30 1 0 0 0 0 A B (a)平衡二叉排序樹 40 25 60 20 30 2 0 1 0 1 A B 15 0 (b)插入 15后失去平衡 25 20 40 15 30 0 0 1 0 B A 60 0 0 169。調(diào)整后的二叉排序樹 (a)圖 A的右子樹 B的右子樹上插入 70后，導(dǎo)致失衡，如 (b)圖。為恢復(fù)平衡并保證二叉排序樹的特性，可將 A改為 B的左子， B原來的左子改為 A的右子，圖 (c),即以 B為軸，對 A做一次逆時針旋轉(zhuǎn)。 (a)平衡二叉排序樹 25 20 40 30 60 1 0 0 0 0 A B 25 20 40 30 60 2 1 0 1 0 A B 70 0 (b)插入 70后失去平衡 40 25 60 30 70 0 1 0 0 0 A B 20 0 169。調(diào)整后的二叉排序樹 (a)圖 A的左子樹 B的右子樹上插入 45后，導(dǎo)致失衡，如 (b)圖。為恢復(fù)平衡并保證二叉排序樹的特性，可首先將 B改為 C的左子，而 C原來的左子改為 B的右子；然后將 A改為 C的右子， C原來的右子改為 A的左子，即對 B做了一次逆時針旋轉(zhuǎn)，對 A做一次順時針旋轉(zhuǎn)。 1 80 10 90 40 20 30 60 50 70 85 95 A 0 0 0 0 C 0 0 0 0 0 0 B (a)一棵平衡二叉排序樹 80 10 90 40 20 30 60 50 70 85 95 A 0 0 0 1 C 0 1 0 0 0 1 B 45 0 2 (b)插入 45后失去平衡 0 60 10 80 40 20 30 50 45 70 90 C 1 0 0 1 0 0 0 0 0 B A 85 95 0 0 169。調(diào)整后的二叉排序樹 (a)圖 A的右子樹 B的左子樹上插入 55后，導(dǎo)致失衡，如 (b)圖。為恢復(fù)平衡并保證二叉排序樹的特性，可首先將 B改為 C的右子，而 C原來的右子改為 B的左子；然后將 A改為 C的左子， C原來的左子改為 A的右子，即對 B做了一次順時針旋轉(zhuǎn)，對 A做一次逆時針旋轉(zhuǎn)。 (a)一棵平衡二叉排序樹 1 40 A 0 50 80 60 70 90 85 95 0 C 0 0 0 0 0 B 20 10 30 0 0 0 0 0 2 40 A 1 50 80 60 70 90 85 95 0 C 0 0 1 1 B 20 10 30 0 0 55 0 0 (b)插入 55后失去平衡 0 40 C 1 80 90 85 95 0 0 B 20 604020 0 70 50 55 10 30 1 0 0 0 0 0 A 169。調(diào)整后的二叉排序樹 綜上所述，失衡類型及相應(yīng)的調(diào)整方法可歸納為以下四種： 1） LL型（以 B軸，對 A做了一次順時針旋轉(zhuǎn)） A B BL BR S AR 2 1 (a)插入新結(jié)點 S后失去平衡 B A BL BR S AR 0 0 (b)調(diào)整后恢復(fù)平衡 在一般二叉排序樹的結(jié)點中增加一個存放平衡因子的域 bf。 LL型失衡的特點是： Abf=2， Bbf=1。 相應(yīng)調(diào)整操作可用如下語句完成： B=ALchild； ALchild=brchild； Brchild=A； Abf=0； Bbf=0； 1） LL型 最后 ， 將調(diào)整后二叉樹的根結(jié)點 B―接到 ” 原 A處 。令 A原來的父指針為 FA， 如果 FA非空 ， 則用 B代替 A做 FA的左子或右子；否則原來 A就是根結(jié)點 ，此時應(yīng)令根指針 t指向 B： if (FA==NULL) t=B。 else if (A==FALchild) FALchild=B。 else FArchild=B； 2） LR型（對 B做了一次逆時針旋轉(zhuǎn)，對 A做了一次順時針旋轉(zhuǎn)） A B CR CL S AR 2 1 (a)插入新結(jié)點 S后失去平衡 BL C 1 C B CR CL S AR 0 0 (b)調(diào)整后恢復(fù)平衡 BL A 1 LR型失衡的特點是： Abf=2， Bbf=1。 相應(yīng)調(diào)整操作可用如下語句完成： B=Alchild； C=BRchild； Brchild=Clchild； Alchild=Crchild； Clchild=B； Crchild=A； 然后針對上述三種不同情況 ， 修改 A、 B、 C的平衡因子： if (Skey Ckey) /* 在 CL下插入 S */ { Abf=1； Bbf=0 ； Cbf=0； } if (Skey Ckey) /* 在 CR下插入 S */ { Abf=0； Bbf=1 ； Cbf=0； } if (Skey ==Ckey) /* C本身就是插入的新結(jié)點 S */ { Abf=0； Bbf=0 ； } 最后 ， 將調(diào)整后的二叉樹的根結(jié)點 C―接到 ” 原 A處 。令 A原來的父指針為 FA， 如果 FA非空 ， 則用 C代替A做 FA的左子或右子；否則 ， 原來 A就是根結(jié)點 ，此時應(yīng)令根指針 t指向 C： if (FA==NULL) t=C。 else if (A==FAlchild) FAlchild=C。 else FArchild=C； 3） RR型（以 B為軸，對 A做了一次逆時針旋轉(zhuǎn)） (a)插入新結(jié)點 S后失去平衡 A B BL BR S AL 2 1 1 (b)調(diào)整后恢復(fù)平衡 0 B A BL BR S AL 0 RR型失衡的特點是： Abf=2， Bbf=1。 相應(yīng)調(diào)整操作可用如下語句完成： B=Archild； Archild=Blchild； Blchild=A； Abf=0； Bbf=0； 最后 ， 將調(diào)整后二叉樹的根結(jié)點 B―接到 ” 原 A處 。令 A原來的父指針為 FA， 如果 FA非空 ， 則用 B代替A做 FA的左子或右子；否則 ， 原來 A就是根結(jié)點 ，此時應(yīng)令根指針 t指向 B： if (FA==NULL) t=B。 else if (A==FALchild) FALchild=B。 else FArchild=B； 4） RL型（ 對 B做了一次順時針旋轉(zhuǎn)，對 A做了一次逆時針旋轉(zhuǎn) ） A B C AL CL CR BR S 2 1 1 (a)插入新結(jié)點 S后失去平衡 B A C BR CL CR AL S 0 0 1 (b)調(diào)整過后恢復(fù)平衡 RL型失衡的特點是： Abf=2， Bbf=1。 相應(yīng)調(diào)整操作可用如下語句完成： B=Archild； C=Blchild； Blchild=Crchild； Archild=Clchild； Clchild=A； Crchild=B； 然后針對上述三種不同情況 ， 修改 A、 B、 C的平衡因子： if (Skey Ckey) /* 在 CL下插入 S */ { Abf=0； Bbf=1 ； Cbf=0； } if (Skey Ckey) /* 在 CR下插入 S */ { Abf=1； Bbf=0 ； Cbf=0； } if (Skey ==Ckey) /* C本身就是插入的新結(jié)點 S */ { Abf=0； Bbf=0 ； } 最后 ， 將調(diào)整后的二叉樹的根結(jié)點 C―接到 ” 原 A處 。令 A原來的父指針為 FA， 如果 FA非空 ， 則用 C代替 A做 FA的左子或右子；否則 ， 原來 A就是根結(jié)點 ， 此時應(yīng)令根指針 t指向 C： if (FA==NULL) t=C。 else if (A==FAlchild) FAlchild=C。 else FArchild=C； 綜上所述 ， 在一個平衡二叉排序樹上插入一個新結(jié)點 S時 ， 主要包括以下三步： （ 1） 查找應(yīng)插位置 ， 同時記錄離插入位置最近的可能失衡結(jié)點 A（ A的平衡因子不等于 0） 。 （ 2） 插入新結(jié)點 S， 并修改從 A到 S路徑上各結(jié)點的平衡因子 。 （ 3）根據(jù) A、 B的平衡因子，判斷是否失衡以及失衡類型，并做相應(yīng)處理。 平衡二叉排序樹的插入算法 其中 AVLTree為平衡二叉排序樹類型， AVLTNode為平衡二叉排序樹結(jié)點類型 void ins_AVLtree（ AVLTree *avlt , KeyType k） /*在平衡二叉樹中插入元素 k， 使之成為一棵新的二叉排序樹 */ { s=(AVLTree)malloc(sizeof(AVLTNode))。 skey=k。 slchild=srchild=NULL。 Sbf=0。 if (*avlt==NULL) *avlt=S。 else { /* 首先查找 S的插入位置 FP， 同時記錄距 S的插入位置最近且 平衡因子不等于 0（ 等于 1或 1） 的結(jié)點 a， a為可能的失衡結(jié)點 */ A=*avlt； fa=NULL。 p=*avlt； fp=NULL while (p!=NULL) { if (pbf!=0) {a=p。 fa=fp}。 fp=p。 if (K pkey) p=plchild。 else p=prchild。 } /* 插入 S*