平衡因子是指二叉樹中某個節點的左子樹高度與右子樹高度之差。具體計算方法如下:
定義:平衡因子 = 左子樹高度 - 右子樹高度。
計算示例:
對於節點A,如果左子樹高度爲3,右子樹高度爲2,則平衡因子 = 3 - 2 = 1。
對於節點B,如果左子樹高度爲1,右子樹高度爲2,則平衡因子 = 1 - 2 = -1。
平衡狀態:
當平衡因子爲0、1、-1時,樹處於平衡狀態。
當平衡因子爲2或-2時,表示樹失衡,需要通過旋轉等操作來恢復平衡。
特殊情況:在AVL樹中,平衡因子的範圍被限定爲-1、1、0,以確保樹的平衡。這是因爲在AVL樹中,任何節點的左右子樹的高度之差絕對值不超過1。
通過計算平衡因子,可以幫助判斷二叉樹的平衡狀態,並在必要時進行平衡調整,以維持樹的平衡性。