建站
咨詢
售后
建站咨詢
新聞中心
AVL 樹的意義：是二分查找樹 BST 。二分查找樹查找某個值時，時間復(fù)雜度是 O(h) ，因此，我們讓樹的盡可能平衡，即最大高度盡可能的小。因此有了 AVL 。
創(chuàng)新互聯(lián)長期為上千余家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為北關(guān)企業(yè)提供專業(yè)的網(wǎng)站建設(shè)、網(wǎng)站制作，北關(guān)網(wǎng)站改版等技術(shù)服務(wù)。擁有10年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
參考例題：
- AcWing：AVL樹的根[1]
百度百科[2]：在計(jì)算機(jī)科學(xué)中，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點(diǎn)的兩個子樹的高度最大差別為1，所以它也被稱為高度平衡樹。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。AVL樹得名于它的發(fā)明者G. M. Adelson-Velsky和E. M. Landis，他們在1962年的論文《An algorithm for the organization of information》中發(fā)表了它。
BST 本質(zhì)上是維護(hù)一個有序序列，AVL 樹中的左旋右旋操作，并不會改變樹的中序遍歷結(jié)果。
上圖中把 A 右旋是怎么做的呢?把 B 旋轉(zhuǎn)到根節(jié)點(diǎn)，然后把 A 變成 B 的右孩子，把 E 補(bǔ)償給 A 作為 A 的左孩子。
左旋和右旋
對節(jié)點(diǎn) u 右旋：
- 根 u 的左兒子變成新的根 p
- 根的左兒子變成新的根 p 原本的右兒子
- 新的根 p 的右兒子變成了原本的根 u
- u 和 p 的高度都需要更新
- void R(int& u)
- {
- int p = l[u];
- l[u] = r[p], r[p] = u;
- update(u), update(p);
- u = p;
- }
對節(jié)點(diǎn) u 右旋：
- 根 u 的右兒子變成新的根 p
- 根的右兒子變成新的根 p 原本的左兒子
- 新的根 p 的左兒子變成了原本的根 u
- u 和 p 的高度都需要更新
- void L(int& u)
- {
- int p = r[u];
- r[u] = l[p], l[p] = u;
- update(u), update(p);
- u = p;
- }
高度更新由左右兒子決定，因?yàn)榍蟾叨葧r，默認(rèn)其兩個兒子已經(jīng)更新完高度了：
- void update(int u)
- {
- h[u] = max(h[l[u]], h[r[u]]) + 1;
- }
插入的四種情況
四種情況
(一)新數(shù)字插到了左子樹，導(dǎo)致左子樹比右子樹高2;左孩子的左子樹比其右子樹高1
對于四種情況中的①。應(yīng)該右旋 A 。
實(shí)例如上圖，右旋 88 即可。
(二)新數(shù)字插到了左子樹，導(dǎo)致左子樹比右子樹高2;左孩子的右子樹比其左子樹高1
對于四種情況中的③。應(yīng)該左旋 B 再右旋 A 。
對應(yīng)的情況如如下：
- 70
- 61
- 65
- // 左旋 61
- 70
- 65
- 61
- // 右旋 70
- 65
- 61 70
(三)新數(shù)字插到了右子樹，導(dǎo)致右子樹比左子樹高2;右孩子的右子樹比其左子樹高1
對于四種情況中的②。應(yīng)該左旋 A 。
對應(yīng)的情況如 88 96 120 ，左旋 88 即可。
(四)新數(shù)字插到了右子樹，導(dǎo)致右子樹比左子樹高2;右孩子的左子樹比其右子樹高1
對于四種情況中的④。應(yīng)該右旋 B 再左旋 A 。
對應(yīng)的情況如如下：
- 70
- 96
- 88
- // 右旋 96
- 70
- 88
- 96
- // 左旋 70
- 96
- 70 88
插入的代碼
- void insert(int& u, int w)
- {
- if (!u) u = ++ idx, v[u] = w;
- else if (w < v[u])
- {
- insert(l[u], w);
- if (get_balance(u) == 2)
- {
- if (get_balance(l[u]) == 1) R(u);
- else L(l[u]), R(u);
- }
- }
- else
- {
- insert(r[u], w);
- if (get_balance(u) == -2)
- {
- if (get_balance(r[u]) == -1) L(u);
- else R(r[u]), L(u);
- }
- }
- update(u);
- }
參考資料
[1]AVL樹的根: https://www.acwing.com/problem/content/description/1554/
[2]百度百科: https://baike.baidu.com/item/AVL%E6%A0%91/10986648
名稱欄目：AVL小樹轉(zhuǎn)轉(zhuǎn)轉(zhuǎn)轉(zhuǎn)轉(zhuǎn)，我的考試掛掛掛掛掛
文章URL：http://www.5511xx.com/article/coeiigp.html
