AVL樹來(lái)自"NOCOW"本文在GNU自由文檔許可證之條款下提供 在計(jì)算機(jī)科學(xué)中，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點(diǎn)的兩個(gè)兒子子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過(guò)一次或多次樹旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹。AVL樹得名于它的發(fā)明者 G.M. Adelson-Velsky 和 E.M. Landis，他們?cè)?962年的論文 "An algorithm for the organization of information" 中發(fā)表了它。 節(jié)點(diǎn)的平衡因子是它的右子樹的高度減去它的左子樹的高度。帶有平衡因子 1、0 或 -1 的節(jié)點(diǎn)被認(rèn)為是平衡的。帶有平衡因子 -2 或 2 的節(jié)點(diǎn)被認(rèn)為是不平衡的，并需要重新平衡這個(gè)樹。平衡因子可以直接存儲(chǔ)在每個(gè)節(jié)點(diǎn)中，或從可能存儲(chǔ)在節(jié)點(diǎn)中的子樹高度計(jì)算出來(lái)。
[編輯] 操作AVL樹的基本操作一般涉及運(yùn)做同在不平衡的二叉查找樹所運(yùn)做的同樣的算法。但是要進(jìn)行預(yù)先或隨后做一次或多次所謂的"AVL 旋轉(zhuǎn)"。 假設(shè)由于在二叉排序樹上插入結(jié)點(diǎn)而失去平衡的最小子樹根結(jié)點(diǎn)的指針為a(即a是離插入點(diǎn)最近，且平衡因子絕對(duì)值超過(guò)1的祖先結(jié)點(diǎn))，則失去平衡后進(jìn)行進(jìn)行的規(guī)律可歸納為下列四種情況：
[編輯] 插入向AVL樹插入可以通過(guò)如同它是未平衡的二叉查找樹一樣把給定的值插入樹中，接著自底向上向根節(jié)點(diǎn)折回，于在插入期間成為不平衡的所有節(jié)點(diǎn)上進(jìn)行旋轉(zhuǎn)來(lái)完成。因?yàn)檎刍氐礁?jié)點(diǎn)的路途上最多有 1.5 乘 log n 個(gè)節(jié)點(diǎn)，而每次 AVL 旋轉(zhuǎn)都耗費(fèi)恒定的時(shí)間，插入處理在整體上耗費(fèi) O(log n) 時(shí)間。 在平衡的二叉排序樹Balanced BST上插入一個(gè)新的數(shù)據(jù)元素e的遞歸算法可描述如下：
[編輯] 刪除從AVL樹中刪除可以通過(guò)把要?jiǎng)h除的節(jié)點(diǎn)向下旋轉(zhuǎn)成一個(gè)葉子節(jié)點(diǎn)，接著直接剪除這個(gè)葉子節(jié)點(diǎn)來(lái)完成。因?yàn)樵谛D(zhuǎn)成葉子節(jié)點(diǎn)期間最多有 log n個(gè)節(jié)點(diǎn)被旋轉(zhuǎn)，而每次 AVL 旋轉(zhuǎn)耗費(fèi)恒定的時(shí)間，刪除處理在整體上耗費(fèi) O(log n) 時(shí)間。（感覺(jué)這樣處理之后，有可能這個(gè)樹就不一定還是AVL樹了，正確應(yīng)該在刪除的時(shí)候也像插入的時(shí)候一樣，需要旋轉(zhuǎn)調(diào)整的吧） [編輯] 查找在AVL樹中查找同在一般BST完全一樣的進(jìn)行，所以耗費(fèi) O(log n) 時(shí)間，因?yàn)锳VL樹總是保持平衡的。不需要特殊的準(zhǔn)備，樹的結(jié)構(gòu)不會(huì)由于查詢而改變。(這是與伸展樹查找相對(duì)立的，它會(huì)因?yàn)椴檎叶兏鼧浣Y(jié)構(gòu)。) [編輯] 參考實(shí)現(xiàn)[編輯] 使用高度替代平衡因子在linux早期的內(nèi)核中，AVL樹便是用存儲(chǔ)高度來(lái)判別樹是否平衡的，這樣的好處是能直接的得到任一節(jié)點(diǎn)的高度，旋轉(zhuǎn)時(shí)的更新也更容易（參看下面的推算）。使用高度替代平衡因子的實(shí)現(xiàn)：AVL C++ Alternative Height Based [編輯] 平衡因子的推算在AVL樹的旋轉(zhuǎn)過(guò)程中，平衡因子（高度）的改變可以通過(guò)旋轉(zhuǎn)的類型推算得到。下面的推算是從本人的code中摘取的注釋，其中： * bf(N) 節(jié)點(diǎn)N的平衡因子(balance factor) * h(N) 節(jié)點(diǎn)N的高度 (height) * No 旋轉(zhuǎn)前的節(jié)點(diǎn)N (old node) * Nn 旋轉(zhuǎn)后的節(jié)點(diǎn)N (new node) * 高度和平衡因子保持不變的節(jié)點(diǎn)用數(shù)字 1, 2, 3...表示 /* LL: right rotate * * (N) (L) * / \ / * (L) 3 ==> 1 (N) * / \ / * 1 2 2 3 * * * how to get bf(Nn) ? * * bf(No) = h(Lo)-h(3) * bf(Nn) = h(2)-h(3) * bf(No)-bf(Nn) = h(Lo)-h(2) * = max(h(1), h(2))+1-h(2) * = max(h(1)-h(2), 0)+1 * = max(bf(Lo), 0)+1 * * bf(Nn) = bf(No)-(max(bf(Lo), 0)+1) * * Result: * * bf(N) -= max(bf(bf(Lo), 0)+1 * * how to get bf(Ln) ? * * bf(Lo) = h(1)-h(2) * bf(Ln) = h(1)-h(Nn) * bf(Ln)-bf(Lo) = h(2)-h(Nn) * = h(2)-max(h(2), h(3))-1 * = min(0, h(2)-h(3))-1 * = min(0, bf(Nn))-1 * * bf(Ln) = bf(Lo)+(min(0, bf(Nn))-1) * * Result: * * bf(L) += min(0, bf(Nn))-1 * * how to get height ? * * h(Nn) = max(h(2), h(3))+1 * h(Ln) = max(h(1), h(Nn))+1 * */ /* RR: left rotate * * (N) (R) * / \ / * 1 (R) ==> (N) 3 * / \ / * 2 3 1 2 * * * how to get bf(Nn) ? * * bf(No) = h(1)-h(Ro) * bf(Nn) = h(1)-h(2) * bf(No)-bf(Nn) = h(2)-h(Ro) * = h(2)-max(h(2), h(3))-1 * = min(0, h(2)-h(3))-1 * = min(0, bf(Ro))-1 * * bf(Nn) = bf(No)-(min(0, bf(Ro))-1) * * Result: * * bf(N) -= min(0, bf(Ro))-1 * * how to get bf(Rn) ? * * bf(Ro) = h(2)-h(3) * bf(Rn) = h(Nn)-h(3) * bf(Rn)-bf(Ro) = h(Nn)-h(2) * = max(h(1), h(2))+1-h(2) * = max(h(1)-h(2), 0)+1 * = max(bf(Nn), 0)+1 * * bf(Rn) = bf(Ro)+(max(bf(Nn), 0)+1) * * Result: * * bf(R) += max(bf(Nn), 0)+1 * * how to get height ? * * h(Nn) = max(h(1), h(2))+1 * h(Rn) = max(h(Nn), h(3))+1 * */ /* LR: left-right rotate * * (N) (LR) * / \ / * (L) 4 ==> (L) (N) * / \ / \ / * 1 (LR) 1 2 3 4 * / * 2 3 * * note that left-right rotate could be implemented as a call to * left_rotate(L) followed by a call to right_rotate(N). * * how to get bf(Ln) ? * * bf(Lo) = h(1)-h(LRo) * bf(Ln) = h(1)-h(2) * bf(Lo)-bf(Ln) = h(2)-h(LRo) * = h(2)-max(h(2), h(3))-1 * = min(0, h(2)-h(3))-1 * = min(0, bf(LRo))-1 * * bf(Ln) = bf(Lo)-(min(0, bf(LRo))-1) * * Result: * * bf(L) -= min(0, bf(LRo))-1 * * how to get bf(Nn) ? * * bf(No) = h(Lo)-h(4) * bf(Nn) = h(3)-h(4) * bf(No)-bf(Nn) = h(Lo)-h(3) * = max(h(1), max(h(2), h(3))+1)+1-h(3) * = max(h(1)-h(3), max(h(2)-h(3), 0)+1)+1 * = max(h(1)-h(3), max(bf(LRo), 0)+1)+1 * bf(Ln) = h(1)-h(2) * bf(LRo) = h(2)-h(3) * h(1)-h(3) = bf(Ln)+bf(LRo) * * bf(Nn) = bf(No)-(max(bf(Ln)+bf(LRo), max(bf(LRo), 0)+1)+1) * * Result: * * bf(N) -= max(bf(Ln)+bf(LRo), max(bf(LRo), 0)+1)+1 * * how to get bf(LRn) ? * * bf(LRo) = h(2)-h(3) * bf(LRn) = h(Ln)-h(Nn) * bf(LRn)-bf(LRo) = h(Ln)-h(2)+h(3)-h(Nn) * = max(h(1), h(2))+1-h(2)+h(3)-max(h(3), h(4))-1 * = max(h(1)-h(2), 0)+min(0, h(3)-h(4)) * = max(bf(Ln), 0)+min(0, bf(Nn)) * * bf(LRn) = bf(LRo)+(max(bf(Ln), 0)+min(0, bf(Nn))) * * Result: * * bf(LR) += max(bf(Ln), 0)+min(0, bf(Nn)) * */ /* right-left rotate * * (N) (RL) * / \ / * 1 (R) ==> (N) (R) * / \ / \ / * (RL) 4 1 2 3 4 * / * 2 3 * * note that right-left rotate could be implemented as a call to * right_rotate(R) followed by a call to left_rotate(N). * * how to get bf(Rn) ? * * bf(Ro) = h(RLo)-h(4) * bf(Rn) = h(3)-h(4) * bf(Ro)-bf(Rn) = h(RLo)-h(3) * = max(h(2), h(3))+1-h(3) * = max(h(2)-h(3), 0)+1 * = max(bf(RLo), 0)+1 * * bf(Rn) = bf(Ro)-(max(bf(LRo), 0)+1) * * Result: * * bf(R) -= max(bf(LRo), 0)+1 * * how to get bf(Nn) ? * * bf(No) = h(1)-h(Ro) * bf(Nn) = h(1)-h(2) * bf(No)-bf(Nn) = h(2)-h(Ro) * = h(2)-max(max(h(2), h(3))+1, h(4))-1 * = min(h(2)-max(h(2), h(3))-1, h(2)-h(4))-1 * = min(min(0, h(2)-h(3))-1, h(2)-h(4))-1 * = min(min(0, bf(RLo))-1, h(2)-h(4))-1 * bf(Rn) = h(3)-h(4) * bf(RLo) = h(2)-h(3) * h(2)-h(4) = bf(Rn)+bf(RLo) * * bf(Nn) = bf(No)-(min(min(0, bf(RLo))-1, bf(Rn)+bf(RLo))-1) * * Result: * * bf(N) -= min(bf(Rn)+bf(RLo), min(bf(RLo), 0)-1)-1 * * how to get bf(RLn) ? * * bf(RLo) = h(2)-h(3) * bf(RLn) = h(Nn)-h(Rn) * bf(RLn)-bf(RLo) = h(Nn)-h(2)+h(3)-h(Rn) * = max(h(1), h(2))+1-h(2)+h(3)-max(h(3), h(4))-1 * = max(h(1)-h(2), 0)+min(0, h(3)-h(4)) * = max(bf(Nn), 0)+min(0, bf(Rn)) * * bf(RLn) = bf(RLo)+(max(bf(Nn), 0)+min(0, bf(Rn))) * * Result: * * bf(RL) += max(bf(Nn), 0)+min(0, bf(Rn)) * */ |
|
|
