AVL Trees (Balanced binary search trees)

平衡二叉樹的定義：左右子樹深度差絕對值不能超過1。

是什么意思呢？比如左子樹的深度是2，右子樹的深度只能是1 或者3。

這個時候我們再按順序插入1、2、3、4、5、6，一定是這樣，不會變成一棵“斜樹”。

那它的平衡是怎么做到的呢？怎么保證左右子樹的深度差不能超過1 呢？

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

插入1、2、3。

我們注意看：當我們插入了1、2 之后，如果按照二叉查找樹的定義，3 肯定是要在2 的右邊的，這個時候根節點1 的右節點深度會變成2，但是左節點的深度是0，因為它沒有子節點，所以就會違反平衡二叉樹的定義。

那應該怎么辦呢？因為它是右節點下面接一個右節點，右-右型，所以這個時候我們要把2 提上去，這個操作叫做左旋。

同樣的，如果我們插入7、6、5，這個時候會變成左左型，就會發生右旋操作，把6提上去。

所以為了保持平衡，AVL 樹在插入和更新數據的時候執行了一系列的計算和調整的操作。

平衡的問題我們解決了，那么平衡二叉樹作為索引怎么查詢數據？

在平衡二叉樹中，一個節點，它的大小是一個固定的單位，作為索引應該存儲什么內容？

它應該存儲三塊的內容：

第一個是索引的鍵值。比如我們在id 上面創建了一個索引，我在用where id =1 的條件查詢的時候就會找到索引里面的id 的這個鍵值。

第二個是數據的磁盤地址，因為索引的作用就是去查找數據的存放的地址。

第三個，因為是二叉樹，它必須還要有左子節點和右子節點的引用，這樣我們才能找到下一個節點。比如大于26 的時候，走右邊，到下一個樹的節點，繼續判斷。

如果是這樣存儲數據的話，我們來看一下會有什么問題。

在分析用AVL 樹存儲索引數據之前，我們先來學習一下InnoDB 的邏輯存儲結構。

?

總結

以上是生活随笔為你收集整理的平衡二叉树（AVL Tree）（左旋、右旋）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。