如果BST樹插入的順序是有序的，那么BST樹就會退化成一個雙鏈表結構，查詢的速率就會很慢，

所以有了AVL樹的意義。

AVL樹的定義：

是具有下列性質的二叉搜索樹

? ? ? ? 1、它的左子樹和右子樹都是AVL樹

? ? ? ? 2、左子樹和右子樹的高度之差的絕對值不超過1

結點的平衡因子：每一個結點都有一個平衡因子，代表著右子樹（左子樹）高度減去左子樹（右子樹）高度的高度差，AVL樹任一結點的平衡因子只能取-1，0，1。

AVL樹的插入：

向一棵本來是平衡的AVL樹插入時，出現(xiàn)了不平衡，則需要做平衡話處理，使其平衡

平衡化旋轉

1、如單旋轉（左旋和右旋）

2、雙旋轉（左平衡和右平衡）

3、每插入一個新結點時，AVL樹中相關結點的平衡狀態(tài)會發(fā)生改變，因此，需要從插入位置沿通向根的路徑回溯，檢查各結點的平衡因子（左、右子樹的高度差）。

如果在某一結點發(fā)現(xiàn)高度不平衡，停止回溯。

1、從發(fā)生不平衡的結點起，沿剛才回溯的路徑取直接下兩層的結點

2、如果這三個結點處于一條直線上，則采用單旋轉進行平衡化，單旋轉可按其方向分為左單旋和右單旋，其中一個是另一個的鏡像，其方向與不平衡的形狀相關

3、如果這三個結點處于一條折現(xiàn)上，則采用雙旋轉進行平衡化，雙旋轉也分兩種。

左單旋轉

void RotateLeft(AVLTree* ptree, AVLNode* ptr)//左單旋
{
	assert(ptree != nullptr && ptr != nullptr);
	AVLNode* newroot = ptr->rightchild;
	newroot->parent = ptr->parent;
	ptr->rightchild = newroot->leftchild;
	if (newroot->leftchild != nullptr)
	{
		newroot->leftchild->parent = ptr;
	}
	newroot->leftchild = ptr;
	AVLNode* pa = ptr->parent;
	if (pa == nullptr)
	{
		ptree->root = newroot;
	}
	if (pa->leftchild = ptr)
	{
		pa->leftchild = newroot;
	}
	else
	{
		pa->rightchild = newroot;
	}
	ptr->parent = newroot;
}

右單旋

void RotateRight(AVLTree* ptree, AVLNode* ptr)//右單旋
{
	assert(ptree != nullptr && ptr != nullptr);
	AVLNode* newroot = ptr->leftchild;
	newroot->parent = ptr->parent;
	ptr->leftchild = newroot->rightchild;
	if (newroot->rightchild != nullptr)
	{
		ptr->leftchild->parent = ptr;
	}
	newroot->rightchild = ptr;
	AVLNode* pa = ptr->parent;
	if (pa == nullptr)
	{
		ptree->root = newroot;
	}else
	{
	if (pa->leftchild == ptr)
	{
		pa->leftchild = newroot;
	}
	else
	{
		pa->rightchild = newroot;
	}
	ptr->parent = newroot;
	}
}

雙旋轉

?

//雙旋轉 分為兩次單旋轉
void LeftBalance(AVLTree* ptree, AVLNode* ptr)//左平衡
{
	assert(ptree != nullptr && ptr != nullptr);
	AVLNode* leftsub = ptr->leftchild, * rightsub = nullptr;
	switch (leftsub -> balance)
	{
	case 0:
		cout << "left banlance!" << endl;
		break;
	case -1:
		ptr->balance = 0;
		leftsub->balance = 0;
		RotateRight(ptree, ptr);
		break;
	case 1:
		rightsub = leftsub->rightchild;
		switch (rightsub->balance)
		{
		case 0:
			ptr->balance = 0;
			leftsub->balance = 0;
			break;
		case 1:
			ptr->balance = 0;
			leftsub->balance = -1;
			break;
		case -1:
			ptr->balance = 1;
			leftsub->balance = 0;
			break;
		}
		rightsub->balance = 0;
		RotateLeft(ptree, leftsub);
		RotateRight(ptree, ptr);
		break;
	}
}
void RightBalance(AVLTree* ptree, AVLNode* ptr)//右平衡
{
	assert(ptree != nullptr && ptr != nullptr);
	AVLNode* rightsub = ptr->rightchild, * leftsub = nullptr;
	switch (rightsub->balance)
	{
	case 0:
		cout << "avl tree right balance" << endl;
		break;
	case 1:
		ptr->balance = 0;
		rightsub->balance = 0;
		RotateLeft(ptree, ptr);
		break;
	case -1:
		leftsub = rightsub->leftchild;
		switch (leftsub->balance)
		{
		case 0: 
			ptr->balance = 0;
			rightsub->balance = 0;
			break;
		case 1:
			ptr->balance = -1;
			rightsub->balance = 0;
			break;
		case -1:
			ptr->balance = 0;
			rightsub->balance = 1;
			break;
		}
		leftsub->balance = 0;
		RotateRight(ptree, rightsub);
		RotateLeft(ptree, ptr); 
		break;
	}
	
}

插入和調整

void Adjust_Insert_Item(AVLTree* ptree, AVLNode* ptr)
{
	assert(ptree != nullptr && ptr != nullptr);
	bool taller = true;
	AVLNode* pa = ptr->parent;
	while (pa != nullptr && taller)
	{
		if (pa->leftchild == ptr)
		{
			switch (pa->balance)
			{
			case 0: pa->balance = -1; break;
			case 1: pa->balance = 0;
				taller = false;
				break;
			case -1:
				LeftBalance(ptree, pa);
				taller = false;
				break;
			}
		}
		else
		{	// ptr pa->rightchild
			switch (pa->balance)
			{
			case 0: pa->balance = 1; break;
			case -1: pa->balance = 0;
				taller = false;
				break;
			case 1:
				RightBalance(ptree, pa);
				taller = false;
				break;
			}
		}
		ptr = pa;
		pa = ptr->parent;
	}
}

bool Insert_Item(AVLTree* ptree, const KeyType kx)
{
	assert(ptree != nullptr);
	AVLNode* ptr = ptree->root, * pa = nullptr;
	while (ptr != nullptr && ptr->key != kx)
	{
		pa = ptr;
		ptr = kx > ptr->key ? ptr->rightchild : ptr->leftchild;
	}
	if (ptr != nullptr && ptr->key == kx) return false;

	ptr = Buynode();
	ptr->key = kx;
	ptr->parent = pa; //
	if (pa != nullptr)
	{
		if (ptr->key > pa->key)
		{
			pa->rightchild = ptr;
		}
		else
		{
			pa->leftchild = ptr;
		}
	}
	else
	{
		ptree->root = ptr;
	}
	Adjust_Insert_Item(ptree, ptr);
	ptree->cursize += 1;
}

刪除

和刪除BST樹結點思路相同，如果是雙分支，則刪除中序遍歷的下一個結點文章來源地址http://www.zghlxwxcb.cn/news/detail-448423.html

到了這里，關于AVL樹（平衡二叉搜索樹）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！