在平衡二叉樹中,插入一個節(jié)點(diǎn)后引起不平衡,設(shè)離插入節(jié)點(diǎn)最近的不平衡點(diǎn)是A，并且已知A的左右孩子的平衡節(jié)點(diǎn)？因?yàn)楣?jié)點(diǎn)a的右子樹的平衡因子為0，所以只能是插在左子樹上的節(jié)點(diǎn)，也就是說節(jié)點(diǎn)a的左子樹被加高了

在平衡二叉樹中,插入一個節(jié)點(diǎn)后引起不平衡,設(shè)離插入節(jié)點(diǎn)最近的不平衡點(diǎn)是A，并且已知A的左右孩子的平衡節(jié)點(diǎn)？

因?yàn)楣?jié)點(diǎn)a的右子樹的平衡因子為0，所以只能是插在左子樹上的節(jié)點(diǎn)，也就是說節(jié)點(diǎn)a的左子樹被加高了。如果平衡因子的定義是左子樹的高度右子樹的高度，則節(jié)點(diǎn)a的平衡因子必須為零如果平衡因子的定義是右子樹的高度左子樹的高度，則a的平衡因子必須為-2，并且需要向右旋轉(zhuǎn)，也就是說，RR型旋轉(zhuǎn)

二叉排序樹也稱為二叉搜索樹。它要么是空樹，要么具有以下屬性：（1）如果其左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值。（2） 如果右子樹不為空，則右子樹中所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值。（3） 左右子樹也是二叉排序樹。

平衡二叉樹是具有以下屬性的空樹或二叉排序樹：（1）左右子樹都是平衡二叉樹；（2） 左右子樹高差的絕對值

如果左右子樹的高差稱為節(jié)點(diǎn)x的平衡因子，則用BF（x）表示。

然后我們從平衡二叉樹的定義知道：BF（x）=x左子樹深度-x右子樹深度