平衡二叉树理论详解
文章目錄
- 基本概念
- 平衡二叉樹插入結(jié)點
- LL（左單旋）
- RR（右單旋）
- LR（左右旋）
- RL（右左旋）
- 示例插入推導(dǎo)過程
基本概念
平衡二叉樹是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹
又被稱為AVL（Adelson-Velsky and Landis）樹
如圖所示，第三個圖中的樹左右高差為2，是一顆不平衡的二叉樹。
平衡二叉樹插入結(jié)點
在平衡二叉樹結(jié)點的插入過程中，可能會導(dǎo)致樹從平衡變成不平衡的情況，具體有四種情況，如下所示：
LL（左單旋）
由于插入到左孩子的左孩子上導(dǎo)致的不平衡。
恢復(fù)平衡辦法： 一次向右旋轉(zhuǎn)即可
如圖：以B節(jié)點為軸，向右旋轉(zhuǎn)
以B節(jié)點為軸向右旋轉(zhuǎn)，B節(jié)點的右子樹成為A節(jié)點的左子樹
RR（右單旋）
由于插入到右孩子的右孩子上導(dǎo)致的不平衡。
恢復(fù)平衡辦法： 一次向左旋轉(zhuǎn)即可
如圖：以B節(jié)點為軸，向左旋轉(zhuǎn)
以B節(jié)點為軸，向左旋轉(zhuǎn)，B結(jié)點的左子樹成為A節(jié)點的右子樹
LR（左右旋）
由于插入到左孩子的右孩子上導(dǎo)致的不平衡。
恢復(fù)平衡辦法： 先向左旋轉(zhuǎn)，再向右旋轉(zhuǎn)
如圖：
1、以B節(jié)點為軸，向左旋轉(zhuǎn)
2、以C節(jié)點為軸，向右旋轉(zhuǎn)
下圖同上面圖一個意思，只是考慮節(jié)點多一些。
RL（右左旋）
由于插入到右孩子的左孩子上導(dǎo)致的不平衡。
恢復(fù)平衡辦法： 先向右旋轉(zhuǎn)，再向左旋轉(zhuǎn)
如圖：
1、以B節(jié)點為軸，向右旋轉(zhuǎn)
2、以C節(jié)點為軸，向左旋轉(zhuǎn)
下圖同上面圖一個意思，只是考慮節(jié)點多一些。
示例插入推導(dǎo)過程
例題：輸入關(guān)鍵字序列(16，3，7，11 ，9，26)給出AVL樹
如圖推導(dǎo)過程：
ps:計劃每日更新一篇博客，今日2023-05-12，日更第二十六天。（補更）
昨日更新：
動態(tài)規(guī)劃理論基礎(chǔ)
總結(jié)
