【数据结构】AVL树

03-07 1596阅读

【数据结构】AVL树

👀樊梓慕：个人主页

 🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子，都是对生命的辜负

目录

前言

1.概念

 2.定义

3.插入

 4.旋转

4.1右单旋

原理图与实现细节 

代码实现

4.2左单旋

原理图与实现细节 

代码实现

4.3先左旋再右旋

原理图与实现细节 

代码实现

4.4先右旋再左旋

原理图与实现细节 

代码实现

4.5插入的完整代码 

5.验证

5.1验证二叉搜索特性

5.2验证平衡特性

前言

本篇文章主要与大家一起学习AVL树-平衡二叉搜索树。

我们前面学习二叉搜索树时，了解到如果插入的元素有序或者接近有序，二叉搜索树的结构就会退化成单支树甚至是链表，那么此时搜索的时间复杂度会退化，如果一个二叉搜索树可以一直保持平衡的话，那么他的时间复杂度是logN，即高度次，所以AVL树-平衡二叉搜索树的出现就是为了解决二叉搜索树不平衡的问题，从而保证搜索效率。

声明：本篇文章的图片样式取自 《Hello 算法》-github.com ，后博主根据文章内容对图片作了修改，大家感兴趣也可以了解一下这本书。

欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。 

=========================================================================

GITEE相关代码：🌟樊飞 (fanfei_c) - Gitee.com🌟

=========================================================================

1.概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查

找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

即AVL树满足以下条件：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

    比如：

    【数据结构】AVL树

     2.定义

    AVL树节点的定义：

    template
struct AVLTreeNode
{
	AVLTreeNode* _left;// 该节点的左孩子
	AVLTreeNode* _right;// 该节点的右孩子
	AVLTreeNode* _parent;// 该节点的双亲
	int _bf; // 该节点的平衡因子
	pair _kv;
	AVLTreeNode(const pair& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _kv(kv)
	{}
};

    3.插入

    那么如何用算法实现AVL树呢？

    其实AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。

    那么AVL树的插入过程可以分为两步：

    1. 按照二叉搜索树的方式插入新节点
    2. 调整节点的平衡因子

    即第一步我们就把二叉搜索树的插入代码copy一份过来，进行一定的修改：

    template
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	bool Insert(const pair& kv)
	{
/********* 普通二叉搜索树的插入 *********/
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->kv.first _right;
			}
			else if (cur->kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first _right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
/**************************************/
		return true;
	}
private:
	Node* _root = nullptr;
};

     然后第二步就是调整平衡因子，让左右子树高度之差（平衡因子）不超过1.

    当cur插入后，cur的父亲节点parent的平衡因子一定需要调整，再插入之前，parent的平衡因子分为三种情况：-1、0、1（插入之前一定满足AVL树规则），我们默认平衡因子=右子树高度-左子树高度，那么就分为以下两种情况：

    • 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可
    • 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可

      如果parent的平衡因子发生了变化，那么就证明祖先有可能会受影响，就要向上继续更新。

      这里我们同样需要分情况讨论：

      此时parent的平衡因子可能有三种情况：0，正负1， 正负2。

      • 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功，且高度没有发生变化。
      • 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新。
      • 如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行『 旋转』处理。

        我们把上述逻辑转化成代码：

        template
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	bool Insert(const pair& kv)
	{
/********* 普通二叉搜索树的插入 *********/
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->kv.first _right;
			}
			else if (cur->kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first _right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
/**************************************/
/************* 调整平衡因子 ************/
        while (parent)
		{
            // 更新双亲的平衡因子
			if(cur == parent->left)
				parent->_bf--;
			else
				parent->_bf++;
            
            // 更新后检测双亲的平衡因子
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 旋转处理
			}
			else
			{
				// 插入之前AVL树就有问题
				assert(false);
			}
		}
		return true;
	}
private:
	Node* _root = nullptr;
};

         4.旋转

        当节点的平衡因子为正负2时，则需要我们对该子树进行旋转处理。

        那旋转最重要的是不能破坏我们二叉搜索树的特性，即旋转过后依旧满足左子树小于根，根小于右子树，那么怎么样进行旋转既能让二叉搜索树保持平衡，又能保持二叉搜索树的特性呢？

        4.1右单旋

        当新节点插入到较高左子树的左侧时（左左），我们需要进行『 右单旋』操作。

        原理图与实现细节 

        一般有以下这两种情况以及对应的旋转操作：

        （1）失衡节点的左孩子没有右孩子（subL无右孩子）

        【数据结构】AVL树

        当subL无右孩子时，parent直接旋转到subL的右分支即可，我们不需要考虑subL的右孩子放到哪。

        （2）失衡节点的左孩子有右孩子（subL有右孩子subLR）

        【数据结构】AVL树

        当subL有右孩子时，parent如果旋转到subL的右孩子处，需要将subL的右孩子subLR放到旋转过来的parent节点的左分支上即可。

        体现到代码中如何判断什么时候进行右旋呢？

        观察图像得知，当parent平衡因子为-2 && cur平衡因子为-1时，进行右旋。

        观察发现，这样旋转后依然满足二叉搜索树的特性，且旋转后该树平衡了。

         那么接下来我们要进行代码实现：

        这里有几个需要注意的细节：

        • 细节1：subL是否有右孩子subLR，如果有我们需要更新subLR的双亲节点。
        • 细节2：parent是否是根节点，如果是根节点，我们需要更新根节点的值为subL；如果不是根节点，可能是某个节点的左子树，也可能是某个节点的右子树，我们需要更新subL的双亲节点为旋转之前parent双亲节点的左分支或右分支，所以我们需要提前保存parent的双亲结点ppnode。
        • 细节3：旋转结束后更新parent与subL的平衡因子为0；

          代码实现

          void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	parent->_left = subLR;
	// 细节1
	if (subLR)
		subLR->_parent = parent;
	subL->_right = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subL;
	// 细节2
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subL;
		}
		else
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	// 细节3
	subL->_bf = 0;
	parent->_bf = 0;
}

          4.2左单旋

          当新节点插入到较高右子树的右侧时（右右），我们需要进行『 左单旋』操作。

          原理图与实现细节 

          一般有以下这两种情况以及对应的旋转操作：

          （1）失衡节点的右孩子没有左孩子（subR无左孩子）

          【数据结构】AVL树

          当subR无左孩子时，parent直接旋转到subR的左分支即可，我们不需要考虑subR的左孩子放到哪。

          （2）失衡节点的右孩子有左孩子（subR有左孩子subRL）

          【数据结构】AVL树

          当subR有左孩子时，parent如果旋转到subR的左孩子处，需要将subR的左孩子subRL放到旋转过来的parent节点的右分支上即可。

          体现到代码中如何判断什么时候进行左旋呢？

          观察图像得知，当parent平衡因子为2 && cur平衡因子为1时，进行左旋。

          观察发现，这样旋转后依然满足二叉搜索树的特性，且旋转后该树平衡了。

           那么接下来我们要进行代码实现：

          这里有几个需要注意的细节：

          • 细节1：subR是否有左孩子subRL，如果有我们需要更新subRL的双亲节点。
          • 细节2：parent是否是根节点，如果是根节点，我们需要更新根节点的值为subR；如果不是根节点，可能是某个节点的左子树，也可能是某个节点的右子树，我们需要更新subR的双亲节点为旋转之前parent双亲节点的左分支或右分支，所以我们需要提前保存parent的双亲结点ppnode。
          • 细节3：旋转结束后更新parent与subR的平衡因子为0；

            代码实现

            void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	// 细节1
	if (subRL)
		subRL->_parent = parent;
	subR->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subR;
	// 细节2
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subR;
		}
		else
		{
			ppnode->_right = subR;
		}
		subR->_parent = ppnode;
	}
	// 细节3
	parent->_bf = 0;
	subR->_bf = 0;
}

            4.3先左旋再右旋

            当新节点插入到较高左子树的右侧时（左右），仅使用左旋或右旋都无法使子树恢复平衡，所以我们需要进行『 先左旋再右旋』操作。

            原理图与实现细节 

            【数据结构】AVL树

            体现到代码中如何判断什么时候进行先左旋再右旋呢？

            观察图像得知，当parent平衡因子为-2 && cur平衡因子为1时，进行先左旋再右旋。

            观察发现，这样旋转后依然满足二叉搜索树的特性，且旋转后该树平衡了。

            如果是下面这种树，你会发现会有两种不同的情况，即新插入的节点是subLR的左树还是右树，这个问题决定了最后parent和subL的平衡因子。

            • 如果是右树，如图『 节点4』，最后旋转结束，parent的平衡因子为0，subL的平衡因子为-1；
            • 如果是左树，如图『 节点2』，最后旋转结束，parent的平衡因子为1，subL的平衡因子为0；

              【数据结构】AVL树

              所以根据上面的分析，我们需要知道新插入的节点是subLR的左树还是右树.

              这个通过subLR的平衡因子就能判定：

              • 如果为1，证明插入的节点是subLR的右树，即『 节点4』，所以最终subL的平衡因子为-1，parent的平衡因子为0；
              • 如果为-1，证明插入的节点是subLR的左树，即『 节点2』，所以最终parent的平衡因子为1，subL的平衡因子为0；
              • 如果为0，则为上上面图片的情况，最终parent和subL的平衡因子都为0。

                代码实现

                void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;
	RotateL(parent->_left);
	RotateR(parent);
	if (bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

                4.4先右旋再左旋

                当新节点插入到较高右子树的左侧时（右左），仅使用左旋或右旋都无法使子树恢复平衡，所以我们需要进行『 先右旋再左旋』操作。

                原理图与实现细节 

                【数据结构】AVL树

                体现到代码中如何判断什么时候进行先右旋再左旋呢？

                观察图像得知，当parent平衡因子为2 && cur平衡因子为-1时，进行先右旋再左旋。

                观察发现，这样旋转后依然满足二叉搜索树的特性，且旋转后该树平衡了。

                如果是下面这种树，你会发现会有两种不同的情况，即新插入的节点是subRL的左树还是右树，这个问题决定了最后parent和subR的平衡因子。

                • 如果是左树，如图『 节点2』，最后旋转结束，parent的平衡因子为0，subR的平衡因子为1；
                • 如果是右树，如图『 节点4』，最后旋转结束，parent的平衡因子为-1，subR的平衡因子为0；

                  【数据结构】AVL树

                  所以根据上面的分析，我们需要知道新插入的节点是subRL的左树还是右树.

                  这个通过subRL的平衡因子就能判定：

                  • 如果为-1，证明插入的节点是subRL的左树，即『 节点2』，所以最终subR的平衡因子为1，parent的平衡因子为0；
                  • 如果为1，证明插入的节点是subRL的右树，即『 节点4』，所以最终parent的平衡因子为-1，subR的平衡因子为0；
                  • 如果为0，则为上上面图片的情况，最终parent和subR的平衡因子都为0。

                    代码实现

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

                    4.5插入的完整代码 

                    bool Insert(const pair& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->kv.first _right;
		}
		else if (cur->kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(kv);
	if (parent->_kv.first _right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;
	while (parent)
	{
		if (cur == parent->left)
		{
			parent->_bf--;
		}
		else
		{
			parent->_bf++;
		}
		if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			// 旋转处理
			if (parent->_bf == 2 && cur->_bf == 1)
			{
				RotateL(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == -1)
			{
				RotateR(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == 1)
			{
				RotateLR(parent);
			}
			else
			{
				RotateRL(parent);
			}
			break;
		}
		else
		{
			// 插入之前AVL树就有问题
			assert(false);
		}
	}
	return true;
}

                    5.验证

                    5.1验证二叉搜索特性

                    如何验证一个平衡二叉搜索树是否健康呢？

                    那是否符合二叉搜索很简单，我们只需要中序遍历一遍看看是不是有序的即可。

                    中序遍历：

                    //中序遍历
void Inorder()
{
	_Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{
	if (root == nullptr)
		return;
	_Inorder(root->_left);
	cout _kv.first _right);
}

                    创建子函数实现中序遍历的原因是：外部调用Inorder无法访问到private的根节点。

                    5.2验证平衡特性

                    验证平衡特性，我们可以获取左右子树的高度，然后利用这个高度计算差值，看看是否平衡即可。

                    首先是获取左右子树的高度：

                    int _Height(Node* root)
{
	if (root == nullptr)
		return 0;
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
    //返回左右子树高的那一个+1作为当前树的高度
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
int Height()
{
	return _Height(_root);
}

                    判断是否平衡：

                    bool _IsBalance(Node* root)
{
    if (root == nullptr)
    {
        return true;
    }
	int leftHeight = Height(root->_left);
	int rightHeight = Height(root->_right);
	if (abs(rightHeight - leftHeight) >= 2)
	{
		cout _kv.first _left, leftHeight)
		|| !_IsBalance(root->_right, rightHeight))
	{
		return false;
	}
	if (abs(rightHeight - leftHeight) >= 2)
	{
		cout _kv.first
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]