不同結(jié)構(gòu)的二叉查找樹，查找效率有很大的不同（單支樹結(jié)構(gòu)的查找效率退化成了順序查找）。如何解決這個問題呢？關(guān)鍵在于如何最大限度的減小樹的深度。正是基于這個想法，平衡二叉樹出現(xiàn)了。

平衡二叉樹的定義 （AVL—— 發(fā)明者為Adel’son-Vel’skii 和 Landis）

平衡二叉查找樹，又稱 AVL樹。 它除了具備二叉查找樹的基本特征之外，還具有一個非常重要的特點(diǎn)：它 的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值（平衡因子 ） 不超過1。 也就是說AVL樹每個節(jié)點(diǎn)的平衡因子只可能是-1、0和1（左子樹高度減去右子樹高度）。

那么如何是二叉查找樹在添加數(shù)據(jù)的同時保持平衡呢？基本思想就是：當(dāng)在二叉排序樹中插入一個節(jié)點(diǎn)時，首先檢查是否因插入而破壞了平衡，若 破壞，則找出其中的最小不平衡二叉樹，在保持二叉排序樹特性的情況下，調(diào)整最小不平衡子樹中節(jié)點(diǎn)之間的關(guān)系，以達(dá) 到新的平衡。所謂最小不平衡子樹 指離插入節(jié)點(diǎn)最近且以平衡因子的絕對值大于1的節(jié)點(diǎn)作為根的子樹。

平衡二叉樹的操作

• 查找操作
  平衡二叉樹的查找基本與二叉查找樹相同。

• 插入操作
  在平衡二叉樹中插入結(jié)點(diǎn)與二叉查找樹最大的不同在于要隨時保證插入后整棵二叉樹是平衡的。那么調(diào)整不平衡樹的基本方法就是： 旋轉(zhuǎn) 。 下面我們歸納一下平衡旋轉(zhuǎn)的4種情況：
  這里我們把必須重新平衡的節(jié)點(diǎn)叫做A。
  平衡因子：左子樹的深度減去右子樹的深度。
  相關(guān)旋轉(zhuǎn)圖示見 嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》（C語言版）P235

• 單旋轉(zhuǎn)–向右旋轉(zhuǎn)平衡處理–在A的左兒子的左子樹進(jìn)行一次插入。此時平衡因子變?yōu)?。
• 單旋轉(zhuǎn)–向左旋轉(zhuǎn)平衡處理–在A的右兒子的右子樹進(jìn)行一次插入操作。此時平衡因子變?yōu)?2.
• 雙旋轉(zhuǎn)–先右后左旋轉(zhuǎn)平衡處理–在A的左兒子的右子樹進(jìn)行一次插入操作。此時平衡因子變?yōu)?.
• 雙旋轉(zhuǎn)–先左后右平衡處理–在A的右兒子的左子樹進(jìn)行一次插入操作。此時平衡因子變?yōu)?2.

代碼實(shí)現(xiàn)：

/***AVL 樹 插入新節(jié)點(diǎn) 的實(shí)現(xiàn)*/struct AVLNode{int val;AVLNode* left;AVLNode* right;int height;AVLNode(const int& value, AVLNode* lt, AVLNode* rt, int h = 0):val(value), left(lt),right(rt),height(h){} };/***Return thr height of node t ot -1 if NULL* / int height(AVLNode* t) const {return t == NULL ? -1 : t->height; }void insert(const int& x, AVLNode* & t) {if(t == NULL) //empty Treet = new AVLNode(x, NULL, NULL);else if(x < t->val) //插入到左兒子{//insert into left subtreeinsert(x, t->left);if(height(t->left) - height(t->right) == 2){if(x < t->left->val) //插入到了左兒子的左子樹中 ，向右單旋轉(zhuǎn)rotateWithLeftChild(t);else //插入到左兒子的右子樹， 先左后右雙旋轉(zhuǎn)doubleRotateWithLeftChild(t);}}else if(x > t->val) //插入到右兒子{insert(x, t->right);if(height(t->right) - height(t->left) == 2){if(x > t->right->val)rotateWithRightChild(t); //插入到右兒子的右子樹， 向左單旋轉(zhuǎn)else if(x < t->right->val)doubleRotateWithRightChild(t); //插入到右兒子的左子樹， 先右后左雙旋轉(zhuǎn)}}else {//待插入節(jié)點(diǎn)已經(jīng)存在， do nothing}t->height = max(height(t->left), height(t->right)) + 1; }//向右單旋轉(zhuǎn) void rotateWithLeftChild( AVLNode* & root) {AVLNode *newRoot = root->left;root->left = newRoot->right;newRoot->right = root;root->height = max(height(root->left), height(root->right)) + 1;newRoot->height = max(height(newRoot->left), root->height) + 1;root = newRoot; //root 指向新的root節(jié)點(diǎn) }//向左單旋轉(zhuǎn) void rotateWithRightChild(AVLNode* & root) {AVLNode* newRoot = root->right;root->right = newRoot->left;newRoot->left = root;root->height = max(height(root->left), height(root->right)) + 1;newRoot->height = max(height(newRoot->right), root->height) + 1;root = newRoot; }//先左后右雙旋轉(zhuǎn) void doubleRotateWithLeftChild(AVLNode* & root) {rotateWithRightChild(root->left); //先對root的左子樹進(jìn)行向左單旋轉(zhuǎn)rotateWithLeftChild(root); //然后對root進(jìn)行向右單旋轉(zhuǎn) }//先右后左雙旋轉(zhuǎn) void doubleRotateWithRightChild(AVLNode* & root) {rotateWithLeftChild(root->right); //先對root的右子樹進(jìn)行向右單旋轉(zhuǎn)rotateWithRightChild(root); //然后對root進(jìn)行向左單旋轉(zhuǎn) }

平衡二叉樹性能分析

平衡二叉樹的性能優(yōu)勢：
很顯然，平衡二叉樹的優(yōu)勢在于不會出現(xiàn)普通二叉查找樹的最差情況。其查找的時間復(fù)雜度為O(logN)。
在平衡樹上進(jìn)行查找的過程和二叉排序樹相同，因此，在查找的過程中和給定值進(jìn)行比較的關(guān)鍵字個數(shù)不超過樹的深度。
那么，
含有n個關(guān)鍵字的平衡樹的最大深度是多少呢？
為了解答這個問題，
可以借助 深度為h的平衡樹所具有的最少節(jié)點(diǎn)數(shù)的計(jì)算公式:
最少節(jié)點(diǎn)數(shù)

S(h) = S(h - 1) + S(h - 2) + 1 其中，h = 0, S(h) = 1; h = 1, S(h) = 2.

得到h的最大值。

平衡二叉樹的缺陷：
(1) 很遺憾的是，為了保證高度平衡，動態(tài)插入和刪除的代價也隨之增加。因此，我們在下一專題中講講《紅黑樹》 這種更加高效的查找結(jié)構(gòu)。

(2) 所有二叉查找樹結(jié)構(gòu)的查找代價都與樹高是緊密相關(guān)的，能否通過減少樹高來進(jìn)一步降低查找代價呢。我們可以通過多路查找樹的結(jié)構(gòu)來做到這一點(diǎn)，在后面專題中我們將通過《多路查找樹/B-樹/B+樹 》來介紹。

(3) 在大數(shù)據(jù)量查找環(huán)境下(比如說系統(tǒng)磁盤里的文件目錄，數(shù)據(jù)庫中的記錄查詢 等)，所有的二叉查找樹結(jié)構(gòu)(BST、AVL、RBT)都不合適。如此大規(guī)模的數(shù)據(jù)量（幾G數(shù)據(jù)），全部組織成平衡二叉樹放在內(nèi)存中是不可能做到的。那么把這棵樹放在磁盤中吧。問題就來了：假如構(gòu)造的平衡二叉樹深度有1W層。那么從根節(jié)點(diǎn)出發(fā)到葉子節(jié)點(diǎn)很可能就需要1W次的硬盤IO讀寫。大家都知道，硬盤的機(jī)械部件讀寫數(shù)據(jù)的速度遠(yuǎn)遠(yuǎn)趕不上純電子媒體的內(nèi)存。 查找效率在IO讀寫過程中將會付出巨大的代價。在大規(guī)模數(shù)據(jù)查詢這樣一個實(shí)際應(yīng)用背景下，平衡二叉樹的效率就很成問題了。對這一問題的解決：我們也會在《多路查找樹/B-樹/B+樹 》 將詳細(xì)分析。

上面提到的紅黑樹和多路查找樹都是屬于深度有界查找樹（depth-bounded tree —DBT）

轉(zhuǎn)載于:https://www.cnblogs.com/lanqiu5ge/p/9472203.html

總結(jié)

以上是生活随笔為你收集整理的平衡二叉查找树 AVL 的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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