【数据结构】中的平衡搜索树-AVLTree

深藏阁楼爱情的钟 2022-06-18 09:58 138阅读 0赞

数据结构中：

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。

特点：

AVL树本质上还是一棵二叉搜索树，它的特点是：

1.本身首先是一棵二叉搜索树。

2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

在AVL树里面，有几个重要的代码实现：

插入：

bool Insert(const K& key, const V& value)
    	{
    		if (_root == NULL)
    		{
    			_root = new Node(key, value);
    			return true;
    		}
    
    		Node* parent = NULL;
    		Node* cur = _root;
    
    		//判断插入的值和cur的大小
    		while (cur)
    		{
    			parent = cur;
    			if (cur->_key < key)
    			{
    				cur = cur->_right;
    			}
    			else if (cur->_key>key)
    			{
    				cur = cur->_left;
    			}
    			else
    			{
    				return false;
    			}
    		}
    
    		cur = new Node(key, value);//构建一个新的节点
    		if (parent->_key > key)//如果父节点的值大于key,则key就为父节点的左边
    		{
    			parent->_left = cur;
    			cur->_parent = parent;
    		}
    		else // 如果父节点的值小于key, 则key就为父节点的右边
    		{
    			parent->_right = cur;
    			cur->_parent = parent;
    		}
    
    		while (parent)
    		{
    			if (cur == parent->_left)//如果插入的节点在parent的左边，则平衡因子-1
    			{
    				parent->_bf--;
    			}
    			else//如果插入的节点在parent的右边，则平衡因子+1
    			{
    				parent->_bf++;
    			}
    
    			if (parent->_bf == 0)//平衡因子为0，子树的高度没有变化
    			{
    				break;
    			}
    			else if(parent->_bf == -1 || parent->_bf == 1)
    			{
    				//子树的高度变化，但是高度没有变化，继续向上一层树进行检查，是否对上一层有影响
    				cur = parent;
    				parent = cur->_parent;
    			}
    
    			else//子树的高度为2或者-2 导致二叉树不再平衡，则需要进行旋转
    			{
    				if(parent->_bf==2)//说明右边子树的高度增加了
    				{
    					Node* subR = parent->_right;
    
    					if (subR->_bf == 1)
    					{
    						RotateL(parent);
    					}
    					else
    					{
    						RotateRL(parent);
    					}
    				}
    
    				else//说明左边的子树的高度增加了
    				{
    					Node* subL = parent->_left;
    					if (subL->_bf == -1)
    					{
    						RotateR(parent);
    					}
    					else
    					{
    						RotateLR(parent);
    					}
    				}
    				break;
    			}
    		}
    	}

左单旋：

void RotateL(Node* parent)
    	{
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    		parent->_right = subRL;
    		if (subRL!=NULL)
    		{
    			subRL->_parent = parent;
    		}
    		subR->_left = parent;
    		Node* ppNode = parent->_parent;
    		parent->_parent = subR;
    		if (ppNode == NULL)
    		{
    			subR = _root;
    			subR->_parent = NULL;
    		}
    		else
    		{
    			if (ppNode->_left == parent)
    			{
    				ppNode->_left = subR;
    			}
    			else
    			{
    				ppNode->_right = subR;
    			}
    			subR->_parent = ppNode;
    		}
    		parent->_bf = subR->_bf = 0;
    	}

右单旋：

void RotateR(Node* parent)
    	{
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		parent->_left = subLR;
    		if (subLR)
    		{
    			subLR->_parent = parent;
    		}
    		subL->_right = parent;
    		Node* ppNode = parent->_parent;
    		parent->_parent = subL;
    
    		if (ppNode == NULL)
    		{
    			_root = subL;
    			subL->_parent = NULL;
    		}
    		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(subL);
    		RotateR(parent);
    
    		if (bf == 0)
    		{
    			parent->_bf = subL->_bf = subLR->_bf = 0;
    		}
    		else if (bf==1)
    		{
    			subL->_bf = -1;
    			parent->_bf = 0;
    			subLR->_bf = 0;
    		}
    		else
    		{
    			subL->_bf = 0;
    			subLR->_bf = 0;
    			parent->_bf = 1;
    		}
    	}

右左双旋：

void RotateRL(Node* parent)
    	{
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    		int bf = subRL->_bf;
    
    		RotateR(subR);
    		RotateL(parent);
    
    		if (bf == 0)
    		{
    			parent->_bf = subR->_bf = subRL->_bf = 0;
    		}
    		else if (bf == -1)
    		{
    			parent->_bf = 0;
    			subRL->_bf = 0;
    			subR->_bf = 1;
    		}
    		else
    		{
    			parent->_bf = -1;
    			subRL->_bf = 0;
    			subR->_bf = 0;
    		}
    	}

判断是否是平衡树：

bool _IsBalance(Node* root,int height)
    	{
    		if (root == NULL)
    		{
    			height = 0;
    			return true;
    		}
    		int l = 0;
    		int r = 0;
    
    		if (_IsBalance(root->_left, 1)&& _IsBalance(root->_right, r) && abs(r - 1) < 2)
    		{
    			height = l < r ? r + 1 : l + 1;
    
    			if (root->_bf != r - 1)
    			{
    				cout << "平衡因子异常"<<root->_key <<endl;
    				return false;
    			}
    			return true;
    		}
    	}

下面是完整的代码：

#include<iostream>
    using namespace std;
    
    #include<cstdlib>
    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)
    		, _bf(0)
    		, _key(key)
    		, _value(value)
    	{}
    };
    
    
    template<class K,class V>
    class AVLTree
    {
    	typedef AVLTreeNode<K, V> Node;
    public:
    	AVLTree()
    	:_root(NULL)
    	{}
    
    	~AVLTree()
    	{}
    
    	bool Insert(const K& key, const V& value)
    	{
    		if (_root == NULL)
    		{
    			_root = new Node(key, value);
    			return true;
    		}
    
    		Node* parent = NULL;
    		Node* cur = _root;
    
    		//判断插入的值和cur的大小
    		while (cur)
    		{
    			parent = cur;
    			if (cur->_key < key)
    			{
    				cur = cur->_right;
    			}
    			else if (cur->_key>key)
    			{
    				cur = cur->_left;
    			}
    			else
    			{
    				return false;
    			}
    		}
    
    		cur = new Node(key, value);//构建一个新的节点
    		if (parent->_key > key)//如果父节点的值大于key,则key就为父节点的左边
    		{
    			parent->_left = cur;
    			cur->_parent = parent;
    		}
    		else // 如果父节点的值小于key, 则key就为父节点的右边
    		{
    			parent->_right = cur;
    			cur->_parent = parent;
    		}
    
    		while (parent)
    		{
    			if (cur == parent->_left)//如果插入的节点在parent的左边，则平衡因子-1
    			{
    				parent->_bf--;
    			}
    			else//如果插入的节点在parent的右边，则平衡因子+1
    			{
    				parent->_bf++;
    			}
    
    			if (parent->_bf == 0)//平衡因子为0，子树的高度没有变化
    			{
    				break;
    			}
    			else if(parent->_bf == -1 || parent->_bf == 1)
    			{
    				//子树的高度变化，但是高度没有变化，继续向上一层树进行检查，是否对上一层有影响
    				cur = parent;
    				parent = cur->_parent;
    			}
    
    			else//子树的高度为2或者-2 导致二叉树不再平衡，则需要进行旋转
    			{
    				if(parent->_bf==2)//说明右边子树的高度增加了
    				{
    					Node* subR = parent->_right;
    
    					if (subR->_bf == 1)
    					{
    						RotateL(parent);
    					}
    					else
    					{
    						RotateRL(parent);
    					}
    				}
    
    				else//说明左边的子树的高度增加了
    				{
    					Node* subL = parent->_left;
    					if (subL->_bf == -1)
    					{
    						RotateR(parent);
    					}
    					else
    					{
    						RotateLR(parent);
    					}
    				}
    				break;
    			}
    		}
    	}
    
    	void InOrder()
    	{
    		_InOrder(_root);
    	}
    
    	bool IsBalance()
    	{
    		int height = 0;
    		return _IsBalance(_root,height);
    	}
    	
    protected:
    	void RotateL(Node* parent)
    	{
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    		parent->_right = subRL;
    		if (subRL!=NULL)
    		{
    			subRL->_parent = parent;
    		}
    		subR->_left = parent;
    		Node* ppNode = parent->_parent;
    		parent->_parent = subR;
    		if (ppNode == NULL)
    		{
    			subR = _root;
    			subR->_parent = NULL;
    		}
    		else
    		{
    			if (ppNode->_left == parent)
    			{
    				ppNode->_left = subR;
    			}
    			else
    			{
    				ppNode->_right = subR;
    			}
    			subR->_parent = ppNode;
    		}
    		parent->_bf = subR->_bf = 0;
    	}
    
    	void RotateR(Node* parent)
    	{
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		parent->_left = subLR;
    		if (subLR)
    		{
    			subLR->_parent = parent;
    		}
    		subL->_right = parent;
    		Node* ppNode = parent->_parent;
    		parent->_parent = subL;
    
    		if (ppNode == NULL)
    		{
    			_root = subL;
    			subL->_parent = NULL;
    		}
    		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(subL);
    		RotateR(parent);
    
    		if (bf == 0)
    		{
    			parent->_bf = subL->_bf = subLR->_bf = 0;
    		}
    		else if (bf==1)
    		{
    			subL->_bf = -1;
    			parent->_bf = 0;
    			subLR->_bf = 0;
    		}
    		else
    		{
    			subL->_bf = 0;
    			subLR->_bf = 0;
    			parent->_bf = 1;
    		}
    	}
    
    	void RotateRL(Node* parent)
    	{
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    		int bf = subRL->_bf;
    
    		RotateR(subR);
    		RotateL(parent);
    
    		if (bf == 0)
    		{
    			parent->_bf = subR->_bf = subRL->_bf = 0;
    		}
    		else if (bf == -1)
    		{
    			parent->_bf = 0;
    			subRL->_bf = 0;
    			subR->_bf = 1;
    		}
    		else
    		{
    			parent->_bf = -1;
    			subRL->_bf = 0;
    			subR->_bf = 0;
    		}
    	}
    
    	void _InOrder(Node* root)//中序
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_InOrder(root->_left);
    		cout << root->_key << ":" << root->_value << endl;
    		_InOrder(root->_right);
    	}
    
    	size_t _Height(Node* root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		size_t LHeight = _Height(root->_left);
    		size_t RHeight = _Height(root->_right);
    
    		return LHeight < RHeight ? RHeight + 1 : LHeight + 1;
    	}
    
    	bool _IsBalance(Node* root,int height)
    	{
    		if (root == NULL)
    		{
    			height = 0;
    			return true;
    		}
    		int l = 0;
    		int r = 0;
    
    		if (_IsBalance(root->_left, 1)&& _IsBalance(root->_right, r) && abs(r - 1) < 2)
    		{
    			height = l < r ? r + 1 : l + 1;
    
    			if (root->_bf != r - 1)
    			{
    				cout << "平衡因子异常"<<root->_key <<endl;
    				return false;
    			}
    			return true;
    		}
    	}
    
    protected:
    	Node* _root;
    };
    
    
    void Test()
    {
    	int a[10] = { 3, 2, 8, 1, 4, 13, 15, 7, 16, 14 };
    
    	AVLTree<int, int> tree;
    
    	for (int i = 0; i < 9; i++)
    	{
    		tree.Insert(a[i], i);
    	}
    	tree.InOrder();
    	tree.IsBalance();
    }
    
    
    int main()
    {
    	Test();
    	system("pause");
    	return 0;
    }