之前簡單了解過 AVL 樹，知道概念但一直沒動(dòng)手實(shí)踐過。Now
 
 AVL 樹是二叉搜索樹的一種。二叉搜索樹的規(guī)則就是：每個(gè)節(jié)點(diǎn)的 left child 都比自己小，right child 都比自己大。而 AVL 的在此之上又加了一個(gè)規(guī)則：每個(gè)節(jié)點(diǎn)的 left 深度與 right 深度只差<=1，這樣就能充分利用 二叉樹的結(jié)構(gòu)，避免出現(xiàn)一個(gè)分支走到黑，導(dǎo)致搜索效率變低。如下圖：
                                             
                                這種樹結(jié)構(gòu)，搜索起來完全沒有體現(xiàn)出二叉搜索樹的優(yōu)勢
 
所以同樣多的元素，搜索樹的深度越低，就會(huì)越快的定位到搜索點(diǎn)。
 
AVL 樹為了保持樹的平衡，每次插入、刪除都會(huì)檢查 每個(gè)受影響的節(jié)點(diǎn)，深度差是否 <  1。最難的部分就是如果樹失衡，如何調(diào)整節(jié)點(diǎn)。插入的處理流程大致如下：
     給定一個(gè) value，一路比較直到插入到某個(gè)位置。然后查找哪些節(jié)點(diǎn)因此而失衡，針對(duì)第一個(gè)失衡的節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)。
 
下面是我從另一個(gè)博客上找來的圖（http://blog.csdn.net/gabriel1026/article/details/6311339），介紹了四種失衡的情況，以及調(diào)整方式：
注：圖中紅色的小塊 表示新插入的元素，A 點(diǎn)表示從插入點(diǎn)向上，發(fā)現(xiàn)的第一個(gè)失衡的點(diǎn)。
 
      AVL樹的旋轉(zhuǎn)一共有四種情形，注意所有旋轉(zhuǎn)情況都是圍繞著使得二叉樹不平衡的第一個(gè)節(jié)點(diǎn)展開的。
1： 

我想了解如何學(xué)習(xí)

姓名：
手機(jī)：
留言：