這篇文章將為大家詳細(xì)講解有關(guān)AVL樹(shù)中如何插入，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

創(chuàng)新互聯(lián)公司長(zhǎng)期為上千余家客戶(hù)提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為榮昌企業(yè)提供專(zhuān)業(yè)的成都做網(wǎng)站、成都網(wǎng)站制作，榮昌網(wǎng)站改版等技術(shù)服務(wù)。擁有十多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。

AVL樹(shù)被稱(chēng)為高度平衡的二叉搜索樹(shù)，盡量降低二叉樹(shù)的高度，來(lái)保持二叉樹(shù)的平衡，減少樹(shù)的平均搜索長(zhǎng)度。

AVL樹(shù)的性質(zhì)：1、左子樹(shù)和右子樹(shù)的高度之差（絕對(duì)值）不超過(guò)1

2、樹(shù)中的每棵子樹(shù)都是AVL樹(shù)，

3、每個(gè)節(jié)點(diǎn)都有一個(gè)平衡因子，取值為（-1,0,1），通過(guò)平衡因子來(lái)判斷樹(shù)的平衡。

AVL樹(shù)的插入需要考慮以下的幾種情況：（箭頭表示要插入的方向和節(jié)點(diǎn)）

第一種情況：插入的節(jié)點(diǎn)在20的右邊，但是這樣導(dǎo)致10的平衡因子大于1所以需要進(jìn)行旋轉(zhuǎn)才能改變平衡因子

第二種情況：在左邊插入，導(dǎo)致平衡因子也不滿(mǎn)足條件，需要旋轉(zhuǎn)

第三種情況：插入的節(jié)點(diǎn)可能不構(gòu)成單旋，所以需要雙旋來(lái)解決

第四種情況：與第三種情況相反的雙旋

如此通過(guò)旋轉(zhuǎn)就可以達(dá)到在插入的時(shí)候讓此二叉樹(shù)達(dá)到平衡。

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

//main函數(shù)

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
using namespace std;
#include"AVLTree.h"

int main()
{
	testAVLTree();
	system("pause");
	return 0;
}

//AVLTree  ---->  被稱(chēng)為高度平衡的二叉搜索樹(shù)
//使用三叉鏈來(lái)實(shí)現(xiàn)此二叉平衡搜索樹(shù)
//性質(zhì)：左右高度差不超過(guò)1 && 該樹(shù)的左右子樹(shù)都為二叉平衡樹(shù)


template
struct AVLTreeNode
{
	AVLTreeNode* _left;   
	AVLTreeNode* _right;
	AVLTreeNode* _parent;

	K _key;
	V _value;

	int _bf; // 平衡因子

	//構(gòu)造函數(shù)
	AVLTreeNode(const K& key,const V& value) :_left(NULL), _right(NULL), _parent(NULL)
		, _key(key), _value(value), _bf(0)
	{}
};

template
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	AVLTree() :_root(NULL)
	{}
	//使用非遞歸的插入
	bool Insert(const K& key, const V& value)
	{
		//如果根節(jié)點(diǎn)不存在說(shuō)明插入的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)，直接new 一個(gè)即可
		if (_root == NULL){
			_root = new Node(key, value);
			return true;
		}
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key < key){
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key>key){
				parent = cur;
				cur = cur->_left;
			}
			else{
				return false;
			}
		}
			//走到這里，說(shuō)明這個(gè)節(jié)點(diǎn)不存在，先new
			cur = new Node(key, value);

			//比較插入節(jié)點(diǎn)的值與父節(jié)點(diǎn)的值，再考慮鏈上左還是右
			if (parent->_key < key){
				parent->_right = cur;
				cur->_parent = parent;
			}
			else if (parent->_key>key){
				parent->_left = cur;
				cur->_parent = parent;
			}
			else{
				while (parent)
				{
					//判斷cur是插在了parent的左邊還是右邊，再判斷平衡因子是++還是--
					if (cur == parent->_left){
						parent->_bf--;
					}
					else{
						parent->_bf++;
					}
					//++或--之后，判斷平衡因子是否等于2或等于-2
					if (parent->_bf == 0)    //等于0說(shuō)明沒(méi)有變，則跳出循環(huán)
					{
						break;
					}
					else if (parent->_bf == 1 || parent->_bf == -1)
					{
						cur = parent;
						parent = cur->_parent;
					}
					else if (parent->_bf == 2 || parent->_bf == -2)//如果等于2或者等于-2則不再插入，先調(diào)節(jié)為二叉平衡樹(shù)再插入
					{
						//根據(jù)平衡因子來(lái)判斷需要調(diào)整的樹(shù)是哪種類(lèi)型，再選擇單旋還是雙旋
						//如果父節(jié)點(diǎn)的平衡因子等于2，說(shuō)明右子樹(shù)比左子樹(shù)高，再判斷右子樹(shù)的子樹(shù)是在它的左邊還是右邊
						if (parent->_bf == 2)
						{
							if (cur->_bf == 1){
								RotateL(parent);
							}
							else{
								RotateRL(parent);
							}
						}
						else
						{
							if (cur->_bf == -1)
								RotateR(parent);
							else
								RotateLR(parent);
						}
					}
				}
			}
			return true;
		}
		//cur = parent;
	//右單旋
	void RotateR(Node* parent)
	{
		//需要記錄parent上面是否還有父親節(jié)點(diǎn)
		Node* ppNode = parent->_parent;

		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		//如果subLR存在  就將它的父親置為parent
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		parent->_parent = subL;

		//如果parent等于根節(jié)點(diǎn)，說(shuō)明已經(jīng)到第一個(gè)節(jié)點(diǎn)，不需要調(diào)整，直接將subL作為根即可
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = NULL;
		}
		else   //如果還沒(méi)有到根節(jié)點(diǎn)還需要判斷parent是左還是右
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}
	//左單旋
	void RotateL(Node* parent)
	{
		Node* ppNode = parent->_parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		//判斷subRL是否存在
		if (subRL){
			subRL->_parent = parent;			
		}
		subR->_left = parent;
		parent->_parent = subRL;
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = NULL;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
			subR->_parent = ppNode;
		}
	}
	//左右單旋
	void RotateLR(Node* parent)
	{
		RotateL(parent->_right);
		RotateR(parent);
	}
	//右左單旋
	void RotateRL(Node* parent)
	{
		RotateR(parent->_left);
		RotateL(parent);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}	
	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (root == NULL)
			return;
		int leftheight = _Height(root->_left);
		int rightheight = _Height(root->_right);
		return abs(rightheight - leftheight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
	}
	size_t _Height(Node* root)
	{
		if (root == NULL)
			return 0;
		size_t left = _Height(root->_left);
		size_t right = _Height(root->_right);
		return left > right ? left + 1 : right + 1;
	}
private:
	Node* _root;
};

void testAVLTree()
{
	AVLTree t;
	int a[] = { 16,3,7,11,9,26,18,14,15};
	for (int i = 0; i < (sizeof(a) / sizeof(a[0])); i++)
	{
		cout<
關(guān)于“AVL樹(shù)中如何插入”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。
            
            
                        

            當(dāng)前名稱(chēng)：AVL樹(shù)中如何插入            

            轉(zhuǎn)載來(lái)于：http://weahome.cn/article/gopdop.html