二叉排序樹(shù)的定義,平衡二叉樹(shù)和某接點(diǎn)的平衡因子的定義

某個(gè)節(jié)點(diǎn)的平衡因子就是那個(gè)節(jié)點(diǎn)左子樹(shù)的高度減去右子樹(shù)的高度，你可以對(duì)照左邊的圖檢查一下是不是這樣
比如a節(jié)點(diǎn)的因子就是它左邊的子樹(shù)的高度，這里是3，減去右子樹(shù)的高度，這里是2，所以=1
對(duì)于b節(jié)點(diǎn)，左子樹(shù)高度為1，右邊為2，所以1-2=-1就是b節(jié)點(diǎn)的平衡因子

　　二叉排序樹(shù)也稱(chēng)二叉查找樹(shù)。它或者是一棵空樹(shù)；或者有性質(zhì)：（1）若其左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。（2）若其右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。（3）左右子樹(shù)也為二叉排序樹(shù)。
　　平衡二叉樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉排序樹(shù)：(1)左、右子樹(shù)都是平衡二叉樹(shù)；(2)左、右子樹(shù)高度差的絕對(duì)值<=1。
　　若把左子樹(shù)與右子樹(shù)高度之差稱(chēng)為結(jié)點(diǎn)x的平衡因子(balance factor)，用bf(x)表示。
　　則由平衡二叉樹(shù)定義知:Bf(x)=x左子樹(shù)深度-x右子樹(shù)深度