「AVL 旋轉」存在的目的是什麼？儘管有 logN 的時間複雜度，樹的 hierarchy 豈不全亂了？

01-02

初學數據結構，有一問題不得解。

AVL樹是搜索用的，樹的hierarchy本身沒什麼特別的意義。旋轉的關鍵是，保證平衡，並且中序遍歷後的順序不變。可以把它理解為一個黑箱，查找使用，我們並不需要知道它內部的hierarchy。

旋轉是為了讓樹平衡，不平衡的樹查找性能比較差

AVL旋轉是AVL樹的旋轉，AVL樹存在的意義是二分法查找，二分法查找的要求是能找到要找的結點，而樹的層級結構只要能滿足這一點就可以。

假設一顆不平衡的二叉樹，從根節點開始查找，可以找到某個葉子結點，中間經過四次分叉；經過AVL旋轉，再次從樹的根節點開始查找（根節點也許變了），中間可能只要兩次分叉，但是仍舊會找到要找的葉子結點。樹的拓撲結構的確改變了，但是每個結點與其他結點之間的關係，也就是局部邏輯，並沒有改變。

樹的最終目的不是維護節點與節點之間的層級關係。

AVL樹是「自平衡二叉查找樹」的一種實現方式，那為什麼會出現「自平衡二叉查找樹」呢？主要是因為「二叉查找樹」在遇到有序數列的情況下會退化成「鏈表」

而「鏈表」查找元素的時間複雜度為O(n)。所以為了避免出現這種情況，就需要「自平衡」。

AVL樹的自平衡是通過旋轉來實現的，有左旋(處理RR)，右旋(處理LL)，左右旋(處理LR)，右左旋(處理RL)這4種，因為旋轉方式比較多，所以編程實現上會稍微複雜些。

另外還有一種類似的數據結構：Treap (Tree + Heap)，在具備「二叉查找樹」性質的同時，還兼具「最小堆」的特性，編程實現複雜度較低，同時時間複雜度也低（搜索/插入/刪除均為O(log n)）

byvoid專門為treap寫過一篇論文：http://www.byvoid.com/blog/wp-content/uploads/2010/12/treap-analysis-and-application.pdf

平衡二叉樹是用來做查找的工具而已。如果只有平衡二叉樹，你面對的數據還是一堆可以快速檢索的、有順序關係的單個結點。所以本來就沒有樹的 herarchy 可以破壞。

AVL樹本質上還是一棵二叉搜索樹，它的特點是：
1.本身首先是一棵二叉搜索樹。
2.帶有平衡條件：每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1。

「AVL 旋轉」的目的是保證AVL樹的性質2.

你說的hierarchy 亂了是什麼意思？旋轉的目的就是要確保層高不亂啊。（層高之差&<2）

再說一點就是，只要保證性質2，不一定得使用旋轉這個操作。

旋轉這個操作好處多：

怎麼轉它都是一顆二叉樹
它實現簡單，不容易錯
旋轉可以改變平衡因子，且變化不會太大。

int balance(avl* root,int cl,int cr) { avl*tl=root-&>l,*tr=root-&>r; avl* t=root; if((cr-cl)==2){ if(deep(tr-&>l)&>deep(tr-&>r)){ auto nroot=tr-&>l; t-&>r=nroot-&>l; tr-&>l=nroot-&>r; root=nroot; root-&>l=t; root-&>r=tr;


		}else{

			t-&>r=tr-&>l;

			root=tr;

			root-&>l=t;

		}

		return cr;

	}

	if((cl-cr)==2){

		if(deep(tl-&>l)&r)){

			auto nroot=tl-&>r;

			t-&>l=nroot-&>r;

			tl-&>r=nroot-&>l;

			root=nroot;

			root-&>r=t;

			root-&>l=tl;

}else{ t-&>l=tl-&>r; root=tl; root-&>r=t; } return cl; } assert(0); }

這是非旋轉的版本，花了我2個多小時才寫對。如果是用旋轉的話，半個小時夠了。

AVL就是為了快速插入，刪除，查找。不需要知道每個結點的父與子。

查找最壞複雜度是O（ n2）, 平衡將最壞複雜度提高的O（lgn）但是破壞了樹結構，適合於黑盒存儲的地方， AVL樹被紅黑樹替代，後者保持了樹結構。

保持平衡。平衡二叉樹的平均搜索次數比較少，在刪除或者插入的時候保持為二叉排序樹，並且高度最小，這樣查找的速度就會略高於二叉排序樹