【c++】AVL树详解

雨点打透心脏的1/2处 2022-07-15 02:24 135阅读 0赞

AVL树是又叫平衡二叉搜索树，但是它不是完全平衡，只是近似平衡（高度平衡）。什么叫完全平衡？想象一下完全二叉树。

根据名字’二叉搜索树‘，我们可以知道它的一些性质：

1. 每个节点都有一个作为搜索依据的关键码（key），所有节点的关键码互不相同。

2. 左子树上所有节点的关键码（key）都小于根节点的关键码（key）。

3. 右子树上所有节点的关键码（key）都大于根节点的关键码（key）。

除此之外，它还具有一些它独特的性质来维持它的高度平衡。

1. 左子树和右子树的高度之差的绝对值不超过1

2. 树中的每个左子树和右子树都是AVL树

3. 每个节点都有一个平衡因子(balance factor--bf),任一节点的平衡因子是-1,0,1。(每个节点的平衡因子等于右子树的高度减去左子树

的高度)

AVL树有三个值，一个\_key（关键码），一个\_value（值，目前不要关心这个value是什么），一个\_bf（平衡因子）。三个指针，左

孩子指针，右孩子指针，父亲指针。由此我们便得出了AVL树的结构：

template<typename K,typename V>
    struct AVLTreeNode
    {
    	K _key;
    	V _value;
    
    	AVLTreeNode<K, V>* _left;
    	AVLTreeNode<K, V>* _right;
    	AVLTreeNode<K, V>* _parent;
    
    	int _bf;
    
    	AVLTreeNode(const K& key, const V& value)
    		:_key(key)
    		,_value(value)
    		,_bf(0)
    		, _left(NULL)
    		, _right(NULL)
    		, _parent(NULL)
    	{}
    };

搞懂AVL树的结构并不难，难点在于如何去维护这个结构，并用代码写出来。当我们对一棵AVL树插入一个结点的时候，我们很容易

就破坏了它高度平衡的结构（从前文我们可 以知道，我们可以拿平衡因子来判断一棵树是否平衡，当一个结点的平衡因子bf 等于-2

或者2时，这个树便不再平衡。）所以我们需 要做一些工作去调整插入新结点后的AVL 树。

对下图中出现的符号做一些备注：\_bf - - - - 平衡因子

a，b，c，d - - - - 子树，若一个为空，都为空。若一个不为空，则都不为空，并且都平衡且满足AVL树。

parent - - - - 祖先结点，因为我们不确定根结点在哪里，所以用parent统一概括祖先结点。

①**左单旋**，对应插入情况如图所示，当在子树c上插入一个新结点。此时子树c 的高度变为h+1，子树b的高度为h。结点5的bf变为

1，结点3的bf变为2。此树不再平衡。

![SouthEast][]

**什么叫左单旋？**让结点3和结点5以及它们之间的连线为基准，进行逆时针旋转。具体操作为，将结点5的左子树b变为结点3的右子

树，将结点3以及其子树变为结点5的左子树。

完成一次左单旋。结果我们可以看到结点3的\_bf与结点5的\_bf都变为0，AVL树变为平衡。

![SouthEast 1][]

②**右单旋**，对应的新结点插入位置如图所示，当在子树a的下面入一个结点时，结点3的\_bf左子树高度为h+1，右子树高度为h，平衡

因子\_bf变为-1,。结点5的左子树高度变为h+2，右子树高度为h，平衡因子\_bf变为-2。AVL树不再平衡。

![SouthEast 2][]

**什么叫右单旋？**同上，以结点5和结点3以及它们之间的连线为基准，进行顺时针旋转。具体操作为，将结点5的左子树变为结点3的

右子树，将结点3以及其子树变为结点5的左子树，将parent指向结点3。完成一次右单旋，完成后我们可以看到结点3与结点5的平衡

因子\_bf变为0，AVL树恢复平衡。

![SouthEast 3][]

③**左右双旋**，当我们理解了左单旋与右单旋后，理解左右双旋就简单的多了。其插入情况如图所示（PS：插到子树b上与插到子树c

会导致结点4的平衡因子\_bf不同，属于是不同的情况。这里以插到子树b下为例，另一种情况与其类似。），当在子树b下插入一个

结点时，结点4的平衡因子\_bf变为-1，结点3的平衡因子\_bf变为1，结点5的平衡因子\_bf变为-2。AVL树不再平衡。

![SouthEast 4][]

**什么么叫左右双旋？**很简单啦！先左单旋，再右单旋！不过两次的对象不同。先对结点3和结点4进行左单旋。

![SouthEast 5][]

再对结点5与结点4进行右单旋。

![SouthEast 6][]

最后结点4的平衡因子\_bf变为0，结点3的平衡因子\_bf变为0，j结点5的平衡因子\_bf变为1。AVL树恢复平衡。

④**右左单旋**，其插入情况如图所示（PS：插到子树b上与插到子树c会导致结点4的平衡因子\_bf不同，属于是不同的情况。这里以插

到子树c下为例，另一种情况与其类似。），当在子树b下插入一个结点时，结点3的平衡因子\_bf变为1，结点5的平衡因子\_bf变

为-1，结点4的平衡因子\_bf变为2。AVL树不再平衡。

![SouthEast 7][]

**什么叫右左双旋呢？**哈哈，相信聪明的你已经知道了。先对结点5与结点3进行右单旋。

![SouthEast 8][]

再对结点3与结点4进行左单旋。

![SouthEast 9][]

旋转完成后结点5的平衡因子\_bf变为0，结点4的平衡因子\_bf变为-1，结点3的平衡因子\_bf变为0。AVL树恢复平衡。

以上4中旋转就囊括所有的插入情况与调整情况了，掌握这些，写代码就简单了。

先看**左单旋代码**，将上面左单旋的图类比成下面这副。结点3类比为结点parent，结点5类比结点subR，子树b类比为subRL，

ppNode为祖先结点，即parent的parent。

![SouthEast 10][]

代码即为：

void RotateL(Node* parent)
    {
    	Node* subR = parent->_right;//subR为parent结点的左孩子。
    	Node* subRL = subR->_left;//subRL为subR的左孩子
    	parent->_right = subRL;// 将subRL变为parent的右子树
    
    	if (subRL)//若sunRL不为空，则设置它的父亲指针，否则则不设置。
    	{
    		subRL->_parent = parent;
    	}
    	Node* ppNode = parent->_parent;//记录parent的父亲结点，即祖先结点
    
    	//将parent变为subR的左子树，并设置父亲指针。
    	subR->_left = parent;
    	parent->_parent = subR;
    
    	//设置ppNode，若不为空，则将其指向subR
    	if (ppNode)
    	{
    		//判断parent是ppNode的左孩子还是右孩子，以方便设置subR的父亲结点。
    		if (ppNode->_left == parent)
    			ppNode->_left = subR;
    		else
    			ppNode->_right = subR;
    		subR->_parent = ppNode;
    	}
    	else//若其为空，则代表parent原来为根节点，则旋转后subR变为根节点。
    	{
    		subR->_parent = NULL;
    		_root = subR;
    	}
    	//设置平衡因子，置0。
    	subR->_bf = parent->_bf = 0;
    }

**右单旋代码**，类比图如下，结点5类比为结点parent，结点3类比为结点subL，子树b类比为subLR。ppNode为祖先结点。

![SouthEast 11][]

代码即为：

void RotateR(Node* parent) //对照左单旋的代码注释进行阅读
    {
    	Node* subL = parent->_left;
    	Node* subLR = subL->_right;
    	parent->_left = subLR;
    	if (subLR)
    	{
    		subLR->_parent = parent;
    	}
    
    	Node* ppNode = parent->_parent;
    
    	subL->_right = parent;
    	parent->_parent = subL;
    
    	if (ppNode)
    	{
    		if (ppNode->_left == parent)
    			ppNode->_left = subL;
    		else
    			ppNode->_right = subL;
    		subL->_parent = ppNode;
    	}
    	else
    	{
    		subL->_parent = NULL;
    		_root = subL;
    	}
    	subL->_bf = parent->_bf = 0;
    }

**左右单旋代码**，类比图如下，类比规则与上相同。从上面两段代码中可以看到，我在最后对平衡因子\_bf进行了调整。细心的同学可

以注意到，我在上面说过新结点插入子树b下与插入子树c下是两种不同的情况。这里得到了体现。插入的不同影响到了最后平衡因

子的调整的不同。

①插入子树b下

![SouthEast 12][]

②插入子树c下

![SouthEast 13][]

仔细观察上面两幅图，我们会看到，无论新结点插入到哪里，

1、结点subLR的左子树b都变成了结点subL的右子树；

2、结点subRL的右子树c都变成了结点parent的左子树；

3、平衡因子的计算公式为，\_bf = 右子树高度-左子树高度；

通过这三点，我们可以概括一下了，

①旋转前，新结点插到子树b下，\_bf(subLR) = Hc(h-1) - Hb(h-1+1) = -1。旋转后，\_bf(subL) = Hb(h-1+1) - Ha(h) = 0，\_bf(parent) =

Hd(h) - Hc(h-1) = 1,\_bf(sunLR) = 0。

②旋转前，新结点插到子树c下，\_bf(subLR) = Hc(h-1+1) - Hb(h-1) = 1。旋转后，\_bf(subL) = Hb(h-1) - Ha(h) = -1，\_bf(parent) =

Hd(h) - Hc(h-1+1) = 0,\_bf(sunLR) = 0。

③为什么会出现第三种情况呢？？？？不要忘了子树a、b、c、d都为空的情况。当其都为空时，ppNode为空，parent为根节点。此

时subLR就变成了插入的新结点。示意图如下。旋转前\_bf(sunRL) = 0，旋转后，\_bf(suBL) = 0，\_bf(parent) = 0。

![SouthEast 14][]

以上三种情况概括下来就是：

![SouthEast 15][]

到这里，就可以写代码了，因为已经写出了左单旋与右单旋代码，所以在双旋时我们可以复用这些代码。

void RotateLR(Node* parent)
    {
    	Node* SubL = parent->_left;
    	Node* SubLR = SubL->_right;
    	int bf = SubLR->_bf;//记录旋转前subLR的平衡因子
    	//左右双旋
    	RotateL(parent->_left);//  复用代码，先左单旋
    	RotateR(parent);//  复用代码，再右单旋
    
    	//三种情况
    	if (bf == 0)
    	{
    		parent->_bf = SubL->_bf = 0;
    		SubLR->_bf = 0;
    	}
    	else if (bf == -1)
    	{
    		SubL->_bf = 0;
    		parent->_bf = 1;
    		SubLR->_bf = 0;
    	}
    	else
    	{
    		SubL->_bf = 1;
    		parent->_bf = 0;
    		SubLR->_bf = 0;
    	}
    
    }

右左双旋与左右双旋就一样了，同样的类比，同样的三种情况①子树b②子树c③子树a、b、c、d都为空。这里只给出插入子树b下的

类比图。

![Image 1][]

![20161030102258634][]

三种情况平衡因子的总结：

![20161030102343344][]

右左旋代码：

void RotateRL(Node* parent)
    {
    	Node* SubR = parent->_right;
    	Node* SubRL = SubR->_left;
    	int bf = SubRL->_bf;//记录旋转前subRL的平衡因子
    	//
    	RotateR(SubR);//复用代码，先右旋
    	RotateL(parent);//复用代码，后左旋
    
    	//调整平衡因子
    	//三种情况
    	if (bf == 0)
    	{
    		SubR->_bf = parent->_bf = 0;
    	}
    	else if (bf == 1)
    	{
    		SubR->_bf = 0;
    		parent->_bf = -1;
    	}
    	else
    	{
    		SubR->_bf = 1;
    		parent->_bf = 0;
    	}
    	SubRL->_bf = 0;
    }

以上，我们就已经讲完了它的调整算法。

AVL树的核心算法就是当AVL树平衡被破坏时，如何去调整并让它恢复平衡。这也是整个AVL树知识的重点与难点，面试时极大可能

性被问到，如果你很完美的把它答了上来，恭 喜你，面试官已经给你加分了。所以赶紧搞定它吧 ！

思考：当我们已经构建好了一棵AVL树，我们如何去检查它是否正确呢？（我给出代码，大家自己研究）

//递归检查AVL树是或否正确。
    bool _IsAVLTree(Node *root, int &Height)
    {
    	if (root == NULL)
    	{
    		Height = 0;
    		return true;
    	}
    
    	//检查左子树
    	int leftHeight = 0;
    	if (_IsAVLTree(root->_left, leftHeight) == false)
    	{
    		return false;
    	}
    	//检查右子树
    	int rightHeight = 0;
    	if (_IsAVLTree(root->_right, rightHeight) == false)
    	{
    		return false;
    	}
    	//计算高度
    	Height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    
    	//检查当前结点
    	return abs(leftHeight - rightHeight) < 2;
    }

完成的AVL树代码：

头文件 AVLTree.h

#pragma once
    #include<iostream>
    using namespace std;
    
    template<typename K,typename V>
    struct AVLTreeNode
    {
    	K _key;
    	V _value;
    
    	AVLTreeNode<K, V>* _left;
    	AVLTreeNode<K, V>* _right;
    	AVLTreeNode<K, V>* _parent;
    
    	int _bf;
    
    	AVLTreeNode(const K& key, const V& value)
    		:_key(key)
    		,_value(value)
    		,_bf(0)
    		, _left(NULL)
    		, _right(NULL)
    		, _parent(NULL)
    	{}
    };
    
    template<typename K, typename V>
    class AVLTree
    {
    	typedef AVLTreeNode<K, V> Node;
    public:
    	AVLTree()
    		:_root(NULL)
    	{}
    	bool Insert(const K& k, const V& v)
    	{
    		if (_root == NULL)
    		{
    			_root = new Node(k, v);
    			return true;
    		}
    		Node* cur = _root;
    		Node* parent = NULL;
    		while (cur)
    		{
    			if (k > cur->_key)
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (k < cur->_key)
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else
    			{
    				return false;
    			}
    		}
    
    
    		cur = new Node(k, v);
    		if (k > parent->_key)
    		{
    			parent->_right = cur;
    			cur->_parent = parent;
    		}
    		else
    		{
    			parent->_left = cur;
    			cur->_parent = parent;
    		}
    
    		//调整平衡因子
    		while (parent)
    		{
    			//如果cur左右不为空且平衡因子为0，则parent的平衡因子不用改变。
    			if (cur->_bf == 0&&cur->_left!= NULL&&cur->_right!= NULL)
    			{
    				break;
    			}
    
    			if (parent->_left == cur)
    			{
    				parent->_bf--;
    			}
    			else
    			{
    				parent->_bf++;
    			}
    			if (parent->_bf == 2 || parent->_bf == -2)
    			{
    				break;
    			}
    			cur = parent;
    			parent = cur->_parent;
    		}
    
    		if (parent == NULL)
    		{
    			return true;
    		}
    		//旋转
    		if (parent->_bf == 2)
    		{
    			if (cur->_bf == 1)
    			{
    				RotateL(parent);
    			}
    			else if (cur->_bf == -1)
    			{
    				RotateRL(parent);
    			}
    		}
    		else
    		{
    			if (cur->_bf == -1)
    			{
    				RotateR(parent);
    			}
    			else if (cur->_bf == 1)
    			{
    				RotateLR(parent);
    			}
    		}
    	}
    
    	//判断一棵树是否是平衡二叉树
    	bool IsAVLTree()
    	{
    		int Height = 0;
    		return _IsAVLTree(_root,Height);
    	}
    
    	void InOrder()
    	{
    		_InOrder(_root);
    		cout << endl;
    	}
    protected:
    	void RotateR(Node* parent)
    	{
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    		parent->_left = subLR;
    		if (subLR)
    		{
    			subLR->_parent = parent;
    		}
    
    		Node* ppNode = parent->_parent;
    
    		subL->_right = parent;
    		parent->_parent = subL;
    
    		if (ppNode)
    		{
    			if (ppNode->_left == parent)
    				ppNode->_left = subL;
    			else
    				ppNode->_right = subL;
    			subL->_parent = ppNode;
    		}
    		else
    		{
    			subL->_parent = NULL;
    			_root = subL;
    		}
    		subL->_bf = parent->_bf = 0;
    	}
    	void RotateL(Node* parent)
    	{
    		Node* subR = parent->_right;//subR为parent结点的左孩子。
    		Node* subRL = subR->_left;//subRL为subR的左孩子
    		parent->_right = subRL;// 将subRL变为parent的右子树
    
    		if (subRL)//若sunRL不为空，则设置它的父亲指针，否则则不设置。
    		{
    			subRL->_parent = parent;
    		}
    
    		Node* ppNode = parent->_parent;//记录parent的父亲结点，即祖先结点
    
    		//将parent变为subR的左子树，并设置父亲指针。
    		subR->_left = parent;
    		parent->_parent = subR;
    
    		//设置ppNode，若不为空，则将其指向subR
    		if (ppNode)
    		{
    			//判断parent是ppNode的左孩子还是右孩子，以方便设置subR的父亲结点。
    			if (ppNode->_left == parent)
    				ppNode->_left = subR;
    			else
    				ppNode->_right = subR;
    			subR->_parent = ppNode;
    		}
    		else//若其为空，则代表parent原来为根节点，则旋转后subR变为根节点。
    		{
    			subR->_parent = NULL;
    			_root = subR;
    		}
    		//设置平衡因子，置0。
    		subR->_bf = parent->_bf = 0;
    	}
    	void RotateRL(Node* parent)
    	{
    		Node* SubR = parent->_right;
    		Node* SubRL = SubR->_left;
    		int bf = SubRL->_bf;//记录旋转前subRL的平衡因子
    		//
    		RotateR(SubR);//
    		RotateL(parent);
    
    		//调整平衡因子
    		//三种情况
    		if (bf == 0)
    		{
    			SubR->_bf = parent->_bf = 0;
    		}
    		else if (bf == 1)
    		{
    			SubR->_bf = 0;
    			parent->_bf = -1;
    		}
    		else
    		{
    			SubR->_bf = 1;
    			parent->_bf = 0;
    		}
    		SubRL->_bf = 0;
    	}
    	void RotateLR(Node* parent)
    	{
    		Node* SubL = parent->_left;
    		Node* SubLR = SubL->_right;
    		int bf = SubLR->_bf;//记录旋转前subLR的平衡因子
    		//左右双旋
    		RotateL(parent->_left);//  先左单旋
    		RotateR(parent);//  再右单旋
    		
    		//三种情况
    		if (bf == 0)
    		{
    			parent->_bf = SubL->_bf = 0;
    			SubLR->_bf = 0;
    		}
    		else if (bf == -1)
    		{
    			SubL->_bf = 0;
    			parent->_bf = 1;
    			SubLR->_bf = 0;
    		}
    		else
    		{
    			SubL->_bf = 1;
    			parent->_bf = 0;
    			SubLR->_bf = 0;
    		}
    		
    	}
    	void _InOrder(Node* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_InOrder(root->_left);
    
    		cout << root->_key << " ";
    
    		_InOrder(root->_right);
    	}
    	int _Height(Node* root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		int left = _Height(root->_left) + 1;
    		int right = _Height(root->_right) + 1;
    		
    		return left > right ? left : right;
    	}
    	bool _IsAVLTree(Node *root, int &Height)
    	{
    		if (root == NULL)
    		{
    			Height = 0;
    			return true;
    		}
    
    		int leftHeight = 0;
    		if (_IsAVLTree(root->_left, leftHeight) == false)
    		{
    			return false;
    		}
    		int rightHeight = 0;
    	    if (_IsAVLTree(root->_right, rightHeight) == false)
    		{
    			return false;
    		}
    
    		Height = leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    
    		return abs(leftHeight - rightHeight) < 2;
    	}
    protected:
    	Node* _root;
    };
    
    void Test()
    {
    	AVLTree<int, int> tree;
    	int a[9] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    	//int a[3] = { 3, 14, 2 };
    	for (int i = 0; i < 9; i++)
    	{
    		tree.Insert(a[i], i);
    	}
    	tree.InOrder();
    	cout << "IsAVLTree?" << tree.IsAVLTree() << endl;
    
    	int b[10] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    	AVLTree<int, int> tree1;
    	for (int i = 0; i < 10; i++)
    	{
    		tree1.Insert(b[i], i);
    	}
    	tree1.InOrder();
    	cout <<"IsAVLTree?"<< tree1.IsAVLTree() << endl;
    
    
    }

test.cpp

#include"AVLTree.h"
    
    int main()
    {
    	Test();
    	system("pause");
    	return 0;
    }

[SouthEast]: /images/20220715/fb59ce035f3140fcaa427b153a631db8.png
[SouthEast 1]: /images/20220715/836e250d34f549d6a561e2a9eb8aa492.png
[SouthEast 2]: /images/20220715/db1a751935bb449bb5f52981a739477b.png
[SouthEast 3]: /images/20220715/6ae3acd2e52f4f07b6cdb2fc5286c8ab.png
[SouthEast 4]: /images/20220715/41f529b995f246ac95810db50e5cb915.png
[SouthEast 5]: /images/20220715/0a482d75d3a2470eb15951ce80f10534.png
[SouthEast 6]: /images/20220715/fed88491a1034e2fbab664c81fef55c0.png
[SouthEast 7]: /images/20220715/35c5f50d880343308627fa28066ad45c.png
[SouthEast 8]: /images/20220715/99b6a24e3b8f483b9eabc3cbe801d059.png
[SouthEast 9]: /images/20220715/d2c5c3e104df42898d441ce61abd846f.png
[SouthEast 10]: /images/20220715/867e58bf691b49df8cf171208995a5b1.png
[SouthEast 11]: /images/20220715/8a3d2380ff2c4c4395a0aedf171164a4.png
[SouthEast 12]: /images/20220715/010305f7a4004f96bb007819f79e7179.png
[SouthEast 13]: /images/20220715/6c39fcd8437b4b4b969421c451c2d578.png
[SouthEast 14]: /images/20220715/304626df19204f5c9f398a2306b94bfc.png
[SouthEast 15]: /images/20220715/5812cd9c4ad2436aa09e9ffb424547f2.png
[Image 1]: 
[20161030102258634]: /images/20220715/bab56fce4e9d42f8ab65573f8972b574.png
[20161030102343344]: /images/20220715/ce791e0e790840779aa4a76de0b3cc47.png