av激情亚洲男人的天堂国语,日韩欧美精品一中文字幕,无码av一区二区三区无码,国产又色又爽又刺激的a片,国产又色又爽又刺激的a片

AVL小樹轉(zhuǎn)轉(zhuǎn)轉(zhuǎn)轉(zhuǎn)轉(zhuǎn)，我的考試掛掛掛掛掛

AVL 樹的意義：是二分查找樹 BST 。二分查找樹查找某個值時，時間復(fù)雜度是 O(h) ，因此，我們讓樹的盡可能平衡，即最大高度盡可能的小。因此有了 AVL 。

創(chuàng)新互聯(lián)長期為上千余家客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗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)驗和眾多成功案例,為您定制開發(fā)。

參考例題：

  • AcWing：AVL樹的根[1]

百度百科[2]：在計算機科學(xué)中，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為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é)點，然后把 A 變成 B 的右孩子，把 E 補償給 A 作為 A 的左孩子。

左旋和右旋

對節(jié)點 u 右旋：

  • 根 u 的左兒子變成新的根 p
  • 根的左兒子變成新的根 p 原本的右兒子
  • 新的根 p 的右兒子變成了原本的根 u
  • u 和 p 的高度都需要更新
 
 
 
 
    
  
  
  
  
  1. void R(int& u) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     int p = l[u]; 
    4.   
  
  
  
  4.     l[u] = r[p], r[p] = u; 
    5.   
  
  
  
  5.     update(u), update(p); 
    6.   
  
  
  
  6.     u = p; 
    7.   
  
  
  
  7. } 
    8.

對節(jié)點 u 右旋：

  • 根 u 的右兒子變成新的根 p
  • 根的右兒子變成新的根 p 原本的左兒子
  • 新的根 p 的左兒子變成了原本的根 u
  • u 和 p 的高度都需要更新
 
 
 
 
    
  
  
  
  
  1. void L(int& u) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     int p = r[u]; 
    4.   
  
  
  
  4.     r[u] = l[p], l[p] = u; 
    5.   
  
  
  
  5.     update(u), update(p); 
    6.   
  
  
  
  6.     u = p; 
    7.   
  
  
  
  7. } 
    8.

高度更新由左右兒子決定，因為求高度時，默認(rèn)其兩個兒子已經(jīng)更新完高度了：

 
 
 
 
    
  
  
  
  
  1. void update(int u) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     h[u] = max(h[l[u]], h[r[u]]) + 1; 
    4.   
  
  
  
  4. } 
    5.

插入的四種情況

四種情況

(一)新數(shù)字插到了左子樹，導(dǎo)致左子樹比右子樹高2;左孩子的左子樹比其右子樹高1

對于四種情況中的①。應(yīng)該右旋 A 。

實例如上圖，右旋 88 即可。

(二)新數(shù)字插到了左子樹，導(dǎo)致左子樹比右子樹高2;左孩子的右子樹比其左子樹高1

對于四種情況中的③。應(yīng)該左旋 B 再右旋 A 。

對應(yīng)的情況如如下：

 
 
 
 
    
  
  
  
  
  1.   70 
    2.   
  
  
  
  2. 61 
    3.   
  
  
  
  3.   65 
    4.   
  
  
  
  4. // 左旋 61 
    5.   
  
  
  
  5.     70 
    6.   
  
  
  
  6.   65 
    7.   
  
  
  
  7. 61 
    8.   
  
  
  
  8. // 右旋 70 
    9.   
  
  
  
  9.   65 
    10.   
  
  
  
  10. 61  70 
    11.

(三)新數(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)的情況如如下：

 
 
 
 
    
  
  
  
  
  1.   70 
    2.   
  
  
  
  2. 96 
    3.   
  
  
  
  3.   88 
    4.   
  
  
  
  4. // 右旋 96 
    5.   
  
  
  
  5. 70 
    6.   
  
  
  
  6.   88 
    7.   
  
  
  
  7.     96 
    8.   
  
  
  
  8. // 左旋 70 
    9.   
  
  
  
  9.   96 
    10.   
  
  
  
  10. 70  88 
    11.

插入的代碼

 
 
 
 
    
  
  
  
  
  1. void insert(int& u, int w) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if (!u) u = ++ idx, v[u] = w; 
    4.   
  
  
  
  4.     else if (w < v[u]) 
    5.   
  
  
  
  5.     { 
    6.   
  
  
  
  6.         insert(l[u], w); 
    7.   
  
  
  
  7.         if (get_balance(u) == 2) 
    8.   
  
  
  
  8.         { 
    9.   
  
  
  
  9.             if (get_balance(l[u]) == 1) R(u); 
    10.   
  
  
  
  10.             else L(l[u]), R(u); 
    11.   
  
  
  
  11.         } 
    12.   
  
  
  
  12.     } 
    13.   
  
  
  
  13.     else 
    14.   
  
  
  
  14.     { 
    15.   
  
  
  
  15.         insert(r[u], w); 
    16.   
  
  
  
  16.         if (get_balance(u) == -2) 
    17.   
  
  
  
  17.         { 
    18.   
  
  
  
  18.             if (get_balance(r[u]) == -1) L(u); 
    19.   
  
  
  
  19.             else R(r[u]), L(u); 
    20.   
  
  
  
  20.         } 
    21.   
  
  
  
  21.     } 
    22.   
  
  
  
  22.  
    23.   
  
  
  
  23.     update(u); 
    24.   
  
  
  
  24. } 
    25.

參考資料

[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://uogjgqi.cn/article/coeiigp.html
掃二維碼與項目經(jīng)理溝通

我們在微信上24小時期待你的聲音

解答本文疑問/技術(shù)咨詢/運營咨詢/技術(shù)建議/互聯(lián)網(wǎng)交流