代码详解AVL树的插进去【C#.Net教程】,插入,详解,代码

AVL树被称为高度均衡的二叉搜刮树，只管下降二叉树的高度，来坚持二叉树的均衡，削减树的均匀搜刮长度。

AVL树的性子：1、左子树和右子树的高度之差（绝对值）不凌驾1

2、树中的每棵子树都是AVL树，

3、每一个节点都有一个均衡因子，取值为（-1,0,1），经由过程均衡因子来推断树的均衡。

AVL树的插进去须要斟酌以下的几种状况：（箭头示意要插进去的方向和节点）

第一种状况：插进去的节点在20的右侧，然则如许致使10的均衡因子大于1所以须要举行扭转才转变均衡因子

第二种状况：在左侧插进去，致使均衡因子也不满足前提，须要扭转

第三种状况：插进去的节点可能不构成单旋，所以须要双旋来处理

第四种状况：与第三种状况相反的双旋

云云经由过程扭转就能够到达在插进去的时刻让此二叉树到达均衡。

完成代码以下：

//main函数

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
using namespace std;
#include"AVLTree.h"

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

//AVLTree  ---->  被称为高度均衡的二叉搜刮树
//运用三叉链来完成此二叉均衡搜刮树
//性子：摆布高度差不凌驾1 && 该树的摆布子树都为二叉均衡树


template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;   
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	K _key;
	V _value;

	int _bf; // 均衡因子

	//组织函数
	AVLTreeNode(const K& key,const V& value) :_left(NULL), _right(NULL), _parent(NULL)
		, _key(key), _value(value), _bf(0)
	{}
};

template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K,V> Node;
public:
	AVLTree() :_root(NULL)
	{}
	//运用非递归的插进去
	bool Insert(const K& key, const V& value)
	{
		//假如根节点不存在申明插进去的节点是第一个节点，直接new 一个即可
		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;
			}
		}
			//走到这里，申明这个节点不存在，先new
			cur = new Node(key, value);

			//比较插进去节点的值与父节点的值，再斟酌链上左照样右
			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申明没有变，则跳出轮回
					{
						break;
					}
					else if (parent->_bf == 1 || parent->_bf == -1)
					{
						cur = parent;
						parent = cur->_parent;
					}
					else if (parent->_bf == 2 || parent->_bf == -2)//假如即是2或许即是-2则不再插进去，先调治为二叉均衡树再插进去
					{
						//依据均衡因子来推断须要调解的树是哪一种范例，再挑选单旋照样双旋
						//假如父节点的均衡因子即是2，申明右子树比左子树高，再推断右子树的子树是在它的左侧照样右侧
						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上面是不是另有父亲节点
		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即是根节点，申明已到第一个节点，不须要调解，直接将subL作为根即可
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = NULL;
		}
		else   //假如还没有到根节点还须要推断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<int, int> t;
	int a[] = { 16,3,7,11,9,26,18,14,15};
	for (int i = 0; i < (sizeof(a) / sizeof(a[0])); i++)
	{
		cout<<t.Insert(a[i], 0)<<endl;
	}
	t.InOrder();
}

以上就是代码详解AVL树的插进去的细致内容，更多请关注ki4网别的相干文章！