文章目錄

• 前言
• 一.定義
• 二.基本操作
• • 1.查找，
  • 2.插入(如何調(diào)整)
  • • 如何調(diào)整
    • 代碼實(shí)現(xiàn)插入

前言

首先我們來(lái)思考一下一個(gè)普通二叉樹(shù)保存數(shù)據(jù)，如果想查找一個(gè)數(shù)據(jù)，由于普通二叉樹(shù)保存數(shù)據(jù)是隨機(jī)的，要找到數(shù)據(jù)的時(shí)間復(fù)雜度為O(n)。后面為了方便
，我們又學(xué)習(xí)二叉搜索樹(shù)，它的定義是將比根節(jié)點(diǎn)小的數(shù)放左邊，比根節(jié)點(diǎn)大的數(shù)放右邊，并且每一課子樹(shù)都是二叉搜索樹(shù)這樣使得數(shù)據(jù)在樹(shù)上存儲(chǔ)有一定
的規(guī)律，在一定情況下查找起來(lái)很方便。但是，二叉搜索數(shù)當(dāng)給出數(shù)據(jù)的順序不同時(shí)，二叉搜索樹(shù)也會(huì)不同。比如如果給出的序列為{1，2，3，4，5}或
{3，2，1，4，5}兩顆二叉搜索樹(shù)會(huì)截然不同，查找效率也會(huì)不同。
我們知道一顆樹(shù)的查找效率與樹(shù)的高度有關(guān)，最好的樹(shù)結(jié)構(gòu)當(dāng)然是滿(mǎn)二叉樹(shù)或者是完全二叉樹(shù)，我們稱(chēng)這種樹(shù)是平衡的。由我們知道二叉搜索樹(shù)在一定情況下可以達(dá)到很好的查找效率。但是，通常情況二叉搜索樹(shù)的結(jié)點(diǎn)插入順序并不能事先確定，動(dòng)態(tài)查找(查找時(shí)同時(shí)進(jìn)行刪除與插入操作)的時(shí)候總還是會(huì)改變數(shù)的結(jié)構(gòu)，不能做到平衡。所以，我們就需要考慮如何保證既能完成動(dòng)態(tài)查找，又能保持一個(gè)較完美樹(shù)結(jié)構(gòu)的二叉搜索樹(shù)。這樣我們就有兩個(gè)問(wèn)題需要考慮：一個(gè)是標(biāo)準(zhǔn)，什么樣的樹(shù)才是一顆樹(shù)結(jié)構(gòu)好的樹(shù)，第二是平衡化處理，怎樣使其達(dá)到平衡。

一.定義

平衡二叉樹(shù)又稱(chēng)AVL樹(shù)(由發(fā)明它的兩位數(shù)學(xué)家名字命名)，它仍然是一顆二叉搜索樹(shù)，所以具備二叉搜索樹(shù)的所有性質(zhì)，只是加上了"平衡"的限制。 平衡二叉樹(shù)要不是一顆空樹(shù)，要不是具備以下條件的非空二叉搜索樹(shù)： 1. 左右子樹(shù)高度差的絕對(duì)值不能超過(guò)1(平衡因子，相當(dāng)于一種標(biāo)準(zhǔn))。 2. 左右子樹(shù)仍然是一顆平衡二叉樹(shù)。 有了平衡因子的定義，我們就可以找出不平衡的樹(shù)，然后再對(duì)其進(jìn)行平衡化處理，處理的具體內(nèi)容分如下。處理完后使樹(shù)的高度能保持在O(logn)級(jí)別，使得 查找操作的時(shí)間復(fù)雜度為O(logn).

圖1圖2圓上為平衡因子的值，明顯圖1不是平衡二叉樹(shù)，有提個(gè)點(diǎn)的平衡因子超過(guò)了1。圖2是平衡二叉樹(shù)。

二.基本操作

1.查找，

由于平衡二叉樹(shù)仍是一顆二叉搜索樹(shù)，其查找操作并不會(huì)改變平衡因子，所以與二叉搜索樹(shù)的操作相同。可見(jiàn)博客：二叉搜索樹(shù)的查找。

2.插入(如何調(diào)整)

如何調(diào)整

假設(shè)這里有一顆平衡二叉樹(shù)：(上方代表平衡因子)

LL型
當(dāng)要往D的左子樹(shù)或者右子樹(shù)插入結(jié)點(diǎn)時(shí)，此時(shí)破壞了原來(lái)平衡二叉樹(shù)的平衡結(jié)構(gòu)，如圖：此時(shí)A結(jié)點(diǎn)的平衡因子超過(guò)了1，我們稱(chēng)A結(jié)點(diǎn)為發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)，六角星為產(chǎn)生問(wèn)題結(jié)點(diǎn)。

此時(shí)，我們需要看發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)與產(chǎn)生問(wèn)題結(jié)點(diǎn)路徑上，從發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)開(kāi)始的連續(xù)三個(gè)結(jié)點(diǎn)。入上圖的A->B->D。我們發(fā)現(xiàn)這三個(gè)結(jié)點(diǎn)都在發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)A左子樹(shù)的左子樹(shù)上，我們稱(chēng)這種不平衡狀態(tài)為L(zhǎng)L型(向左傾斜)不平衡。
如何調(diào)整，LL型不平衡的調(diào)整策略主要將這三個(gè)結(jié)點(diǎn)(A,B,D)順時(shí)針旋轉(zhuǎn)，并且仍然要是一顆二叉搜索樹(shù)。
由于二叉搜索樹(shù)的性質(zhì)：

將B結(jié)點(diǎn)的右子樹(shù)成為A的左子樹(shù)。(B的左子樹(shù)比B大，比A小)

讓A成為B的右子樹(shù)(A比B大)

將根節(jié)點(diǎn)設(shè)為B

顯然只有只有從根節(jié)點(diǎn)到插入結(jié)點(diǎn)路徑上的結(jié)點(diǎn)才會(huì)發(fā)生平衡因子的變化，因此只需要對(duì)這條路徑上的失衡的結(jié)點(diǎn)進(jìn)行調(diào)整，并且只需要把最靠近插入節(jié)點(diǎn)的失衡節(jié)點(diǎn)調(diào)整到正常，路徑上的所有結(jié)點(diǎn)都會(huì)平衡。所以發(fā)現(xiàn)問(wèn)題的結(jié)點(diǎn)不一定是根節(jié)點(diǎn)
注意：看的是發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)到產(chǎn)生問(wèn)題結(jié)點(diǎn)路徑上，從發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)開(kāi)始的連續(xù)三個(gè)結(jié)點(diǎn)的方向，確定是什么型。并且主要也是調(diào)整這三個(gè)結(jié)點(diǎn)。
代碼如下：

void SigelleftCir(Bactree **tree){//LL旋轉(zhuǎn)Bactree *temp = NULL;temp = (*tree)->left;(*tree)->left = temp->right;temp->right = (*tree);(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;//調(diào)整后要保持每個(gè)結(jié)點(diǎn)高度正確。temp->hight = (GetHight(temp->left) > GetHight(temp->right) ? GetHight(temp->left) : GetHight(temp->right)) + 1;(*tree) = temp; //要賦值給(*tree),不然temp才是正確的樹(shù)}

RR型
RR型的處理方法與LL型類(lèi)似，如圖：

產(chǎn)生問(wèn)題結(jié)點(diǎn)為六角星結(jié)點(diǎn)(插入E的左子樹(shù)或者右子樹(shù))，發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)為A結(jié)點(diǎn)。路徑上從發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)開(kāi)始的連續(xù)三個(gè)結(jié)點(diǎn)為(A,C,E)結(jié)點(diǎn)，分別在發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)右子樹(shù)的右子樹(shù)上，所以為RR型(向右傾斜)不平衡。
調(diào)整方式：主要將這三個(gè)結(jié)點(diǎn)(A,C,E)逆時(shí)針旋轉(zhuǎn)，并且仍然要是一顆二叉搜索樹(shù)。

將C結(jié)點(diǎn)的左子樹(shù)成為A的右子樹(shù)。

讓A成為C的左子樹(shù)

將根節(jié)點(diǎn)設(shè)為C

void SigelrightCir(Bactree **tree){//RR旋轉(zhuǎn)，與LL一樣Bactree *temp = NULL;temp = (*tree)->right;(*tree)->right = temp->left;temp->left = (*tree);(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;temp->hight = (GetHight(temp->left) > GetHight(temp->right) ? GetHight(temp->left) : GetHight(temp->right)) + 1;(*tree) = temp;

LR型

產(chǎn)生問(wèn)題結(jié)點(diǎn)為六角星(插入E的左子樹(shù)或者右子樹(shù))，發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)為A結(jié)點(diǎn)。路徑上從發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)開(kāi)始的連續(xù)三個(gè)結(jié)點(diǎn)為(A,B,E)結(jié)點(diǎn)，分別在發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)左子樹(shù)的右子樹(shù)上，所以為L(zhǎng)R型不平衡。
調(diào)整方式：“左-右雙旋”，主要先將B結(jié)點(diǎn)作為根節(jié)點(diǎn)逆時(shí)針旋轉(zhuǎn)(左旋)，再以A結(jié)點(diǎn)作為根節(jié)點(diǎn)順時(shí)針旋轉(zhuǎn)(右旋)。(畫(huà)圖以白色六角星作為插入)

代碼實(shí)現(xiàn)調(diào)整LR型就很簡(jiǎn)單了，先右旋，再左旋

void LeftrightCir(Bactree **tree){//LR旋轉(zhuǎn)SigelrightCir(&((*tree)->left));SigelleftCir(tree); }

RL型

產(chǎn)生問(wèn)題結(jié)點(diǎn)為六角星(插入D的左子樹(shù)或者右子樹(shù))，發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)為A結(jié)點(diǎn)。路徑上從發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)開(kāi)始的連續(xù)三個(gè)結(jié)點(diǎn)為(A,C,D)結(jié)點(diǎn)，分別在發(fā)現(xiàn)問(wèn)題結(jié)點(diǎn)右子樹(shù)的左子樹(shù)上，所以為RL型不平衡。
調(diào)整方式："右-左雙旋"主要先將C結(jié)點(diǎn)作為根節(jié)點(diǎn)順時(shí)針旋轉(zhuǎn)(右旋)，再以A結(jié)點(diǎn)作為根節(jié)點(diǎn)逆時(shí)針旋轉(zhuǎn)(左旋)。(畫(huà)圖以白色六角星作為插入)

代碼實(shí)現(xiàn)調(diào)整RL型就很簡(jiǎn)單了，先左旋，再右旋

void RightleftCir(Bactree **tree){//RL旋轉(zhuǎn)SigelleftCir(&((*tree)->right));SigelrightCir(tree); }

代碼實(shí)現(xiàn)插入

#include<stdio.h> #include<stdlib.h> #include<Windows.h> #pragma warning(disable:4996)typedef int Elementtype; typedef struct Balacetree{//二叉樹(shù)信息Elementtype val;int hight;struct Balacetree *left;struct Balacetree *right;}Bactree;Bactree *TreeNodeCreate(Elementtype x){//創(chuàng)建樹(shù)節(jié)點(diǎn)Bactree *tree = (Bactree *)malloc(sizeof(Bactree));tree->val = x;tree->hight = 1;tree->left = NULL;tree->right = NULL;return tree; }int GetHight(Bactree *tree){//求樹(shù)高度if (!tree){return 0;}int H;int LH;int RH;LH = GetHight(tree->left);RH = GetHight(tree->right);H = LH > RH ? LH : RH;return H + 1; } void SigelleftCir(Bactree **tree){//LL旋轉(zhuǎn)Bactree *temp = NULL;temp = (*tree)->left;(*tree)->left = temp->right;temp->right = (*tree);(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;//調(diào)整后要保持每個(gè)結(jié)點(diǎn)高度正確。temp->hight = (GetHight(temp->left) > GetHight(temp->right) ? GetHight(temp->left) : GetHight(temp->right)) + 1;(*tree) = temp; //要賦值給(*tree),不然temp才是正確的數(shù)} void SigelrightCir(Bactree **tree){//RR旋轉(zhuǎn)，與LL一樣Bactree *temp = NULL;temp = (*tree)->right;(*tree)->right = temp->left;temp->left = (*tree);(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;temp->hight = (GetHight(temp->left) > GetHight(temp->right) ? GetHight(temp->left) : GetHight(temp->right)) + 1;(*tree) = temp;}void LeftrightCir(Bactree **tree){//LR旋轉(zhuǎn)SigelrightCir(&((*tree)->left));SigelleftCir(tree); } void RightleftCir(Bactree **tree){//RL旋轉(zhuǎn)SigelleftCir(&((*tree)->right));SigelrightCir(tree); }Bactree *BalaceTreePush(Bactree **tree, Elementtype x){if (!(*tree)){ //插入結(jié)點(diǎn)*tree=TreeNodeCreate(x);return *tree;}if ((*tree)->val > x){ //x小的插入左邊(*tree)->left = BalaceTreePush(&((*tree)->left), x);//往右邊找，將結(jié)點(diǎn)返回給左指針//為什么放循環(huán)里，放循環(huán)里確認(rèn)了一個(gè)方向，是左邊if (GetHight((*tree)->left) - GetHight((*tree)->right) >= 2){//平衡因子if ((*tree)->left->val > x){//確認(rèn)了第二個(gè)方向 左邊SigelleftCir(tree);//LL}else{//右邊LeftrightCir(tree);//LR}}}else{(*tree)->right = BalaceTreePush(&((*tree)->right), x);if (GetHight((*tree)->left) - GetHight((*tree)->right) <= -2){//注意是-2if ((*tree)->right->val < x){SigelrightCir(tree);}else{RightleftCir(tree);}}}(*tree)->hight = (GetHight((*tree)->left) > GetHight((*tree)->right) ? GetHight((*tree)->left) : GetHight((*tree)->right)) + 1;//更新高度return *tree;}void Print(Bactree *tree){if (tree){Print(tree->left);printf("%d ", tree->val);Print(tree->right);} }int main(){Bactree *T = NULL;BalaceTreePush(&T, -10);BalaceTreePush(&T, -3);BalaceTreePush(&T, 0);BalaceTreePush(&T, 5);BalaceTreePush(&T, 9);BalaceTreePush(&T, 10);Print(T);system("pause");return 0; }

總結(jié)

以上是生活随笔為你收集整理的数据结构——平衡二叉树(AVL树)之插入的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。