??作者：一只大喵咪1201
??專欄：《數(shù)據(jù)結(jié)構(gòu)與算法》
??格言：你只管努力，剩下的交給時(shí)間！
我們知道，二叉搜索樹的搜索效率非常高，平均時(shí)間復(fù)雜度是O(log2N)，但是當(dāng)數(shù)據(jù)原本就有序時(shí)，插入二叉樹中就會(huì)形成單支結(jié)構(gòu)，此時(shí)搜索的時(shí)間復(fù)雜度就是O(N)。
為了避免二叉搜索樹的這個(gè)缺陷，在它的基礎(chǔ)上提出了AVL樹(高度平衡二叉搜索樹)和紅黑樹。
??AVL樹
- AVL樹：當(dāng)向二叉搜索樹中插入新節(jié)點(diǎn)后，要保證每個(gè)節(jié)點(diǎn)的左右子樹高度差的絕對(duì)值不超過1。
根據(jù)高度差不超過1的規(guī)制，可以避免二叉搜索樹出現(xiàn)單支的情況，使其更加接近完全二叉樹，保證搜索效率是O(log2N)。
AVL樹的性質(zhì)：
- 它的左右子樹都是AVL樹。
- 左右子樹的高度差(簡稱平衡因子)的絕對(duì)值不超過1。
注意： 一顆空樹或者只有一個(gè)根的樹也屬于AVL樹。
- 平衡因子 = 右子樹高度 - 左子樹高度
- a和b兩種情況下根節(jié)點(diǎn)的平衡因子都是是0，因?yàn)榇藭r(shí)左右子樹高度相同。
- c情況下根節(jié)點(diǎn)的平衡因子是-1，因?yàn)榇藭r(shí)左子樹比右子樹多一個(gè)節(jié)點(diǎn)。
- d情況下根節(jié)點(diǎn)的平衡因子是1，因?yàn)榇藭r(shí)左子樹比右子樹少一個(gè)節(jié)點(diǎn)。
在AVL樹中，每個(gè)節(jié)點(diǎn)的平衡因子只能是1，0，-1三種情況，一旦不是這三種就需要進(jìn)行調(diào)整，保證平衡因子不會(huì)出現(xiàn)第四種情況。
插入新節(jié)點(diǎn)10以后，導(dǎo)致多個(gè)節(jié)點(diǎn)的平衡因子發(fā)生了變化：
- 節(jié)點(diǎn)9的平衡因子從0變成了1，說明新節(jié)點(diǎn)插入到了節(jié)點(diǎn)9的右邊。
- 節(jié)點(diǎn)8的平衡因子從1變成了2，因?yàn)樾鹿?jié)點(diǎn)插入到了節(jié)點(diǎn)8的右子樹中。
- 節(jié)點(diǎn)8的平衡因子不再是1，0，-1三個(gè)數(shù)中的一個(gè)，所以就需要進(jìn)行調(diào)整。
至于怎么調(diào)整一會(huì)兒本喵再詳細(xì)講解。
??AVL樹的插入
破壞二叉搜索樹平衡的操作主要就是插入，所以我們主要來看看AVL樹是如何插入的，是如何在插入過程中保證平衡的。
節(jié)點(diǎn)的定義：
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;//鍵值對(duì)
AVLTreeNode* _left;//左子樹
AVLTreeNode* _right;//右子樹
AVLTreeNode* _parent;//父節(jié)點(diǎn)
int _bf;//平衡因子balance factor
//節(jié)點(diǎn)的構(gòu)造函數(shù)
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
};
- 節(jié)點(diǎn)中的值是一個(gè)鍵值對(duì)。
- 是一個(gè)三叉鏈的結(jié)構(gòu)，不僅有左右子節(jié)點(diǎn)的指針，還有父節(jié)點(diǎn)的指針。
- 平衡因子用來衡量該節(jié)點(diǎn)的狀態(tài)，默認(rèn)情況下是0。
AVL樹的定義：
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode Node;
public:
bool insert(const pair<K, V>& kv)
{
//............
}
protected:
Node* _root = nullptr;//缺省值
};
和二叉搜索樹一樣，AVL樹種也是只有一個(gè)成員變量根，給根一個(gè)缺省值，默認(rèn)情況下它是空樹。
插入：
AVL樹的插入和二叉搜索樹的插入在前半部分一模一樣，大于根的插入到右邊，小于根的插入到左邊，區(qū)別在于AVL樹插入后的調(diào)整。
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool insert(const pair<K, V>& kv)
{
//空樹時(shí)直接插入
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//插入節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)，插入右邊
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
//插入節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)，插入左邊
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
//插入節(jié)點(diǎn)等于當(dāng)前節(jié)點(diǎn)
else
{
//不允許插入
return false;
}
}
cur = new Node(kv);
//判斷當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//更新平衡因子，進(jìn)行調(diào)整
break;
}
}
上面代碼是將節(jié)點(diǎn)插入到二叉搜索樹中的代碼，不再解釋，最重要的是后面的更新平衡因子，這才是AVL樹的重點(diǎn)。
??AVL樹的旋轉(zhuǎn)
平衡因子不是-1/0/1的節(jié)點(diǎn)進(jìn)行調(diào)整，調(diào)整的方式是旋轉(zhuǎn)，下面本喵來詳細(xì)介紹一下如何旋轉(zhuǎn)。
每一個(gè)子樹都是一個(gè)AVL樹，所以子樹的平衡因子發(fā)生變化，勢(shì)必會(huì)對(duì)其父節(jié)點(diǎn)以及祖父節(jié)點(diǎn)等祖宗節(jié)點(diǎn)有影響，可能會(huì)引發(fā)一系列的調(diào)整。
當(dāng)子樹更新完畢后，是否繼續(xù)向上更新平衡因子的依據(jù)是子樹的高度是否發(fā)生變化：
- parent->_bf == 0，說明之前是-1或者1，說明插入之前，該節(jié)點(diǎn)的左右子樹一邊高一邊低，此次插入填平了，但是高度沒有發(fā)生變化，所以不用繼續(xù)向上更新。
- parent->_bf == 1 或者 parent->_bf == -1，說明之前是，兩邊一樣高，此次插入導(dǎo)致一邊高于另外一邊，高度發(fā)生了變化，所以需要繼續(xù)向上更新。
- parent->_bf == 2 或者 parent->_bf == -1，說明之前是1或者-1，本來就左右不平衡，此次插入導(dǎo)致更加不平衡，違反了規(guī)則，需要進(jìn)行旋轉(zhuǎn)處理。
更新平衡因子的代碼：
//更新平衡因子，進(jìn)行調(diào)整
while (parent)//最差更新到根
{
//左邊新插入，平衡因子減一
if (cur == parent->_left)
{
parent->_bf--;
}
//右邊新插入，平衡因子加一
else
{
parent->_bf++;
}
//跟新后的平衡因子是0，說明高度沒有變化，不用繼續(xù)更新
if (parent->_bf == 0)
{
break;
}
//新插入節(jié)點(diǎn)，高度發(fā)生了變化，向上更新
else if(parent->_bf==1 || parent->_bf == -1)
{
//向上更新父節(jié)點(diǎn)
cur = parent;
parent = parent->_parent;
}
//高度差超出1，進(jìn)行旋轉(zhuǎn)
else if(parent->_bf == 2 || parent->_bf == -2)
{
//旋轉(zhuǎn)
//更新旋轉(zhuǎn)后的平衡因子
}
//前面出錯(cuò)，正常情況下不會(huì)進(jìn)入這里
else
{
//出錯(cuò)直接退出
assert(false);
}
旋轉(zhuǎn)的作用：
- 讓這顆子樹左右高度差不超過1。
- 旋轉(zhuǎn)過程中繼續(xù)保持它是搜索樹。
- 更新旋轉(zhuǎn)節(jié)點(diǎn)和其孩子節(jié)點(diǎn)的平衡因子。
- 讓這顆子樹的高度跟插入之前保持一直。
左單旋
- 插入新節(jié)點(diǎn)以后，右子樹的高度發(fā)生了變化，最終變成了2，需要進(jìn)行旋轉(zhuǎn)。
旋轉(zhuǎn)過程：
- 30變成60的左子節(jié)點(diǎn)，60變成根節(jié)點(diǎn)。
- 30和60的平衡因子都變成了0。
在上圖的基礎(chǔ)上，左右子樹同時(shí)增加一層節(jié)點(diǎn)，如下圖：
- 插入新節(jié)點(diǎn)后，右子樹高度發(fā)生了變化，最后變成了2，需要進(jìn)行旋轉(zhuǎn)。
旋轉(zhuǎn)過程：
- 40變成30的右子節(jié)點(diǎn)
- 30變成60的左子節(jié)點(diǎn)
- 60變成根節(jié)點(diǎn)
- 30和60的平衡因子變成0。
在上圖基礎(chǔ)上再增加一層節(jié)點(diǎn)，如下圖：
此時(shí)30的左子樹有兩層，右子樹有3層。
- 左子樹的兩層有三種情況，如黑色箭頭指向的，這里使用紅色框代表兩層子樹。
- 右子樹中要想讓新增節(jié)點(diǎn)引起旋轉(zhuǎn)，新增的兩層節(jié)點(diǎn)必須如上圖所示。
- 新插入的節(jié)點(diǎn)可以插入的位置有兩個(gè)，如上圖實(shí)線圈和虛線圈所示。
旋轉(zhuǎn)過程：
- 60的左子樹變成30的右子樹。
- 30變成60的左子樹。
- 60變成根。
- 30和60的平衡因子變成0。
從新增兩層開始就有多種情況了，當(dāng)層數(shù)越多，情況就越多，所以使用抽象圖來代表有多層子樹的情況：
a，b，c都是高度為h的AVL子樹。
- 在子樹c處插入新節(jié)點(diǎn)，此時(shí)c子樹高度變成了h+1，更新平衡因子，最終導(dǎo)致30的平衡因子變成了2，需要進(jìn)行旋轉(zhuǎn)。
旋轉(zhuǎn)過程：
- 60的左子樹變成30的右子樹。
- 30變成60的左子樹。
- 60變成根。
- 30和60的平衡因子變成0。
通過上面具象圖和抽象圖插入節(jié)點(diǎn)后的旋轉(zhuǎn)，我們可以總結(jié)出一些規(guī)律：
- 插入新的節(jié)點(diǎn)后，平衡因子發(fā)生了變化的3個(gè)節(jié)點(diǎn)在同一條直線上，平衡因子為2的節(jié)點(diǎn)在最上邊，其余兩個(gè)依次排在右下方。
//用左單旋的代碼條件
parent->_bf == 2 && cur->_bf == 1;
旋轉(zhuǎn)過程：
- subRL成為parent的右子樹。
- parent成為subR的左子樹。
- subR成為根。
- parent個(gè)subR的平衡因子變成0。
上面所述的旋轉(zhuǎn)就左旋。形象的理解就是將左邊高的一端按下去。
將左單旋的具體實(shí)現(xiàn)封裝在一個(gè)函數(shù)中，在更新平衡因子的過程中調(diào)用左單旋來調(diào)整結(jié)構(gòu)。
右單旋
右單旋的結(jié)構(gòu)只是和左單旋的結(jié)構(gòu)方向不一樣，其他都一樣，本喵就不再畫具象圖推演了，直接上抽象圖：
a，b，c都是高度為h的AVL子樹。
- 在子樹a處插入新節(jié)點(diǎn)，此時(shí)a子樹高度變成了h+1，更新平衡因子，最終導(dǎo)致60的平衡因子變成了-2，需要進(jìn)行旋轉(zhuǎn)。
旋轉(zhuǎn)過程：
- 30的右子樹成員60的左子樹。
- 60成為30的右子樹。
- 30成為根。
- 60和30的平衡因子變成0。
右單旋的規(guī)律：
- 插入新的節(jié)點(diǎn)后，平衡因子發(fā)生了變化的3個(gè)節(jié)點(diǎn)在同一條直線上，平衡因子為-2的節(jié)點(diǎn)在最上邊，其余兩個(gè)依次排在左下方。
//用右單旋的代碼條件
parent->_bf == -2 && cur->_bf == -1;
旋轉(zhuǎn)過程：
- subLR成為parent的左子樹。
- parent成為subL的右子樹。
- subL成為根。
- parent和subL的平衡因子成為0。
形象的理解就是右邊高，將右邊按下去。
右單旋實(shí)現(xiàn)代碼：
//右旋實(shí)現(xiàn)
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
//不為空才會(huì)鏈接
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
//旋轉(zhuǎn)后與舊樹的鏈接
if (ppNode == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
//新根是子樹
else
{
//在左子樹插入的
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
//在右子樹插入的
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
//更新平衡因子
parent->_bf = subL->_bf = 0;
}
只是邏輯和左單旋相反，其他一樣，不再進(jìn)行詳細(xì)講解。
左右雙旋
- 插入新節(jié)點(diǎn)后，左子樹的高度發(fā)生變化，根節(jié)點(diǎn)90的平衡因子最終變成-2。
旋轉(zhuǎn)過程：
- 左子樹先進(jìn)行左單旋：
- 30變成40的左子樹。
- 40變成根節(jié)點(diǎn)。
- 再整體進(jìn)行右單旋：
- 90變成40的右子樹。
- 40變成根節(jié)點(diǎn)。
- 90和40的平衡因子變成0。
在上圖基礎(chǔ)上各個(gè)子樹再增加一層節(jié)點(diǎn)：
插入的節(jié)點(diǎn)為紅色圈，可插入的位置有兩個(gè)。
- 插入新的節(jié)點(diǎn)后，左子樹的高度發(fā)生了變化，根節(jié)點(diǎn)90的平衡因子變成了-2。
旋轉(zhuǎn)過程：
- 先進(jìn)行左單旋：
- 50的左子樹變成30的右子樹(圖中左子樹為空，所以不用管)。
- 30變成50的左子樹。
- 50變成子樹的根。
- 再進(jìn)行右單旋：
- 50的右子樹變成90的左子樹。
- 90變成50的右子樹。
- 50變成根。
- 90的平衡因子變成0，30的平衡因子變成-1，50的平衡因子變成0。
在上圖基礎(chǔ)上再增加一層節(jié)點(diǎn)：
相對(duì)于最開始來說一共增加了兩層，紅色框表示兩層，這兩層右三種情況，如黑色簡單所指。
- 插入新節(jié)點(diǎn)后，左子樹高度發(fā)生了變化，根節(jié)點(diǎn)90的平衡因子變成-2。
旋轉(zhuǎn)過程：
- 先進(jìn)行左單旋：
- 50的左子樹變成30的右子樹。
- 30變成50的左子樹。
- 50變成子樹的根。
- 再進(jìn)行右單旋：
- 50的右子樹變成90的左子樹。
- 90變成50的右子樹。
- 50成為根。
- 30的平衡因子變成-1，90和50的平衡因子變成0。
將上面具象圖畫成抽象圖：
h表示子樹的高度，紫色框表示插入的節(jié)點(diǎn)。
- 插入新節(jié)點(diǎn)后，左子樹的高度發(fā)生變化，根節(jié)點(diǎn)90的平衡因子變成-2。
//用左右雙旋的代碼條件
parent->_bf == -2 && cur->_bf == 1;
旋轉(zhuǎn)過程：
- 先進(jìn)行左單旋：
- 60的左子樹變成30的右子樹。
- 30變成60的左子樹。
- 60成為子樹的根。
- 再進(jìn)行右單旋：
- 60的右子樹成為90的左子樹。
- 90成為60的右子樹。
- 60成為根。
- 60的平衡因子變成0，90的平衡因子變成1，30的平衡因子變成0。
左右雙旋規(guī)律：
- 插入新的節(jié)點(diǎn)后，平衡因子發(fā)生了變化的3個(gè)節(jié)點(diǎn)形成一個(gè)左邊突出的拐，平衡因子為-2的節(jié)點(diǎn)在最上邊，左下方是平衡因子為1的節(jié)點(diǎn)，最后一個(gè)在1節(jié)點(diǎn)的右下方，該節(jié)點(diǎn)的平衡因子可能是-1也可能是1。
平衡因子更新：
雙旋中，旋轉(zhuǎn)很好實(shí)現(xiàn)，直接復(fù)用前面的左單旋和右單旋就可以，難點(diǎn)在于雙旋過后平衡因子的更新。從上面具象圖和抽象圖中看不出一點(diǎn)平衡因子的變化規(guī)律。
換個(gè)角度來看：
- 子樹b在旋轉(zhuǎn)前是60的左子樹，旋轉(zhuǎn)后成為了30的右子樹。
- 子樹c在旋轉(zhuǎn)前是60的右子樹，旋轉(zhuǎn)后成為了90的左子樹。
- 節(jié)點(diǎn)60在旋轉(zhuǎn)前是子樹根，旋轉(zhuǎn)后成了新的根。
一步到位的來看，旋轉(zhuǎn)就是將節(jié)點(diǎn)60的左右子樹分?jǐn)偨o了30個(gè)90，而它自己做了新的根。
- 新插入的節(jié)點(diǎn)如果在子樹b，那么旋轉(zhuǎn)后30的右子樹高度就會(huì)加一，導(dǎo)致30的平衡因子是0，90的平衡因子是1。
- 新插入的節(jié)點(diǎn)如果在子樹c，那么旋轉(zhuǎn)后90的左子樹高度就會(huì)加一，導(dǎo)致90的平衡因子是0，30的平衡因子是-1。
- 新的根節(jié)點(diǎn)60的平衡因子是0。
自己是新增：
- 插入新節(jié)點(diǎn)后，60的平衡因子是0，說明它自己就是新增節(jié)點(diǎn)。
- 此時(shí)旋轉(zhuǎn)過后，平衡因子變化了的3個(gè)節(jié)點(diǎn)的平衡因子都變成了0。
左右雙旋代碼實(shí)現(xiàn)：
重點(diǎn)在于平衡因子的更新，左單旋和右單旋直接復(fù)用前面的代碼即可。
右左雙旋
右左雙旋和左右雙旋邏輯相反，同樣也不再畫具象圖了，直接看抽象圖：
- 插入新節(jié)點(diǎn)后，右子樹的高度發(fā)生了變化，最終根節(jié)點(diǎn)30的平衡因子變成了2。
//右左雙旋的代碼條件
parent->_bf == 2 && cur->_bf == -1;
旋轉(zhuǎn)過程：
- 先進(jìn)行右單旋：
- 60的右子樹變成90的左子樹。
- 90變成60的右子樹。
- 60成為子樹根。
- 再進(jìn)行左單旋：
- 60的左子樹變成30的右子樹。
- 30變成60的左子樹。
- 60成為根。
- 90的平衡因子變成0，30的平衡因子變成-1，60的平衡因子變成0。
右左雙旋規(guī)律：
- 插入新節(jié)點(diǎn)后，變化了平衡因子的3個(gè)節(jié)點(diǎn)，組成一個(gè)右邊退出的拐，平衡因子為2的節(jié)點(diǎn)在最上邊，為-1的節(jié)點(diǎn)在其右下方，剩下一個(gè)在其左下方。
平衡因子更新：
同樣忽略旋轉(zhuǎn)過程，直接對(duì)比最開始和旋轉(zhuǎn)后的結(jié)構(gòu)：
更新方法和左右雙旋的方式一樣，就不再對(duì)圖詳細(xì)解釋了，直接看代碼：
//右左雙旋實(shí)現(xiàn)
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;//在單旋轉(zhuǎn)之前拿到平衡因子
RotateR(subR);//先進(jìn)行右單旋
RotateL(parent);//在進(jìn)行左單旋
//更新平衡因子
//插入subRL的左邊
if (bf == -1)
{
//右單旋后，該分支成為parent的右子樹
//parent的平衡因子為0
parent->_bf = 0;
//左單旋后，另一個(gè)分支成為subR的左子樹
//subR的平衡因子是1
subR->_bf = 1;
}
//插入subRL的右邊
else if (bf == 1)
{
//右單旋后，另一分支成為parent的右子樹
//parent的平衡因子為-1
parent->_bf = -1;
//左單旋后，該分支成為subR的左子樹
//subR的平衡因子為0
subR->_bf = 0;
}
//subRL就是新插入的節(jié)點(diǎn)
else if (bf == 0)
{
//parent和subR的平衡因子都是0
parent->_bf = 0;
subR->_bf = 0;
}
//出錯(cuò)
else
{
//正常情況下不會(huì)進(jìn)入這里
assert(false);
}
//新根的平衡因子為0
subRL->_bf = 0;
}
只是邏輯和左右雙旋相反，就不再詳細(xì)講解了。
注意：
- 旋轉(zhuǎn)過后，平衡因子的更新最好是在封裝的旋轉(zhuǎn)函數(shù)中更新，如果在外面更新會(huì)因?yàn)橹赶蜿P(guān)系混亂而出錯(cuò)。
- 雙旋時(shí)，在左右單旋之前拿到平衡因子，否則會(huì)因?yàn)樾D(zhuǎn)改變平衡因子導(dǎo)致判斷出問題。
??AVL樹的驗(yàn)證
上面已經(jīng)實(shí)現(xiàn)了AVL樹的插入，包括旋轉(zhuǎn)的插入，此時(shí)我們通過插入就能成功建立一顆AVL樹。
寫幾個(gè)測(cè)試用例看看創(chuàng)建是否能夠成功，插入的數(shù)值是鍵值對(duì)，如上圖所示，并且按照升序打印出來。
- 但是這只能證明二叉搜索樹創(chuàng)建成功了，到底是不是AVL樹是無法證明。
為了證明這是AVL樹需要專門寫一個(gè)函數(shù)來檢查一下。
如上圖所示，是專門用來檢測(cè)是否是AVL樹的。
- 通過檢測(cè)，上面的三個(gè)測(cè)試用例都是AVL樹。
這樣拿三個(gè)例子可能不具有代表性，下面我門用隨機(jī)數(shù)來檢測(cè)：
- 插入十萬個(gè)隨機(jī)數(shù)，經(jīng)過多次檢測(cè)運(yùn)行，發(fā)現(xiàn)都是AVL數(shù)，此時(shí)說明我們的AVL數(shù)成功實(shí)現(xiàn)了。
??AVL數(shù)的刪除(了解)
AVL樹也是二叉搜索樹，可按照二叉搜索樹的方式將節(jié)點(diǎn)刪除，然后再更新平衡因子，只不過與刪除不同的是，刪除節(jié)點(diǎn)后的平衡因子更新，最差情況下一直要調(diào)整到根節(jié)點(diǎn)的位置。
情況比較復(fù)雜，有興趣的小伙伴可以自行了解，推薦《數(shù)據(jù)結(jié)構(gòu)-用面向?qū)ο蠓椒ㄅcC++描述》殷人昆版。
??AVL數(shù)的性能
AVL數(shù)是二叉搜索樹，而且左右子樹的高度差不會(huì)超過1，所以它非常接近完全二叉樹，可以保證搜索的時(shí)間復(fù)雜度在O(log2N)，而不會(huì)出現(xiàn)單只的情況。
但是還是存在一定的效率損失問題：
-
插入時(shí)要維護(hù)其絕對(duì)平衡，旋轉(zhuǎn)的次數(shù)比較多，更差的是在刪除時(shí)，
有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。
雖然旋轉(zhuǎn)保證了搜索的時(shí)間復(fù)雜度在O(log2N)，但是又增加了旋轉(zhuǎn)的時(shí)間復(fù)雜度，主要是體現(xiàn)在插入數(shù)據(jù)時(shí)。
也就是說，AVL樹的結(jié)構(gòu)在修改時(shí)會(huì)導(dǎo)致效率低下。文章來源：http://www.zghlxwxcb.cn/news/detail-417832.html
??總結(jié)
AVL樹是在二叉搜索樹的基礎(chǔ)上增加左右子樹高度不超過1的限制，但是在修改結(jié)構(gòu)的時(shí)候又因?yàn)樾D(zhuǎn)導(dǎo)致了效率降低，后面的紅黑樹就克服了這個(gè)問題，下篇文章見。文章來源地址http://www.zghlxwxcb.cn/news/detail-417832.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】AVL樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu) C++] AVL樹的模擬實(shí)現(xiàn)](https://imgs.yssmx.com/Uploads/2024/02/777301-1.png)
