文章目錄
- 一、 相關概念
- 1.1 AVL定義
- 1.2 平衡因子
- 1.3 AVL的作用
- 二、 失衡調整
- 2.1 LL型
- 2.2 RR型
- 2.3 LR型
- 2.4 RL型
一、 相關概念
1.1 AVL定義
平衡二叉樹又稱為AVL樹，它或者是顆空樹，或者是具有下列性質的二叉排序樹：
- 左右兩個子樹的高度差值不超過1；
- 它的左右子樹也是一顆平衡二叉樹；
1.2 平衡因子
某節點的左子樹與右子樹的高度差即為該節點的平衡因子BF，
按照定義我們可以得到，AVL上所有結點的平衡因子只可能是 -1，0 或 1，
下面這張圖中標出了每一個節點的平衡因子，而根節點的平衡因子為-2，所以顯然這不是一顆平衡二叉樹，
1.3 AVL的作用
為了解決搜索二叉樹在極端的情況下退化成單支樹，引入了平衡二叉樹，使得查找的效率得到改善；
二、 失衡調整
在平衡二叉樹中插入一個新結點后，從該結點起向上尋找第一個不平衡的結點，以確定該樹是否失衡，若找到，則以該結點為根的子樹稱為最小失衡子樹，
2.1 LL型
LL型指的是在最小失衡子樹的左孩子的左子樹上插入了新的結點，
LL型指的是在最小失衡子樹左孩子的左子樹上插入了新的結點，失衡調整如下圖，先找到最小失衡子樹的根8，以其左孩子結點6為軸，對不平衡結點8進行右旋操作，右旋是指讓6頂替8的位置成為原本最小不平衡子樹的新的根節點，并置8為6的右孩子，如果6存在右子樹7,則置7為8的左子樹，
2.2 RR型
RR型指的是在最小失衡子樹的右孩子的右子樹上插入了新的結點，與LL型對稱，
失衡調整如下圖，先找到最小失衡子樹的根6，以其右孩子結點8為軸，對不平衡結點6進行左旋操作，左旋是指讓8頂替6的位置成為原本最小不平衡子樹的新的根節點，并置6為8的左孩子，如果8存在左子樹7,則置7為6的右子樹，
2.3 LR型
LR型指的是最小失衡子樹的左孩子的右子樹上插入了新的結點，
LR型要進行兩步操作，與名字對應，先左旋再右旋，
失衡調整如下圖，首先找到以10為根的最小失衡子樹，以該子樹的左孩子結點4為軸，對右子樹結點8進行左旋操作，使之變為LL型，再以8為軸，對不平衡結點10進行右旋操作，
2.4 RL型
RL型指的是最小失衡子樹的右孩子的左子樹上插入了新的結點，
RL型與LR型對稱，也要進行兩步操作，先右旋再左旋，
失衡調整如下圖，首先找到以2為根的最小失衡子樹，以該子樹的右孩子結點10為軸，對左子樹結點8進行右旋操作，使之變為RR型，再以8為軸，對不平衡結點2進行左旋操作，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/295648.html
標籤：其他
上一篇：順序表和鏈表的詳細對比