AVL樹本質(zhì)上還是一棵二叉搜索樹（因此讀者可以看到我后面的代碼是繼承自二叉搜索樹的），它的特點是：

本身首先是一棵二叉搜索樹。

帶有平衡條件：每個結(jié)點的左右子樹的高度之差的絕對值（平衡因子）最多為1。

AVL樹的查找平均時間復雜度要比二叉搜索樹低——它是O(logN)。

?

旋轉(zhuǎn)操作：

AVL樹是一顆平衡樹，其左右子樹的高度差不會超過一層。爲了保持這一性質(zhì)，採用旋轉(zhuǎn)節(jié)點的方式來降低高度。

如下圖，紅色表示新插入的節(jié)點，一共4種情況：

• 左左：節(jié)點1插入到左子樹的左節(jié)點，導致節(jié)點5不平衡。

?

實際上我們只需要關心節(jié)點1、3、5，根據(jù)二叉搜索樹的性質(zhì)（左 < 中 < 右），所以祇有節(jié)點3才可以作為父節(jié)點，於是將節(jié)點5繞節(jié)點3進行一次左旋，達到平衡。

?

• 右右：和左左類似，可以通過一次右旋來實現(xiàn)平衡，如下圖：

?

?

• 左右：這種情況光旋轉(zhuǎn)失衡的節(jié)點5是不夠的，因爲節(jié)點3是無法成爲父節(jié)點的，祇有節(jié)點4才有可能。

?

所以先把節(jié)點3右旋以使節(jié)點4居中，再將節(jié)點5左旋，共兩次旋轉(zhuǎn)實現(xiàn)平衡。

?

• 右左：和左右的情況類似，也是兩次，先左旋后右旋。

?

圖片出處：http://www.th7.cn/Program/net/201306/140050.shtml

?

代碼尚在醞釀中。

轉(zhuǎn)載于:https://www.cnblogs.com/IT-nerd/p/3477696.html

總結(jié)

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

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