概念

二叉搜索樹(shù)雖然可以縮短查找的效率，但如果數(shù)據(jù)有序或者接近有序二叉搜索樹(shù)將退化為單支樹(shù)，查找元素相當(dāng)于在順序表中搜索元素，效率低下。
。因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問(wèn)題的方法：當(dāng)向二叉搜索樹(shù)中插入新結(jié)點(diǎn)后，如果能保證每個(gè)結(jié)點(diǎn)的左右子樹(shù)高度之差的絕對(duì)值不超過(guò)1(需要對(duì)樹(shù)中的結(jié)點(diǎn)進(jìn)行調(diào)整)，即可降低樹(shù)的高度，從而減少平均搜索長(zhǎng)度。

AVL樹(shù)的特點(diǎn)：
它的左右子樹(shù)都是AVL樹(shù)
左右子樹(shù)高度之差(簡(jiǎn)稱(chēng)平衡因子)的絕對(duì)值不超過(guò)1(-1/0/1)
如果一棵二叉搜索樹(shù)是高度平衡的，它就是AVL樹(shù)。如果它有n個(gè)結(jié)點(diǎn)，其高度可保持在
$O(lo{g}_{2}n)$，搜索時(shí)間復(fù)雜度O($lo{g}_{2}n$)。

AVL樹(shù)節(jié)點(diǎn)定義

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;// 該節(jié)點(diǎn)的左孩子
	AVLTreeNode<K, V>* _right;// 該節(jié)點(diǎn)的右孩子
	AVLTreeNode<K, V>* _parent;// 該節(jié)點(diǎn)的父節(jié)點(diǎn)

	pair<K, V> _kv;// 該節(jié)點(diǎn)的平衡因子
	int _bf;

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

AVL樹(shù)節(jié)點(diǎn)插入

AVL樹(shù)就是在二叉搜索樹(shù)的基礎(chǔ)上引入了平衡因子，因此AVL樹(shù)也可以看成是二叉搜索樹(shù)。那么
AVL樹(shù)的插入過(guò)程可以分為兩步：
1. 按照二叉搜索樹(shù)的方式插入新節(jié)點(diǎn)
2. 調(diào)整節(jié)點(diǎn)的平衡因子

更新平衡因子的規(guī)則:
1、新增在右，parent->bf++; 新增在左，parent->bf–:
2、更新后，parent->bf == 1 r -1，說(shuō)明parent插入前的平衡因子是0，說(shuō)明左右子樹(shù)高度相等，插入后有一邊高，parent高度變了，需要繼續(xù)往上更新
3、更新后，parent->bf == 0，說(shuō)明parent插入前的平衡因子是1 r -1，說(shuō)明左右子樹(shù)一邊高-邊低，插入后兩邊一樣高，插入填上了矮了那邊，parent所在子樹(shù)高度不變，不需要繼續(xù)往上更新
4更新后，parent->bf == 2 r -2，說(shuō)明parent插入前的平衡因子是1 or -1，已經(jīng)平衡臨界值，插入變成2 or -2，打破平衡，parent所在子樹(shù)需要旋轉(zhuǎn)處理。
5更新后，parent->bf > 2 r< -2的值，不可能，如果存在，則說(shuō)明插入前就不是AVL樹(shù)，需要去檢查之前操作的問(wèn)題.

AVL樹(shù)四種旋轉(zhuǎn)情況

左單旋

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		//1.parent是整棵樹(shù)的根
		//2.parent是子樹(shù)的根
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
		subR->_bf = parent->_bf = 0;
	}

右單旋

	//右單旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}

		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		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;
	}

先左單旋再右單旋

void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(parent->_left);
		RotateR(parent);

		//旋轉(zhuǎn)完后的根節(jié)點(diǎn)
		subLR->_bf = 0;
		if (bf == 1)
		{
 			subL->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subL->_bf = 1;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

先右單旋后左單旋

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-673906.html

	//右左雙旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		RotateR(parent->_right);
		RotateL(parent);
		subRL->_bf = 0;
		if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

元素的插入及控制平衡

typedef AVLTreeNode<K, V> Node;
	bool Insert(const pair<K, V>& kv)
	{
		//如果當(dāng)前樹(shù)為空直接設(shè)置節(jié)點(diǎn)
		if (_root == NULL)
		{
			_root = new Node(kv);
			return true;
		}
		//需要有指針記錄上一個(gè)移動(dòng)位置
		Node* cur = _root;
		Node* parent = nullptr;
		//尋找合適位置插入
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		//直接插入節(jié)點(diǎn)并設(shè)置它的指向
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//控制平衡
		//1.更新平衡因子
		while (parent)
		{
			if (parent->_right == cur)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (abs(parent->_bf) == 1)
			{	//如果為1整體向上移動(dòng)再次調(diào)增平衡
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (abs(parent->_bf) == 2)
			{
				//說(shuō)明parent所在子樹(shù)已經(jīng)不平衡了，需要旋轉(zhuǎn)處理
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					//預(yù)防調(diào)整出錯(cuò)情況
					assert(false);
				}
				break;
			}
			else
			{
			//預(yù)防調(diào)整出錯(cuò)情況
				assert(false);
			}
		}
		return true;

	}

判斷最后節(jié)點(diǎn)是否平衡

	//判斷是否平衡
bool _IsBanlance(Node* root)
	{
		if (root == NULL)
		{
			return true;
		}

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		if (rightH - leftH != root->_bf)
		{
			cout << root->_kv.first << "節(jié)點(diǎn)平衡因子異常" << endl;
			return false;
		}

		return abs(leftH - rightH) < 2
			&& _IsBanlance(root->_left)
			&& _IsBanlance(root->_right);
	}

	//計(jì)算它的最大高度
	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return max(leftH, rightH) + 1;
	}

到了這里，關(guān)于【C++】AVL樹(shù)（高度平衡二叉樹(shù)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！