平衡二叉排序樹ppt課件(編輯修改稿)
2025-05-26 00:24 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 BLS CR ARCLA不平衡二叉排序樹的調(diào)整 ——LR 型不平衡二叉排序樹的調(diào)整 ——LR 型806040 905020 957085301045605040 804520 9085703010 95ABCCABAlchild=crchild Brchild=clchildcrchild=Aclchild=B最低層失衡結(jié)點(diǎn)為 A， 在結(jié)點(diǎn) A的右子樹的右子樹上插入新結(jié)點(diǎn) S后，導(dǎo)致失衡，由 A和 B的平衡因子可知， BL、 BR和 AL深度相同，為恢復(fù)平衡并保持二叉排序樹的特性，可將 A改為 B的左子， B原來(lái)的 左子 BL改為 A的右子，這相當(dāng)于 以 B為軸，對(duì) A做了一次逆時(shí)針旋轉(zhuǎn)。ASBBL BRARBAAL SBLBR不平衡二叉排序樹的調(diào)整 ——RR 型不平衡二叉排序樹的調(diào)整 ——RR 型302520 4060AB703025204060AB70Archild=Blchild Blchild=A最低層失衡結(jié)點(diǎn)為 A， 在結(jié)點(diǎn) A的右子樹的左子樹上插入新結(jié)點(diǎn) S后，導(dǎo)致失衡，假設(shè)在 CR下插入 S，由 A、 B、 C的平衡因子可知， CL與 CR深度相同， AL與 BR深度相同， 且 AL、 BR的深度比 CL、 CR的深度大 1；為恢復(fù)平衡并保持二叉排序樹的特性，可將 B改為 C的右子，而 C原來(lái)的右子 CR改為 B的左子，然后將 A改為 C的左子， C原來(lái)的左子 CL改為 A的右子；這相當(dāng)于以 B為軸，對(duì) A做了一次順時(shí)針旋轉(zhuǎn)。ABALSCRBRCLCCAALSCR BRCLB不平衡二叉排序樹的調(diào)整 ——RL 型不平衡二叉排序樹的調(diào)整 ——RL 型8560408050209070 953010ABC55854060805020 9070953010 55Archild=clchild Blchild=crchildclchild=Acrchild=B542 631 87思考：此樹是否為平衡
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1