AVL樹是每個結(jié)點(diǎn)的左子樹和右子樹的高度最多差1的二叉查找樹(空樹的高度定義為-1)。

它能保持二叉樹的高度平衡，盡量降低二叉樹的高度，減少樹的平均搜索長度。

AVL樹的性質(zhì)：

• 左子樹和右子樹的高度差不超過1
• 每個結(jié)點(diǎn)的左子樹和右子樹都是AVL樹
• 每個結(jié)點(diǎn)都有一個平衡因子，任一結(jié)點(diǎn)的平衡因子是-1,0,1。每個結(jié)點(diǎn)的平衡因子等于右子樹高度減去左子樹的高度

AVL樹是在二叉查找樹的基礎(chǔ)上建立的，我們知道二叉查找樹在最壞情況下(每個結(jié)點(diǎn)只有左子樹或右子樹)增刪查的時間復(fù)雜度是O(N)，這種極端的情況下樹是高度不平衡的。

在二叉查找樹的基礎(chǔ)上，如果使左右子樹的高度差不超過1，即達(dá)到高度平衡的狀態(tài)，此時增刪查的時間復(fù)雜度為O(logN)(2為底數(shù))。

為了讓它保持高度平衡，我們引入了平衡因子，每個結(jié)點(diǎn)的平衡因子只可能是-1,0,1中的一個。

每次插入/刪除一個結(jié)點(diǎn)，我們都需要向上更新一下新增結(jié)點(diǎn)/刪除結(jié)點(diǎn)的祖先的平衡因子。一旦發(fā)現(xiàn)某個祖先的平衡因子變?yōu)?或者-2，我們就需要通過旋轉(zhuǎn)來使這棵樹保持AVL樹的特性。

轉(zhuǎn)載于:https://www.cnblogs.com/i-hard-working/p/10749998.html

總結(jié)

以上是生活随笔為你收集整理的AVL树---平衡的二叉查找树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。