什麼是AVL樹？

首先，我們來回顧一下二叉搜尋樹，我們知道，二叉搜尋樹雖然可以縮短查找的效率，但是如果資料有序或接近有序，二叉搜尋樹将退化為單支樹，查找元素的效率相當于在順序表中搜尋元素，效率很低。是以，兩位俄羅斯數學家G.M.Adelson-Velskii和E.Landis在1962年發明了一種解決上述問題的方法：當向二叉搜尋樹中插入新節點後，如果能保證每個結點的左右子樹高度差的絕對值不超過1，即可降低樹的高度，進而減少平均搜尋次數。

一棵AVL樹或者是空樹，或者是具有以下性質的二叉搜尋樹：

它的左右子樹都是AVL樹。
左右子樹高度之差（簡稱平衡因子）的絕對值不超過1（-1/0/1）。

『資料結構』AVL樹什麼是AVL樹？AVL樹結點的定義AVL樹的插入AVL樹的旋轉AVL樹的驗證

如果一棵二叉搜尋樹是高度平衡的，它就是AVL樹。如果它有n個結點，其高度可保持在log2(N)，搜尋時的時間複雜度為O(log2(N))。

AVL樹的性能：

AVL樹是一棵絕對平衡的二叉搜尋樹，其要求每個結點的左右子樹高度差的絕對值都不超過1，這樣可以保證查詢時高效的時間複雜度，即log2(N)。

但是如果要對AVL樹做一些結構修改的操作，性能非常低下，比如：插入時要維護其絕對平衡，旋轉的次數比較多，更差的是在删除時，有可能一直要讓旋轉持續到根的位置，即旋轉的量級為O(log2(N))。

是以：如果需要一種查詢高效且有序的資料結構，而且資料的個數為靜态的（即不會改變），可以考慮AVL樹，但一個結構經常修改，就不太适合。

AVL樹結點的定義

// AVL樹結點
template<class K, class V>
struct AVLTreeNode{

	AVLTreeNode(const pair<K, V>& kv)
		: _bf(0)
		, _kv(kv)
		, _parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
	{}

	// 平衡因子
	int _bf;
	pair<K, V> _kv;
	// 該節點雙親
	AVLTreeNode<K, V>* _parent;
	// 該節點左孩子
	AVLTreeNode<K, V>* _left;
	// 該節點右孩子
	AVLTreeNode<K, V>* _right;
};

AVL樹的插入

從上面AVL數結點的定義，可以看出，AVL樹就是在二叉搜尋樹的基礎上引入了平衡因子，是以AVL樹也可以看成二叉搜尋樹。那麼AVL樹的插入過程可以分為以下步驟：

按照二叉搜尋樹的方式将新節點插入到AVL樹中。
新節點插入後，AVL樹的平衡性可能會遭到破壞，此時，就需要調整平衡因子，并檢測是否破壞了AVL樹的平衡性。
cur插入後，cur的parent的平衡因子一定要調整，在插入之前，cur的parent的平衡因子有三種情況：-1，0，1。分以下兩種情況：

如果cur插入到parent的左側，隻需要給parent的平衡因子-1即可。

如果cur插入到parent的右側，隻需要給parent的平衡因子+1即可。
此時，parent的平衡因子可能有三種情況：0，±1，±2。

如果parent的平衡因子為0，說明插入之前parent的平衡因子為±1，插入後被更新為0，此時滿足AVL樹的性質，插入成功。

如果parent的平衡因子為±1，說明插入之前parent的平衡因子一定為0，插入後被更新為±1，此時以parent為根的樹的高度增加，需要繼續向上更新。

如果parent的平衡因子為±2，則parent的平衡因子違反平衡樹的性質，需要對其進行旋轉處理。

// 插入
bool insert(const pair<K, V>& kv){
	// 空樹，直接插入
	if (_root == nullptr){
		_root = new Node(kv);
		_root->bf = 0;

		return true;
	}

	// 儲存父指針
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur != nullptr){
		// 大于根節點，右樹找
		if (kv.first > cur->_kv.first){
			parent = cur;
			cur = cur->_right;
		}
		// 小于根節點，左樹找
		else if (kv.first < cur->_kv.first){
			parent = cur;
			cur = cur->_left;
		}
		// 已經存在，插入失敗
		else{
			return false;
		}
	}

	// 找到插入位置
	cur = new Node(kv);
	// 新插入結點比parent大，插入到parent右樹
	if (kv.first > parent->_kv.first){
		parent->_right = cur;
		cur->_parent = parent;
	}
	// 新插入結點比parent小，插入到parent左樹
	else{
		parent->_left = cur;
		cur->_parent = parent;
	}

	// 調整平衡因子
	while (parent){
		// 新插入在parent的右樹，平衡因子加1
		if (cur == parent->_right){
			++parent->_bf;
		}
		// 新插入在parent的左樹，平衡因子減1
		else{
			--parent->_bf;
		}

		// 平衡因子為0，高度無影響
		if (parent->_bf == 0){
			break;
		}
		// 平衡因子為1，高度變了，向上更新
		else if (abs(parent->_bf) == 1){
			cur = parent;
			parent = parent->_parent;
		}
		// 平衡因子絕對值為2，不平衡，旋轉調整
		else if (abs(parent->_bf) == 2){
			// 平衡因子為2，右樹變高
			if (parent->_bf == 2){
				// 目前為1，新節點插入在較高右子樹的右側，左單旋
				if (cur->_bf == 1){
					leftRotate(parent);
				}
				// 目前為-1，新節點插入在較高右子樹的左側，右左單旋
				else if (cur->_bf == -1){
					rightLeftRotate(parent);
				}
			}
			// 平衡因子為-2，左樹變高
			else if (parent->_bf == -2){
				// 目前為-1，新節點插入在較高左子樹的左側，右單旋
				if (cur->_bf == -1){
					rightRotate(parent);
				}
				// 目前為1，新節點插入在較高左子樹的右側，左右單旋
				else if (cur->_bf == 1){
					rightLeftRotate(parent);
				}
			}

			break;
		}
		// 平衡因子為其他值，出錯
		else{
			assert(false);
		}
	}
}

AVL樹的旋轉

如果在一棵原本是平衡的AVL樹中插入一個新節點，可能造成不平衡，此時必須調整樹的結構，使之平衡化。根據結點插入位置的不同，AVL樹的旋轉分為四種：

新節點插入較高左子樹的左側–左左：右單旋。

『資料結構』AVL樹什麼是AVL樹？AVL樹結點的定義AVL樹的插入AVL樹的旋轉AVL樹的驗證

上圖在插入前，AVL樹是平衡的，新節點插入到10的左子樹中，10的左子樹高度增加1，導緻以20為根的二叉樹不平衡，要想讓20為根的二叉樹平衡，隻能将20的左子樹高度減少一層，20的右子樹增加一層。

進行右單旋：将左子樹往上提，這樣20轉下來，因為20比10大，隻能将其放在10的右樹，而如果10有右樹，右樹的根一定大于10小于20，是以将其放在20的左樹，旋轉完成後，更新結點的平衡因子即可。

注意事項：

10結點的右孩子可能存在，也可能不存在。
20可能是根節點，也可能是子樹。

如果是根節點，旋轉完成後，要更新根節點。

如果是子樹，可能是某個節點的左子樹，也可能是右子樹。

// 右單旋
void rightRotate(Node* parent){
	// 20結點的左樹10
	Node* subL = parent->_left;
	// 20結點的左樹的右樹b
	Node* subLR = parent->_left->_right;

	// 将b挂到20結點的左樹
	parent->_left = subLR;

	// 如果b不為空，将b的雙親結點指向20結點
	if (subLR){
		subLR->_parent = parent;
	}

	// 将20結點挂到10結點的右樹
	subL->_right = parent;

	// pp儲存20結點的雙親結點
	Node* pp = parent->_parent;
	// 将20結點的雙親結點改為10結點
	parent->_parent = subL;

	// 如果20結點是根節點
	if (pp == nullptr){
		// 10結點設為根節點
		_root = subL;
		_root->_parent = nullptr;
	}
	// 20結點不是根節點
	else{
		// 20結點是其雙親結點的左子樹
		if (pp->_left == parent){
			pp->_left = subL;
		}
		// 20結點是其雙親結點的右子樹
		else{
			pp->_right = subL;
		}

		// 10結點的雙親結點改為20結點的雙親結點
		subL->_parent = pp;
	}

	// 旋轉完成後，平衡因子更新為0
	parent->_bf = subL->_bf = 0;
}

新節點插入較高右子樹的右側–右右：左單旋。

『資料結構』AVL樹什麼是AVL樹？AVL樹結點的定義AVL樹的插入AVL樹的旋轉AVL樹的驗證

同樣，上圖在插入前是平衡的，新節點插入到20節點的右樹，導緻20節點的右樹高度增加1，進而導緻20節點的平衡因子增加到1，10節點的平衡因子增加到2，導緻不平衡，需要進行調整，使其達到平衡。

進行左單旋調整：将10節點壓下去，因為20節點的左樹都是大于10，小于20的，是以可以将20結點的左樹調整到10節點的右樹，同時将10節點調整為20節點的左樹。即可達到平衡，旋轉完成後，更新平衡因子。

注意事項：

20節點的左孩子可能存在，也可能不存在。
10節點可能是根節點，也可能是子樹。

如果10節點是根節點，旋轉完成後，要更新根節點。

如果是子樹，可能是某個節點的左子樹，也可能是右子樹。

// 左單旋
void leftRotate(Node* parent){
	// 10結點的右樹20
	Node* subR = parent->_right;
	// 10結點的右樹的左樹b
	Node* subRL = parent->_right->_left;

	// 将b設定為10結點的右樹
	parent->_right = subRL;

	// 如果b非空，将b的父親設定為10結點
	if (subRL){
		subRL->_parent = parent;
	}

	// 儲存10結點的父結點
	Node* pp = parent->_parent;

	// 将10結點的父結點設定為結點20
	parent->_parent = subR;

	// 将10結點設定為結點20的左樹
	subR->_left = parent;

	// 10結點是根節點
	if (parent == _root){
		// 20結點設為根節點
		_root = subR;
		_root->_parent = nullptr;
	}
	// 10結點不是根結點
	else{
		// 10結點是其父結點的左樹
		if (parent == pp->_left){
			pp->_left = subR;
			subR->_parent = pp;
		}
		// 10結點是其父結點的右樹
		else{
			pp->_right = subR;
			subR->_parent = pp;
		}
	}

	// 調整平衡因子
	parent->_bf = subR->_bf = 0;
}

新節點插入較高左子樹的右側–左右：先左單旋再右單旋。

『資料結構』AVL樹什麼是AVL樹？AVL樹結點的定義AVL樹的插入AVL樹的旋轉AVL樹的驗證

上圖在插入前是平衡的，但是20結點的左樹插入之後，導緻20結點的高度增加1，進而影響10結點，最終影響30結點，30結點平衡因子為-2，不平衡，需要調整。

進行雙旋，先進行左單旋，再進行右單旋。将20結點的左樹挂到10結點的右樹，再将10結點挂到20結點的左樹，完成左單旋；然後将20結點的右樹挂到30結點的左樹。在将30結點挂到20結點的右樹，完成右單旋，樹達到平衡。

注意事項：

這裡要單獨考慮平衡因子，如果不單獨考慮平衡因子，左右單旋後，三個結點的平衡因子都是0，從圖上看，三個結點的平衡因子顯然不全為0。
上述情況，如果新插入的結點在b，則雙旋之後，30結點的平衡因子應該為1，其他兩個節點平衡因子為0，因為插入在b，c的高度為h-1，雙旋後，c會成為30結點的左樹，進而導緻30結點的平衡因子為1。
如果新插入的結點在c，則雙旋之後，10結點的平衡因子為-1，其他兩個節點的平衡因子為0，因為插入在c，b的高度為h-1，雙旋之後，b會成為10結點的右樹，進而導緻10結點的平衡因子為-1。

// 左右雙旋
void leftRightRotate(Node* parent){
	// 儲存20結點的平衡因子，旋轉完成後
	// 根據該平衡因子對其他平衡因子進行調整
	int bf = parent->_left->_right->_bf;

	// 對10結點所在子樹進行左單旋
	leftRotate(parent->_left);

	// 對30結點所在樹進行右單旋
	rightRotate(parent);

	// 插入後20結點平衡因子為1
	// 說明新插入結點在20結點的右樹，說明20結點左樹高度較低
	// 左右旋之後，20結點的左樹成為10結點的右樹
	// 進而10結點的平衡因子為-1
	if (bf == 1){
		parent->_left->_bf = -1;
	}
	// 插入後20結點平衡因子為-1
	// 說明新插入結點在20結點的左樹
	// 20結點的右樹高度較低
	// 左右旋之後，20結點的右樹成為30結點的左樹
	// 進而30結點的平衡因子為1
	else if (bf == -1){
		parent->_bf = 1;
	}
}

新節點插入較高右子樹的左側–右左：先右單旋再左單旋。

『資料結構』AVL樹什麼是AVL樹？AVL樹結點的定義AVL樹的插入AVL樹的旋轉AVL樹的驗證

同樣，上圖插入在c，插入之後20結點右子樹高度增加，進而向上影響，直到影響到10結點，使得10結點平衡因子為2，導緻不平衡，雙旋進行調整。

首先進行右單旋，将c挂到30結點的左，再将30加點挂到20結點的有，完成右單旋；然後進行左單旋，将b挂到10結點的右，然後将10結點挂到20結點的左，完成左單旋。

注意事項：

這裡要注意平衡因子需要單獨處理。
如果新節點插入到b，則20的右樹c的高度較低，為h-1，雙旋之後，c會成為30結點的左樹，進而導緻30結點的平衡因子為1，其他兩個節點平衡因子為0。
如果新節點插入到c，則20結點的左樹b的高度較低，為h-1，雙旋之後，b會成為10結點的右樹，進而導緻10結點的平衡因子為-1。

// 右左旋
void rightLeftRotate(Node* parent){
	// 首先儲存插入之後20結點的平衡因子
	int bf = parent->_right->_left->_bf;

	// 進行右單旋
	rightRotate(parent->_right);

	// 進行左單旋
	leftRotate(parent);

	// 新節點插入在c
	// b的高度較低為h-1
	// 雙旋之後，b會成為10結點的右樹
	// 是以10結點的平衡因子為-1
	if (bf == 1){
		parent->_bf = -1;
	}
	// 新節點插入在b
	// c的高度較低為h-1
	// 雙旋之後，c會成為30結點的左樹
	// 是以30結點的平衡因子為1
	else if (bf == -1){
		parent->_right->_bf = 1;
	}
}

AVL樹旋轉總結：

假如以parent為根的子樹不平衡，即parent的平衡因子為2或-2，分以下情況考慮：

parent的平衡因子為2，說明parent的右子樹高，設parent的右子樹的根為subR。

當subR的平衡因子為1時，執行左單旋；

當subR的平衡因子為-1時，執行右左雙旋；
parent的平衡因子為-2，說明parent的左子樹高，設parent的左子樹的根為subL。

當subL的平衡因子為-1時，執行右單旋；

當subL的平衡因子為1時，執行左右雙旋；

旋轉完成後，原parent為根的子樹高度降低，已經平衡，不需要再向上更新。

AVL樹的驗證

AVL樹是在二叉搜尋樹的基礎上加入了平衡的限制，是以要驗證一棵樹是否為AVL樹，隻需要驗證兩點即可：

這棵樹是否為二叉搜尋樹。
這棵樹是否平衡。

如果兩個條件都滿足就說明是AVL樹。

首先來驗證其是否為二叉搜尋樹：

中序周遊結果為有序即為二叉搜尋樹。

// 中序
void _inorder(Node* root){
	_inorder(root->_left);
	cout << root->_kv.first << " ";
	_inorder(root->_right);
}

// 中序周遊
void inorder(){
	_inOrder(_root);
	cout << endl;
}

驗證是否平衡：

// 計算樹的高度
int _height(Node* root){
	if (root == nullptr){
		return 0;
	}

	if (root->_left == nullptr && root->_right == nullptr){
		return 1;
	}

	// 左樹高度
	int left_height = _height(root->_left) + 1;
	// 右樹高度
	int right_height = _height(root->_right) + 1;

	// 左樹右樹中高度的最大值為這棵樹的高度
	return left_height > right_height ? left_height : right_height;
}

// 是否平衡
bool _isBalance(Node* root){
	// 空樹是平衡的
	if (root == nullptr){
		return true;
	}

	// 計算平衡因子
	int left_height = _height(root->_left);
	int right_height = _height(root->_right);
	int bf = right_height - left_height;

	// 計算出的平衡因子和root的平衡因子不同
	// 或者平衡因子絕對值超過1，不平衡
	if (bf != root->_bf || abs(bf) > 1){
		return false;
	}

	// root的左樹和右樹是否平衡
	return _isBalance(root->_left) && _isBalance(root->_right);
}

『資料結構』AVL樹什麼是AVL樹？AVL樹結點的定義AVL樹的插入AVL樹的旋轉AVL樹的驗證

什麼是AVL樹？

AVL樹結點的定義

AVL樹的插入

AVL樹的旋轉

AVL樹的驗證

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器