AVL樹 #avl樹 #56cto

1、AVL樹：

AVL樹又稱為高度平衡的二叉搜尋樹，是1962年有俄羅斯的數學家G.M.Adel'son-Vel'skii和E.M.Landis提出來的。它能保持二叉樹的高度

平衡，盡量降低二叉樹的高度，減少樹的平均搜尋長度。

2、AVL樹的性質：1、左子樹和右子樹的高度之差的絕對值不超過1.

2、樹中的每個左子樹和右子樹都是AVL樹。

3、每個節點都有一個平衡因子(balance factor--bf),任一節點的平衡因子是-1,0,1。(每個節點的平衡因子等于右子樹的高度減去左子樹樹的高度 )

3、AVL樹的效率

#include <iostream>
#include <queue>
using namespace std;

template <typename T>
struct TreeNode
{
	T Data;
	int height;
	TreeNode<T> *left;
	TreeNode<T> *right;
	TreeNode<T> *parent;
	TreeNode(T data)
		:left(NULL)
		,right(NULL)
		,Data(data)
		,parent(NULL)
		,height(0)
	{}
};


template <typename T>
class AVLtree
{
public:
	AVLtree()
	{}
	~AVLtree()
	{}
	AVLtree(T *arr,size_t sz);
	void Insert(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		_root = tmp;
		InsertAVLtree(_root,data);
	}
	void Search(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		tmp = SearchAVLtree(_root,tmp);
		if(tmp)
			cout<<'Y'<<endl;
		else
			cout<<'N'<<endl;
	}
	void Min()
	{
		TreeNode<T>* node = MinAVLtree(_root);
		cout<<node->Data<<endl;
	}
	void Max()
	{
		TreeNode<T>* node = MaxAVLtree(_root);
		cout<<node->Data<<endl;
	}
	void MaxLeft()
	{
		TreeNode<T>* node = MaxLeftAVLtree(_root);
		cout<<node->Data<<endl;
	}
	void MinRight()
	{
		TreeNode<T>* node = MinRightAVLtree(_root);
		cout<<node->Data<<endl;
	}
	void PrevNode(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		tmp = SearchAVLtree(_root,tmp);
		if (tmp)
			tmp = prevAVLtree(tmp);
		cout<<tmp->Data<<endl;
	}
	void PostNode(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		tmp = SearchAVLtree(_root,tmp);
		if (tmp)
			tmp = postAVLtree(tmp);
		cout<<tmp->Data<<endl;
	}
	void DeleteNode(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		tmp = SearchAVLtree(_root,tmp);
		if (tmp)
			_root= DeleteAVLtree(_root,tmp);
	}
	void Destroy()
	{
		DestroyAVLtree(_root);
	}
	void Mid()
	{
		MidOrder(_root);
	}
	void MidOrder(TreeNode<T> *Root)
	{
		if(Root==NULL)
			return;
		MidOrder(Root->left);
		cout<<Root->Data<<" ";
		MidOrder(Root->right);
	}
	int Height(TreeNode<T> *Root)
	{
		return HeightTree(Root);
	}
	int MAX(int h1, int h2)
	{
		return h1 > h2 ? h1 : h2;
	}

	void BitreeFloorOrder()
	{
		FloorOrder(_root);
	}
	
protected:
	TreeNode<T>* RightRightRotate(TreeNode<T> *Node)
	{
		TreeNode<T> *cur = Node->left;
		Node->left = cur->right;
		cur->right = Node;
		Node->height = MAX(Height(Node->left),Height(Node->right))+1;
		cur->height = MAX(Height(cur->left),Height(cur->right))+1;
		return cur;
	}
	TreeNode<T>* LeftLeftRotate(TreeNode<T> * Node)
	{
		TreeNode<T> * cur=Node->right;
		Node->right=cur->left;
		cur->left=Node;
		Node->height = MAX(Height(Node->left),Height(Node->right))+1;
		cur->height = MAX(Height(cur->left),Height(cur->right))+1;
		return cur;
	}
	TreeNode<T>* RightLeftRotate(TreeNode<T> *Node)
	{
		Node->right = RightRightRotate(Node->right);
		return LeftLeftRotate(Node);
	} 
	TreeNode<T>* LeftRightRotate(TreeNode<T> *Node)
	{
		Node->left = LeftLeftRotate(Node->left);
		return RightRightRotate(Node);
	}
	int HeightTree(TreeNode<T> *Node)
	{
		if(Node != NULL)
			return Node->height;
	}
	TreeNode<T>* InsertAVLtree(TreeNode<T> *root,T key);
	TreeNode<T>* SearchAVLtree(TreeNode<T> *Root,TreeNode<T> *Node);
	TreeNode<T>* MinAVLtree(TreeNode<T>* Root);
	TreeNode<T>* MaxAVLtree(TreeNode<T>* Root);
	TreeNode<T>* MaxLeftAVLtree(TreeNode<T> *Root);
	TreeNode<T>* MinRightAVLtree(TreeNode<T> *Root);
	TreeNode<T>* prevAVLtree(TreeNode<T> *Node);
	TreeNode<T>* postAVLtree(TreeNode<T> *Node);
	TreeNode<T>* DeleteAVLtree(TreeNode<T> *Root, TreeNode<T> *Node);
	void DestroyAVLtree(TreeNode<T> *Root);
	void FloorOrder(TreeNode<T> *Root);
private:
	TreeNode<T> * _root;
};

template<typename T>
AVLtree<T>::AVLtree(T *arr,size_t sz)
{
	_root = new TreeNode<T>(arr[0]);
	for (int i = 1; i < sz; i++)
	{
		_root = InsertAVLtree(_root,arr[i]);
	}
}
template<typename T>
TreeNode<T>* AVLtree<T>::InsertAVLtree(TreeNode<T> *root,T key)
{
	if (root == NULL)
		root = new TreeNode<T>(key);
	else
	{
		if (key < root->Data)
		{
			root->left = InsertAVLtree(root->left, key);
			if (Height(root->left) - Height(root->right) > 1)
			{
				if (key < root->left->Data)
				{
					root = RightRightRotate(root);
				}
				if (key > root->left->Data)
				{
					root = LeftRightRotate(root);
				}
			}
		}
		else if(key > root->Data)
		{
			root->right = InsertAVLtree(root->right, key);
			if (Height(root->right) - Height(root->left) > 1)
			{
				if (key > root->right->Data)
				{
					root = LeftLeftRotate(root);
				}
				if (key < root->right->Data)
				{
					root = RightLeftRotate(root);
				}
			}
		}	
	}
	root->height = MAX(Height(root->left),Height(root->right))+1;
	return root;
}
template<typename T>
TreeNode<T>* AVLtree<T>::SearchAVLtree(TreeNode<T>* Root,TreeNode<T> *Node)
{
	TreeNode<T> *cur=Root;
	while(cur&&cur->Data!=Node->Data)
	{
		if(cur->Data>Node->Data)
		{
			cur=cur->left;
		}
		else 
		{
			cur=cur->right;
		}
	}
	if(cur)
		return cur;
	else 
		return NULL;
}

template<typename T>
TreeNode<T>* AVLtree<T>::MinAVLtree(TreeNode<T>* Root)
{
	TreeNode<T>* cur=Root;
	while(cur->left)
	{
		cur=cur->left;
	}
	return cur;
}

template<typename T>
TreeNode<T>* AVLtree<T>::MaxAVLtree(TreeNode<T>* Root)
{
	TreeNode<T>* cur=Root;
	while(cur->right)
	{
		cur=cur->right;
	}
	return cur;
}


template<typename T>
TreeNode<T>* AVLtree<T>::MaxLeftAVLtree(TreeNode<T> *Root)
{
	if (Root->left == NULL)
		return NULL;
	TreeNode<T>* cur = Root->left;
	while(cur->right)
	{
		cur = cur->right;
	}
	return cur;
}


template<typename T>
TreeNode<T>* AVLtree<T>::MinRightAVLtree(TreeNode<T> *Root)
{
	if (Root->right == NULL)
		return NULL;
	TreeNode<T>* cur = Root->right;
	while(cur->left)
	{
		cur = cur->left;
	}
	return cur;
}


template <typename T>
TreeNode<T>* AVLtree<T>::prevAVLtree(TreeNode<T> *Node)
{
	if (Node->left)
		return MaxLeftAVLtree(Node);
	TreeNode<T> *P = Node->parent;
	if (Node->left == NULL && Node == P->right)
	{
		return Node->parent;
	}
	while (P && Node == P->left)
	{
		Node = P;
		P = P->parent;
	}
	return P;
}


template <typename T>
TreeNode<T>* AVLtree<T>::postAVLtree(TreeNode<T> *Node)
{
	if (Node->right)
		return MinRightAVLtree(Node);
	TreeNode<T> *P = Node->parent;
	if (Node->right == NULL && Node == P->left)
	{
		return Node->parent;
	}
	while (P && Node == P->right)
	{
		Node = P;
		P = P->parent;
	}
	return P;
}
template <typename T>
TreeNode<T>* AVLtree<T>::DeleteAVLtree(TreeNode<T> *Root, TreeNode<T> *Node)
{
	if (Node->Data < Root->Data)
	{
		Root->left = DeleteAVLtree(Root->left,Node);
		if (Height(Root->right) - Height(Root->left) > 1)
		{
			TreeNode<T> *cur = Root->right;
			if (Height(cur->left) < Height(cur->right))
			{
				Root = LeftLeftRotate(Root); 
			}
			if (Height(cur->left) > Height(cur->right))
			{
				Root = RightLeftRotate(Root);
			}
		}
	}
	else if (Node->Data > Root->Data)
	{
		Root->right = DeleteAVLtree(Root->right, Node);
		if (Height(Root->left) - Height(Root->right) > 1)
		{
			TreeNode<T> *cur = Root->left;
			if (Height(cur->left) < Height(cur->right))
			{
				Root = LeftRightRotate(Root);
			}
			if (Height(cur->left) > Height(cur->right))
			{
				Root = RightRightRotate(Root);
			}
		}
	}
	else
	{
		if (Root->left && Root->right)
		{
			if (Height(Root->left) >= Height(Root->right))
			{
				TreeNode<T> *cur = prevAVLtree(Root);
				Root->Data = cur->Data;
				Root->left = DeleteAVLtree(Root->left,cur);
			}
			if (Height(Root->right) >= Height(Root->left))
			{
				TreeNode<T> *cur = postAVLtree(Root);
				Root->Data = cur->Data;
				Root->right = DeleteAVLtree(Root->right,cur);
			}
		}
		else
		{
			TreeNode<T> *tmp = Root;
			Root = Root->left ? Root->left : Root->right;
			delete tmp;
		}
	}
	return Root;
}

template <typename T>
void AVLtree<T>::DestroyAVLtree(TreeNode<T> *Root)
{
	if(Root==NULL)
		return;
	if(Root->left)
		DestroyBStree(Root->left);
	if(Root->right)
		DestroyBStree(Root->right);
	delete Root;
	Root = NULL;
}

template <typename T>
void AVLtree<T>::FloorOrder(TreeNode<T> *Root)
{
	if (Root == NULL)
		return;
	queue<TreeNode<T>*> q;
	TreeNode<T> *cur = Root;
	q.push(cur);
	while (!q.empty())
	{
		TreeNode<T> *tmp = q.front();
		cout<<tmp->Data<<" ";
		q.pop();
		if (tmp->left)
		{
			q.push(tmp->left);
		}
		if (tmp->right)
		{
			q.push(tmp->right);
		}
	}
}


void Test()
{
	//int arr[] = {0,1,2,3,4,5,6,7,8,9};
	//int arr2[] = {16,3,7,11,9,26,18,14,15};
	int arr3[] = {9,8,7,6,5,4,3,2,1,0};
	int sz = sizeof(arr3)/sizeof(arr3[0]);
	AVLtree<int> a(arr3,sz);
	//a.Mid();
	//a.BitreeFloorOrder();
	//cout<<endl;
	a.DeleteNode(5);
	a.BitreeFloorOrder();
}

int main()
{
	Test();
	return 0;
}

AVL樹

繼續閱讀

基礎知識--二叉樹 AVL樹紅黑樹二叉樹AVL樹紅黑樹

【知識點5】平衡二叉樹（AVL樹）⭐⭐⭐⭐⭐1. 提出背景2. 定義3. AVL樹的基本操作——增删改查4. 其他注意事項⭐⭐⭐⭐⭐5. 題型訓練6. 參考文檔

資料結構(python) —— 【28: AVL樹】

AVL樹的詳解與實作AVL樹的插入AVL樹的旋轉AVL樹完整實作（插入，旋轉，中序周遊，判斷是否平衡，求樹的高度）AVL樹性能分析

資料結構之平衡二叉樹（AVL樹）

1123. Is It a Complete AVL Tree (30)[AVL樹+層序周遊]

AVL樹詳解1. 簡介2. 插入3. 删除4 java代碼例子

二叉平衡樹（AVL）-C語言

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

資料結構-AVL樹

AVL平衡樹的旋轉

[ 資料結構 - C++] AVL樹原理及實作

樹、二叉樹、二叉查找樹、AVL樹、伸展樹、B-樹

順序表實作一顆avl樹

認真學習資料結構之AVL樹

AVL樹插入小結