數據結構 9.13 平衡二叉（查找）樹

　　希賽教育計算機專業考研專業課輔導招生

　　希賽教育計算機專業考研專業課輔導視頻

　　希賽教育計算機考研專業課在線測試系統

　　稱二叉樹為平衡指的是它或是空樹或具有下列特性其左子樹和右子樹都是平衡二叉樹且左右子樹深度之差的絕對值不大於例如右側上的兩棵二叉樹為平衡樹右側下的兩棵二叉樹不是平衡樹樹中結點內的數值稱作結點的平衡因子定義為左子樹的深度減去右子樹的深度換句話說平衡樹上所有結點的平衡因子的絕對值均不大於可以證明含有n個結點的平衡二叉樹的深度為因此在平衡二叉樹上進行查找時和關鍵字進行比較的次數是和logn等數量級的

　　平衡處理的原則是保證二叉查找樹始終處於平衡狀態從空樹起（空樹是平衡樹）每插入一個關鍵字都需要檢查二叉查找樹是否失去平衡如因插入新的結點引起不平衡則需對它進行平衡旋轉處理如何進行平衡旋轉處理在教材和其它參考書中都有詳細闡述在此僅以一個例子作簡單介紹

From:http://tw.wingwit.com/Article/program/sjjg/201311/23951.html