之前簡(jiǎn)單了解過(guò) AVL 樹(shù),知道概念但一直沒(méi)動(dòng)手實(shí)踐過(guò)。Now
AVL 樹(shù)是二叉搜索樹(shù)的一種。二叉搜索樹(shù)的規(guī)則就是:每個(gè)節(jié)點(diǎn)的 left child 都比自己小,right child 都比自己大。而 AVL 的在此之上又加了一個(gè)規(guī)則:每個(gè)節(jié)點(diǎn)的 left 深度與 right 深度只差<=1,這樣就能充分利用 二叉樹(shù)的結(jié)構(gòu),避免出現(xiàn)一個(gè)分支走到黑,導(dǎo)致搜索效率變低。如下圖:

這種樹(shù)結(jié)構(gòu),搜索起來(lái)完全沒(méi)有體現(xiàn)出二叉搜索樹(shù)的優(yōu)勢(shì)
所以同樣多的元素,搜索樹(shù)的深度越低,就會(huì)越快的定位到搜索點(diǎn)。
AVL 樹(shù)為了保持樹(shù)的平衡,每次插入、刪除都會(huì)檢查 每個(gè)受影響的節(jié)點(diǎn),深度差是否 < 1。最難的部分就是如果樹(shù)失衡,如何調(diào)整節(jié)點(diǎn)。插入的處理流程大致如下:
給定一個(gè) value,一路比較直到插入到某個(gè)位置。然后查找哪些節(jié)點(diǎn)因此而失衡,針對(duì)第一個(gè)失衡的節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)。
下面是我從另一個(gè)博客上找來(lái)的圖(http://blog.csdn.net/gabriel1026/article/details/6311339),介紹了四種失衡的情況,以及調(diào)整方式:
注:圖中紅色的小塊 表示新插入的元素,A 點(diǎn)表示從插入點(diǎn)向上,發(fā)現(xiàn)的第一個(gè)失衡的點(diǎn)。
AVL樹(shù)的旋轉(zhuǎn)一共有四種情形,注意所有旋轉(zhuǎn)情況都是圍繞著使得二叉樹(shù)不平衡的第一個(gè)節(jié)點(diǎn)展開(kāi)的。
1: