圖解AVL樹數(shù)據(jù)結(jié)構(gòu)輸入與輸出及實(shí)現(xiàn)示例
AVL樹(平衡二叉樹)：
AVL樹本質(zhì)上是一顆二叉查找樹，但是它又具有以下特點(diǎn)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一，所以它也被稱為平衡二叉樹。下面是平衡二叉樹和非平衡二叉樹對(duì)比的例圖：
平衡因子(bf)：結(jié)點(diǎn)的左子樹的深度減去右子樹的深度，那么顯然-1<=bf<=1;
AVL樹的作用：
我們知道，對(duì)于一般的二叉搜索樹（Binary Search Tree），其期望高度（即為一棵平衡樹時(shí)）為log2n，其各操作的時(shí)間復(fù)雜度（O(log2n)）同時(shí)也由此而決定。但是，在某些極端的情況下（如在插入的序列是有序的時(shí)），二叉搜索樹將退化成近似鏈或鏈，此時(shí)，其操作的時(shí)間復(fù)雜度將退化成線性的，即O(n)。我們可以通過隨機(jī)化建立二叉搜索樹來盡量的避免這種情況，但是在進(jìn)行了多次的操作之后，由于在刪除時(shí)，我們總是選擇將待刪除節(jié)點(diǎn)的后繼代替它本身，這樣就會(huì)造成總是右邊的節(jié)點(diǎn)數(shù)目減少，以至于樹向左偏沉。這同時(shí)也會(huì)造成樹的平衡性受到破壞，提高它的操作的時(shí)間復(fù)雜度。
例如：我們按順序?qū)⒁唤M數(shù)據(jù)1,2,3,4,5,6分別插入到一顆空二叉查找樹和AVL樹中，插入的結(jié)果如下圖：
由上圖可知，同樣的結(jié)點(diǎn)，由于插入方式不同導(dǎo)致樹的高度也有所不同。特別是在帶插入結(jié)點(diǎn)個(gè)數(shù)很多且正序的情況下，會(huì)導(dǎo)致二叉樹的高度是O(N)，而AVL樹就不會(huì)出現(xiàn)這種情況，樹的高度始終是O(lgN).高度越小，對(duì)樹的一些基本操作的時(shí)間復(fù)雜度就會(huì)越小。這也就是我們引入AVL樹的原因
AVL樹的基本操作：
AVL樹的操作基本和二叉查找樹一樣，這里我們關(guān)注的是兩個(gè)變化很大的操作：插入和刪除！
我們知道，AVL樹不僅是一顆二叉查找樹，它還有其他的性質(zhì)。如果我們按照一般的二叉查找樹的插入方式可能會(huì)破壞AVL樹的平衡性。同理，在刪除的時(shí)候也有可能會(huì)破壞樹的平衡性，所以我們要做一些特殊的處理，包括：?jiǎn)涡D(zhuǎn)和雙旋轉(zhuǎn)！
AVL樹的插入，單旋轉(zhuǎn)的第一種情況---右旋：
由上圖可知：在插入之前樹是一顆AVL樹，而插入之后結(jié)點(diǎn)T的左右子樹高度差的絕對(duì)值不再 < 1,此時(shí)AVL樹的平衡性被破壞，我們要對(duì)其進(jìn)行旋轉(zhuǎn)。由上圖可知我們是在結(jié)點(diǎn)T的左結(jié)點(diǎn)的左子樹上做了插入元素的操作，我們稱這種情況為左左情況，我們應(yīng)該進(jìn)行右旋轉(zhuǎn)(只需旋轉(zhuǎn)一次，故是單旋轉(zhuǎn))。具體旋轉(zhuǎn)步驟是：
T向右旋轉(zhuǎn)成為L(zhǎng)的右結(jié)點(diǎn)，同時(shí)，Y放到T的左孩子上。這樣即可得到一顆新的AVL樹，旋轉(zhuǎn)過程圖如下：
左左情況的右旋舉例：
AVL樹的插入，單旋轉(zhuǎn)的第二種情況---左旋：
由上圖可知：在插入之前樹是一顆AVL樹，而插入之后結(jié)點(diǎn)T的左右子樹高度差的絕對(duì)值不再 < 1,此時(shí)AVL樹的平衡性被破壞，我們要對(duì)其進(jìn)行旋轉(zhuǎn)。由上圖可知我們是在結(jié)點(diǎn)T的右結(jié)點(diǎn)的右子樹上做了插入元素的操作，我們稱這種情況為右右情況，我們應(yīng)該進(jìn)行左旋轉(zhuǎn)(只需旋轉(zhuǎn)一次，故事單旋轉(zhuǎn))。具體旋轉(zhuǎn)步驟是：
T向右旋轉(zhuǎn)成為R的左結(jié)點(diǎn)，同時(shí)，Y放到T的左孩子上。這樣即可得到一顆新的AVL樹，旋轉(zhuǎn)過程圖如下：
右右情況的左旋舉例：
以上就是插入操作時(shí)的單旋轉(zhuǎn)情況！我們要注意的是：誰是T誰是L，誰是R還有誰是X,Y,Z!T始終是開始不平衡的左右子樹的根節(jié)點(diǎn)。顯然L是T的左結(jié)點(diǎn)，R是T的右節(jié)點(diǎn)。X、Y、Y是子樹當(dāng)然也可以為NULL.NULL歸NULL，但不能破壞插入時(shí)我上面所說的左左情況或者右右情況。
AVL樹的插入，雙旋轉(zhuǎn)的第一種情況---左右(先左后右)旋：
由上圖可知，我們?cè)赥結(jié)點(diǎn)的左結(jié)點(diǎn)的右子樹上插入一個(gè)元素時(shí)，會(huì)使得根為T的樹的左右子樹高度差的絕對(duì)值不再 < 1，如果只是進(jìn)行簡(jiǎn)單的右旋，得到的樹仍然是不平衡的。我們應(yīng)該按照如下圖所示進(jìn)行二次旋轉(zhuǎn)：
左右情況的左右旋轉(zhuǎn)實(shí)例：
AVL樹的插入，雙旋轉(zhuǎn)的第二種情況---右左(先右后左)旋：
由上圖可知，我們?cè)赥結(jié)點(diǎn)的右結(jié)點(diǎn)的左子樹上插入一個(gè)元素時(shí)，會(huì)使得根為T的樹的左右子樹高度差的絕對(duì)值不再 < 1，如果只是進(jìn)行簡(jiǎn)單的左旋，得到的樹仍然是不平衡的。我們應(yīng)該按照如下圖所示進(jìn)行二次旋轉(zhuǎn)：
右左情況的右左旋轉(zhuǎn)實(shí)例：
AVL樹的插入代碼實(shí)現(xiàn):(僅供參考)
懂了以上單旋轉(zhuǎn)和雙旋轉(zhuǎn)的原理之后，那么代碼寫起來也就比較簡(jiǎn)單了，以下是我寫的代碼，如果有錯(cuò)還望大家不吝指正。（參考數(shù)據(jù)結(jié)構(gòu)與算法分析）
#include <iostream>
using namespace std;
#define DataType int
/*
定義AVL樹的結(jié)構(gòu)體，鏈?zhǔn)?
*/
typedef struct AvlNode{
DataType data;
AvlNode * m_pLeft;
AvlNode * m_pRight;
int height;
}*AvlTree,*Position,AvlNode;
//求兩個(gè)數(shù)的最大值
int Max(int a,int b)
{
return a>b?a:b;
}
//求樹的高度
int Height( AvlTree T)
{
if(NULL == T)
return -1;
else
return T->height;
}
//單旋轉(zhuǎn)右旋
AvlTree singleRotateWithRight(AvlTree T)
{
AvlTree L = T->m_pLeft;
T->m_pLeft = L->m_pRight;
L->m_pRight = T;
T->height = Max( Height(T->m_pLeft),Height(T->m_pRight) ) + 1;
L->height = Max( Height(L->m_pLeft),Height(L->m_pRight) ) + 1;
return L; //此時(shí)L成為根節(jié)點(diǎn)了（可參考AVL的插入的左左情況的右旋圖）
}
//單旋轉(zhuǎn)左旋
AvlTree singleRotateWithLeft(AvlTree T)
{
AvlTree R = T->m_pRight;
T->m_pRight = R->m_pLeft;
R->m_pLeft = T;
T->height = Max( Height(T->m_pLeft),Height(T->m_pRight) ) + 1;
R->height = Max( Height(R->m_pLeft),Height(R->m_pRight) ) + 1;
return R; //此時(shí)R成為根節(jié)點(diǎn)了（可參考AVL的插入的左左情況的左旋圖）
}
//雙旋轉(zhuǎn)，先左后右
AvlTree doubleRotateWithLeft(AvlTree T) //先左后右
{
T->m_pLeft = singleRotateWithLeft(T->m_pLeft);
return singleRotateWithRight(T);
}
//雙旋轉(zhuǎn)，先右后左
AvlTree doubleRotateWithRight(AvlTree T) //先右后左
{
T->m_pRight = singleRotateWithRight(T->m_pRight);
return singleRotateWithLeft(T);
}
AvlTree AvlTreeInsert(AvlTree T, DataType x)
{
if(T == NULL) //如果樹為空
{
T = (AvlNode *)malloc(sizeof(struct AvlNode));
if(T)
{
T->data = x;
T->m_pLeft = NULL;
T->m_pRight = NULL;
T->height = 0;
}
else
{
cout << "空間不夠" << endl;
exit(0);
}
}
else if( x < T->data) //如果插入到T結(jié)點(diǎn)的左子樹上
{
T->m_pLeft = AvlTreeInsert(T->m_pLeft,x); //先插入，后旋轉(zhuǎn)
if(Height(T->m_pLeft) - Height(T->m_pRight) == 2) //只有可能是這個(gè)
{
if(x < T->m_pLeft->data) //左左情況，只需要右旋轉(zhuǎn)
{
T = singleRotateWithRight( T );
}
else //左右情況，雙旋轉(zhuǎn),先左
{
T = doubleRotateWithLeft( T );
}
}
}
else if( x > T->data )
{
T->m_pRight = AvlTreeInsert(T->m_pRight,x);
if(Height(T->m_pRight) - Height(T->m_pLeft) == 2)
{
if(x > T->m_pRight->data) //右右情況，進(jìn)行左旋
{
T = singleRotateWithLeft( T );
}
else //左右情況，雙旋轉(zhuǎn),先右
{
T = doubleRotateWithRight( T );
}
}
}
//如果這個(gè)數(shù)已經(jīng)存在，那么不進(jìn)行插入
T->height = Max(Height(T->m_pLeft),Height(T->m_pRight)) + 1;
return T;
}
//遞歸實(shí)現(xiàn)中序遍歷
void inOrderVisitUseRecur(const AvlTree pCurrent)
{
if(pCurrent)
{
inOrderVisitUseRecur(pCurrent->m_pLeft);
cout << pCurrent->data << " ";
if(pCurrent->m_pLeft)
cout << " leftChild: "<<pCurrent->m_pLeft->data;
else
cout << " leftChild: "<<"NULL" ;
if(pCurrent->m_pRight)
cout << " rightChild: "<<pCurrent->m_pRight->data;
else
cout << " rightChild: "<< "NULL";
cout << endl;
inOrderVisitUseRecur(pCurrent->m_pRight);
}
}
int main()
{
AvlTree root = NULL;
root = AvlTreeInsert(root,1);
root = AvlTreeInsert(root,2);
root = AvlTreeInsert(root,3);
root = AvlTreeInsert(root,4);
root = AvlTreeInsert(root,5);
root = AvlTreeInsert(root,6);
root = AvlTreeInsert(root,7);
root = AvlTreeInsert(root,8);
root = AvlTreeInsert(root,9);
root = AvlTreeInsert(root,10);
root = AvlTreeInsert(root,11);
root = AvlTreeInsert(root,12);
root = AvlTreeInsert(root,13);
root = AvlTreeInsert(root,14);
root = AvlTreeInsert(root,15);
inOrderVisitUseRecur(root);
return 0;
}以上就是圖解AVL樹數(shù)據(jù)結(jié)構(gòu)輸入與輸出及實(shí)現(xiàn)示例的詳細(xì)內(nèi)容，更多關(guān)于AVL樹數(shù)據(jù)結(jié)構(gòu)圖解的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
記逆向小白的第一次vbsedit 9爆破及內(nèi)存補(bǔ)丁制作過程
這篇文章主要介紹了記逆向小白的第一次vbsedit 9爆破及內(nèi)存補(bǔ)丁制作過程,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
C++中strcpy函數(shù)的實(shí)現(xiàn)
strncpy這個(gè)可以指定拷貝字符的長(zhǎng)度，指定源地址，目標(biāo)地址，還有需要拷貝的字符的長(zhǎng)度； strcpy只能傳入兩個(gè)參數(shù)，只指定拷貝的起始地址跟目標(biāo)地址，然后整體拷貝；2015-10-10
C語(yǔ)言+MySQL實(shí)現(xiàn)推箱子游戲
經(jīng)典的推箱子是一個(gè)來自日本的古老游戲，目的是在訓(xùn)練你的邏輯思考能力。本文將通過C語(yǔ)言和MySQL實(shí)現(xiàn)推箱子這一經(jīng)典游戲，感興趣的可以了解一下2022-02-02
C++聲明extern變量和extern函數(shù)的用法
extern關(guān)鍵字可以用來聲明變量和函數(shù)作為外部變量或者外部函數(shù)供其它文件使用,所以本文給大家介紹了C++聲明extern變量和extern函數(shù)的用法,文中有相關(guān)的代碼示例供大家參考,需要的朋友可以參考下2024-11-11
C語(yǔ)言中數(shù)組的一些基本知識(shí)小結(jié)
這篇文章主要介紹了C語(yǔ)言中數(shù)組的一些基本知識(shí)小結(jié),其中重點(diǎn)是對(duì)于數(shù)組的內(nèi)存分配相關(guān)方面的知識(shí)整理,需要的朋友可以參考下2016-04-04
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言代碼實(shí)現(xiàn)井字棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08![C 語(yǔ)言基礎(chǔ)教程(我的C之旅開始了)[五]](http://img.jbzj.com/images/xgimg/bcimg6.png)
C 語(yǔ)言基礎(chǔ)教程(我的C之旅開始了)[五]
C 語(yǔ)言基礎(chǔ)教程(我的C之旅開始了)[五]...2007-02-02
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單掃雷小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
這篇文章主要介紹了C 讀取ini文件的實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家實(shí)現(xiàn)這樣的功能，需要的朋友可以參考下2017-10-10
C語(yǔ)言用棧實(shí)現(xiàn)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的方法示例
這篇文章主要介紹了C語(yǔ)言用棧實(shí)現(xiàn)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的方法,結(jié)合實(shí)例形式分析了C語(yǔ)言棧的定義及進(jìn)制轉(zhuǎn)換使用技巧,需要的朋友可以參考下2017-06-06