二叉搜索树：AVL平衡

文章目录

  • 一、 二叉搜索树
    • 1.1 概念
    • 1.2 操作
    • 1.3 代码实现
  • 二、二叉搜索树的应用
    • K模型和KV模型
  • 三、二叉搜索树的性能分析
  • 四、AVL树
    • 4.1 AVL树的概念
    • 4.2 AVL树的实现原理
    • 4.3 旋转
    • 4.4 AVL树最终代码

一、 二叉搜索树

1.1 概念

二叉搜索树（ Binary Search Tree，BST ）是一种特殊的二叉树，它可以是空树，也可以是满足以下性质的一颗二叉树：

  • 若左子树不为空，左子树中所有节点的键值都小于根节点的值。
  • 若右子树不为空，右子树中所有节点的键值都大于根节点的值。
  • 左右子树也分别为二叉搜索树。

因此，二叉搜索树的中序遍历结果是一个有序序列。这个特性使得二叉搜索树在搜索、插入和删除操作时具有高效性能。

1

📝二叉搜索树的结构示意图

1.2 操作

⭕ 对如下二叉搜索树进行操作

在这里插入图片描述

  1. 查询

🔎假设要查询key值是否存在于二叉树中

  • 从根节点开始，key比当前节点的键值大，则往右继续找；key比当前节点的键值小，则往左继续找。
  • 若当前节点为空时还没找到，则key值不存在。

在这里插入图片描述

  1. 插入

1️⃣若树为空，则直接新增节点，作为该树的根节点
2️⃣若树不为空，则按二叉搜索树查询规则找到插入位置，再建立与父节点的链接关系。

在这里插入图片描述

  1. 删除

二叉搜索树的删除某个节点后，要想继续保持二叉搜索树的特性，需要进行一些调整。这里分三种情况。

假设将要删除node节点

1️⃣ 若node没有子树，即node为叶子节点，那么直接删除即可。

在这里插入图片描述

2️⃣ 若node左右子树有一边为空一边非空，则需“托孤”，即把非空一边的子树托付给node父节点。

在这里插入图片描述

3️⃣ 若node左右子树都存在，则需在左子树中找到最大节点（或在右子树中找到最小节点）来替代node，然后在左子树（或右子树）中删除node。

观察二叉搜索树的中序遍历序列，可见进行上述操作后，中序遍历序列依然有序，二叉搜索树保持其特性。

在这里插入图片描述
在这里插入图片描述

💡替换node后，在左子树（或右子树）中删除node，这样做还有一个好处：

因为node是与左子树中最大节点（或右子树中最小节点）替换后，所以替换后的node一定没有右子树（或左子树），因此在这种情况下删除node，必然是删除节点的1️⃣或2️⃣情况，避免了重复3️⃣情况删除而进入死循环。

1.3 代码实现

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

// 二叉搜索树的节点
template <class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Self;

	Self* _pleft;
	Self* _pright;
	K _key;

	BSTreeNode(const K& key)
		:_key(key)
		,_pleft(nullptr)
		,_pright(nullptr)
	{}
};

// 二叉搜索树
template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
	typedef BSTreeNode<K>* pNode;

public:
	// constructor
	BSTree()
		:_root(nullptr)
	{}

	// destructor
	~BSTree()
	{
		_destroy(_root);
	}

	// 中序遍历
	void Inorder()
	{
		_inorder(_root);
		cout << endl;
	}
	
	// 插入
	bool Insert(const K& key)
	{
		// 空树
		if(_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		// 不为空树，要先找到插入位置
		else
		{
			pNode cur = _root;
			pNode parent = nullptr;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_pright;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_pleft;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(key);
			if (cur->_key > parent->_key)
				parent->_pright = cur;
			else
				parent->_pleft = cur;

			return true;
		}
	}
	
	// 删除
	void Erase(const K& key)
	{
		_erase(_root, key);
	}


private:
	pNode _root;

	void _inorder(pNode root)
	{
		if (root == nullptr)
			return;

		_inorder(root->_pleft);
		cout << root->_key << " ";
		_inorder(root->_pright);
	}

	void _destroy(pNode root)
	{
		if (root == nullptr)
			return;

		_destroy(root->_pleft);
		_destroy(root->_pright);
		delete root;
	}

	bool _erase(pNode& root, const K& key)
	{
		// 先找到key值的节点
		pNode cur = root;
		pNode parent = nullptr;
		
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_pright;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_pleft;
			}
			else // 相等，找到了
				break;
		}
		if (cur == nullptr) // 查无key值节点
			return false;


		// 1. cur左右至少有一个空（1️⃣、2️⃣情况）
		if (cur->_pleft == nullptr || cur->_pright == nullptr)
		{
			pNode child = cur->_pleft;
			if (child == nullptr)
				child = cur->_pright;

			// cur为根
			if (cur == root)
			{
				root = child;
			}
			// cur不为根
			else
			{
				if (cur == parent->_pleft)
				{
					parent->_pleft = child;
				}
				else
				{
					parent->_pright = child;
				}
			}
			delete cur;
			cur = nullptr;
		}

		// 2. cur左右都非空（3️⃣情况）
		else
		{
			//(1)找到右边最小(也可以是左边最大，通常小的离根较近，我们选用右边最小)的节点代替cur
			pNode minRight = cur->_pright;
			while (minRight->_pleft)
			{
				minRight = minRight->_pleft;
			}
			swap(cur->_key, minRight->_key);

			//(2)转换为在cur的右子树删除minRight节点
			_erase(cur->_pright, minRight->_key); // 此时一定是1️⃣或2️⃣情况
		}
		return true;
	}
};

💡 _erase函数root参数设为引用的妙处在cur为根时，体现为以下两种情况相同处理

在这里插入图片描述

1. _erase(_root, key);
在这里插入图片描述
2. _erase(cur->_pright(或cur->_pleft), minRight->_key);
在这里插入图片描述

二、二叉搜索树的应用

K模型和KV模型

  1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
    的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树，在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

  1. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方
    式在现实生活中非常常见

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

在这里插入图片描述

💬KV模型的代码实现:

// KV型
template <class K, class V>
struct BSTreeNode
{
	typedef BSTreeNode<K, V> Self;
	Self* _pleft;
	Self* _pright;
	K _key;
	V _val;

	BSTreeNode(const K& key, const V& val)
		: _key(key)
		, _val(val)
		, _pleft(nullptr)
		, _pright(nullptr)
	{}
};

template <class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
	typedef BSTreeNode<K, V>* pNode;

public:
	//constructor
	BSTree()
		:_root(nullptr)
	{}

	//destructor
	~BSTree()
	{
		_destroy(_root);
	}

	void Inorder()
	{
		_inorder(_root);
		cout << endl;
	}

	bool Insert(const K& key,const V& val)
	{
		// 空树
		if (_root == nullptr)
		{
			_root = new Node(key, val);
			return true;
		}
		// 不为空树，要先找到插入位置
		else
		{
			pNode cur = _root;
			pNode parent = nullptr;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_pright;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_pleft;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(key, val);
			if (cur->_key > parent->_key)
				parent->_pright = cur;
			else
				parent->_pleft = cur;

			return true;
		}
	}

	void Erase(const K& key)
	{
		_erase(_root, key);
	}

	pNode Find(const K& key)
	{
		pNode cur = _root;
		while (cur)
		{
			if (key > cur->_key)
			{
				cur = cur->_pright;
			}
			else if (key < cur->_key)
			{
				cur = cur->_pleft;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
private:
	pNode _root;

	void _inorder(pNode root)
	{
		if (root == nullptr)
			return;

		_inorder(root->_pleft);
		cout << root->_key << ":" << root->_val << endl;
		_inorder(root->_pright);
	}

	void _destroy(pNode root)
	{
		if (root == nullptr)
			return;

		_destroy(root->_pleft);
		_destroy(root->_pright);
		delete root;
	}

	bool _erase(pNode& root, const K& key)
	{
		// 先找到key值的节点
		pNode cur = root;
		pNode parent = nullptr;

		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_pright;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_pleft;
			}
			else // 相等，找到了
				break; 
		}
		if (cur == nullptr) // 查无key值节点
			return false;


		// 1. cur左右至少有一个空
		if (cur->_pleft == nullptr || cur->_pright == nullptr)
		{
			pNode child = cur->_pleft;
			if (child == nullptr)
				child = cur->_pright;

			// cur为根
			if (cur == root)
			{
				root = child;
			}
			// cur不为根
			else
			{
				// cur左右都为空
				if (child == nullptr)
				{
					if (parent->_pleft->_key == cur->_key)
					{
						parent->_pleft = nullptr;
					}
					else
					{
						parent->_pright = nullptr;
					}
				}
				// cur左右只有一个为空，不为空的为child
				else
				{
					if (child->_key < parent->_key)
					{
						parent->_pleft = child;
					}
					else
					{
						parent->_pright = child;
					}
				}
				if (cur == parent->_pleft)
				{
					parent->_pleft = child;
				}
				else
				{
					parent->_pright = child;
				}
			}
			delete cur;
			cur = nullptr;
		}

		//2. cur左右都非空
		else
		{
			//找到右边最小的节点代替cur
			pNode minRight = cur->_pright;
			while (minRight->_pleft)
			{
				minRight = minRight->_pleft;
			}
			swap(cur->_key, minRight->_key);

			//转换为在cur的右子树删除minRight节点
			_erase(cur->_pright, minRight->_key);
		}
		return true;
	}
};

三、二叉搜索树的性能分析

💭 二叉搜索树的插入、删除等操作，时间大部分都花费在查找节点上了。因此分析二叉搜索树的性能，主要看查找的性能。

假设二叉树有N个节点

在这里插入图片描述

如图是最优情况下的查找，该二叉搜索树接近完全二叉树，此时查找节点的时间复杂度是O(logN)

在这里插入图片描述
*但也有上图所示的极端情况，有序插入节点后，二叉搜索树退化为单支，这种情况是最差情况，查找节点的时间复杂度为O(N)

💭 二叉搜索树退化为接近单支树时，其效率和性能就失去了。为了解决这个问题，使二叉搜索树始终保持最优情况，我们可以将二叉搜索树改造为AVL树和红黑树。下文分析AVL树。

四、AVL树

4.1 AVL树的概念

💭二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

能满足这种特性的树称为AVL树

⭕一颗AVL树可以是一棵空树，也可以是有以下性质的一棵二叉搜索树：

  • 它的左右子树都是AVL树
  • 左右子树高度差（简称平衡因子）的绝对值不超过1

在这里插入图片描述

AVL树是一棵高度平衡的树。一棵n个节点的AVL树的高度为O(logn)，查找的时间复杂度为O(logn)。

⭕定义

// AVL树的节点
template <class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& val)
		:_val(val)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}

	AVLTreeNode* _left; // 左指针
	AVLTreeNode* _right; // 右指针
	AVLTreeNode* _parent; // 双亲指针
	T _val;
	int _bf;// 平衡因子
};

// AVL树
template <class T>
class AVLTree
{
	typedef AVLTreeNode<T> node;
	typedef AVLTreeNode<T>* ptr;

public:
	AVLTree()
		:_root(nullptr)
	{}

	bool insert(const T& val);

private:
	ptr _root;
};

4.2 AVL树的实现原理

💭AVL树的原理主要体现在插入时要通过对节点的调节，以保证每个节点的左右子树高度差绝对值不超过1（即平衡因子不超过1）。插入后，分为以下三种情况。

默认平衡因子 = 右子树高度 - 左子树高度

  1. 插入后，父节点的平衡因子变为0

在这里插入图片描述

  1. 插入后，父节点的平衡因子变为1或-1

在这里插入图片描述

  1. 插入后，父节点的平衡因子变为2或-2

在这里插入图片描述

那么这里的旋转到底是怎么一回事？见后文详细分析。

📃 先搭建AVL树insert插入函数定义的大致框架

bool insert(const T& val)
	{
		// 先按二叉搜索树规则，找到插入位置
		ptr cur = _root;
		ptr parent = nullptr;

		while (cur)
		{
			if (val < cur->_val)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (val > cur->_val)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				// 相同元素不能插入
				return false;
			}
		}

		// 创建新节点并插入
		cur = new node(val);

		// 若根为空，直接把cur作根
		if (_root == nullptr)
		{
			_root = cur;
			return true;
		}
		else
		{
			if (cur->_val < parent->_val)
			{
				parent->_left = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
		}


		// 更新平衡因子
		while (parent)
		{
			if (cur == parent->_left)
			{
				(parent->_bf)--;
			}
			else
			{
				(parent->_bf)++;
			}

			// 1.parent的_bf更新后为0
			if (parent->_bf == 0)
			{
				// 插入成功
				break;
			}

			// 2.parent的_bf更新后为1或-1，此时需要继续向上更新平衡因子
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//持续往上更新
				cur = parent;
				parent = parent->_parent;
			}

			// 3.parent的_bf更新后为2或-2，此时需要旋转，旋转后以parent为根的子树为平衡二叉树，不需要在继续向上更新平衡因子
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 旋转...
				break;
			}
		}
		return true;
	}

4.3 旋转

🔎如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。这种调整称之为旋转。根据节点插入位置的不同，AVL树的旋转分为四种：

  1. 左左 —— 右单旋

在这里插入图片描述
为什么能这样旋转？

  • b在20的左子树，肯定比20小，故能作20的左子树
  • 20和b都人于10，故以20为根的子树能作10的右子树

💬 代码实现

在这里插入图片描述

	// 左左--右单旋
	void RotateR(ptr pParent)
	{
		ptr subL = pParent->_left;
		ptr subLR = subL->_right;
		ptr ppParent = pParent->_parent;

		//建立新的链接关系
		
		//1.pParent(父)和subLR(子)
		pParent->_left = subLR;
		if (subLR)
			subLR->_parent = pParent;

		//2.subL(父)和pParent(子)
		subL->_right = pParent;
		pParent->_parent = subL;

		//3.ppParent(父)和subL(子)
		if (pParent == _root)
		{
			_root = subL;
		}
		else
		{
			if (ppParent->_left == pParent)
			{
				ppParent->_left = subL;
			}
			else
			{
				ppParent->_right = subL;
			}
		}
		subL->_parent = ppParent;

		//4.更新平衡因子
		subL->_bf = pParent->_bf = 0;
	}
  1. 右右 —— 左单旋
    在这里插入图片描述

💬 代码实现

在这里插入图片描述

// 右右--左单旋
	void RotateL(ptr pParent)
	{
		ptr subR = pParent->_right;
		ptr subRL = subR->_left;
		ptr ppParent = pParent->_parent;

		pParent->_right = subRL;
		if (subRL)
			subRL->_parent = pParent;

		subR->_left = pParent;
		pParent->_parent = subR;

		if (pParent == _root)
		{
			_root = subR;
		}
		else
		{
			// 是否可以用函数参数引用 ptr& pParent 优化？
			//if (subR->_val < ppParent->_val)
			if (ppParent->_left == pParent)
			{
				ppParent->_left = subR;
			}
			else
			{
				ppParent->_right = subR;
			}
		}
		subR->_parent = ppParent;

		subR->_bf = pParent->_bf = 0;
	}
  1. 左右 —— 左右双旋

在这里插入图片描述

🔎我们可以复用RotateL（左单旋）和RotateR（右单旋）来实现右左双旋，但需要注意的是，这两个函数会把平衡因子直接更新为0，但是观察右左双旋的过程图，发现结果所更新节点的平衡因子不全为0。因此，右左双旋要自己更新平衡因子，不能依赖于RotateL和RotateR。

  • 当在c子树插入新节点时，旋转后的结果

在这里插入图片描述

  • 当在b子树插入新节点时，旋转后的结果
    在这里插入图片描述

  • 特殊情况，当h==0时，30的右子树为空，60就是新插入节点。最终平衡因子全为0。
    在这里插入图片描述

💬 代码实现

在这里插入图片描述
🔎通过上两张图可以发现，当在c子树插入时，最终subL指向节点的平衡因子为-1，其他两个为0；当在b子树插入时，最终pParent指向节点的平衡因子为1，其他两个为0。因此，判断在哪颗树插入时决定最终如何更新平衡因子的关键，而插入后且调整前的subLR的平衡因子就可以判断。插入后且调整前，若subLR的平衡因子为1，则是在c子树插入；若subLR的平衡因子为-1，则是在b子树插入。还有h==0的特殊情况，此时subLR的平衡因子为0，作特殊处理。

	void RotateLR(ptr pParent)
	{
		ptr subL = pParent->_left;
		ptr subLR = subL->_right;
		int bf = subLR->_bf; // 保存插入后调整前subLR的平衡因子

		// 两次旋转
		RotateL(subL);
		RotateR(pParent);

		// 更新平衡因子
		if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			pParent->_bf = 0;
		}
		else if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			pParent->_bf = 1;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			pParent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
  1. 右左 —— 右左双旋
    在这里插入图片描述
  • 当在c子树插入新节点时，旋转后的结果

在这里插入图片描述

  • 当在b子树插入新节点时，旋转后的结果
    在这里插入图片描述

💬代码实现

在这里插入图片描述

	void RotateRL(ptr pParent)
	{
		ptr subR = pParent->_right;
		ptr subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(subR);
		RotateL(pParent);

		if (bf == 1)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			pParent->_bf = -1;
		}
		else if (bf == -1)
		{
			subRL->_bf = 0;
			subR->_bf = 1;
			pParent->_bf = 0;
		}
		else if (bf == 0)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			pParent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

4.4 AVL树最终代码

// AVL树的节点
template <class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& val)
		:_val(val)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}

	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	T _val;
	int _bf;// 平衡因子
};

// AVL树
template <class T>
class AVLTree
{
	typedef AVLTreeNode<T> node;
	typedef AVLTreeNode<T>* ptr;

public:
	
	// 构造函数
	AVLTree()
		:_root(nullptr)
	{}
	
	// 析构函数
	~AVLTree()
	{
		destroy(_root);
	}
	
	// 中序遍历
	void InOrder()
	{
		_inorder(_root);
	}

	// 插入新节点
	bool insert(const T& val)
	{
		// 先按二叉搜索树规则，找到插入位置
		ptr cur = _root;
		ptr parent = nullptr;

		while (cur)
		{
			if (val < cur->_val)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (val > cur->_val)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				// 相同元素不能插入
				return false;
			}
		}

		// 创建新节点并插入
		cur = new node(val);

		if (_root == nullptr)
		{
			_root = cur;
			return true;
		}
		else
		{
			if (cur->_val < parent->_val)
			{
				parent->_left = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
		}


		// 更新平衡因子
		while (parent)
		{
			if (cur == parent->_left)
			{
				(parent->_bf)--;
			}
			else
			{
				(parent->_bf)++;
			}

			// 1.parent的_bf更新后为0
			if (parent->_bf == 0)
			{
				// 插入成功
				break;
			}

			// 2.parent的_bf更新后为1或-1，此时需要继续向上更新平衡因子
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//持续往上更新
				cur = parent;
				parent = parent->_parent;
			}

			// 3.parent的_bf更新后为2或-2，此时需要旋转，旋转后以parent为根的子树为平衡二叉树，不需要在继续向上更新平衡因子
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}

				break;
			}
		}
		return true;
	}
	
	bool IsBalance()  
	{
		return is_balance(_root);
	}
	
	int Height()
	{
		return get_height(_root);
	}

private:
	// 检查该树是否平衡
	bool is_balance(ptr root)
	{
		if (root == nullptr)
			return true;

		int leftHeight = get_height(root->_left);
		int rightHeight = get_height(root->_right);

		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->_val << "平衡因子异常" << endl;
		}


		return (abs(rightHeight - leftHeight) == 1 || rightHeight == leftHeight)
			&& is_balance(root->_left)
			&& is_balance(root->_right);
	}

	// 获取以root为根的子树的高度
	int get_height(ptr root)
	{
		if (root == nullptr)
			return 0;

		return 1 + max(get_height(root->_left), get_height(root->_right));
	}

	// 析构函数的子函数
	void destroy(ptr root)
	{
		if (root == nullptr)
			return;

		destroy(root->_left);
		destroy(root->_right);
		delete root;
	}
	
	void _inorder(ptr root)
	{
		if (root == nullptr)
			return;

		_inorder(root->_left);
		cout << root->_val << " ";
		_inorder(root->_right);
	}
	
	// 左左--右单旋
	void RotateR(ptr pParent)
	{
		ptr subL = pParent->_left;
		ptr subLR = subL->_right;
		ptr ppParent = pParent->_parent;

		//1.pParent(父)和subLR(子)
		pParent->_left = subLR;
		if (subLR)
			subLR->_parent = pParent;

		//2.subL(父)和pParent(子)
		subL->_right = pParent;
		pParent->_parent = subL;

		//3.ppParent(父)和subL(子)
		if (pParent == _root)
		{
			_root = subL;
		}
		else
		{
			// 是否可以用函数参数引用 ptr& pParent 优化？
			if (ppParent->_left == pParent)
			{
				ppParent->_left = subL;
			}
			else
			{
				ppParent->_right = subL;
			}
		}
		subL->_parent = ppParent;

		//4.更新平衡因子
		subL->_bf = pParent->_bf = 0;
	}

	// 右右--左单旋
	void RotateL(ptr pParent)
	{
		ptr subR = pParent->_right;
		ptr subRL = subR->_left;
		ptr ppParent = pParent->_parent;

		pParent->_right = subRL;
		if (subRL)
			subRL->_parent = pParent;

		subR->_left = pParent;
		pParent->_parent = subR;

		if (pParent == _root)
		{
			_root = subR;
		}
		else
		{
			// 是否可以用函数参数引用 ptr& pParent 优化？
			//if (subR->_val < ppParent->_val)
			if (ppParent->_left == pParent)
			{
				ppParent->_left = subR;
			}
			else
			{
				ppParent->_right = subR;
			}
		}
		subR->_parent = ppParent;

		subR->_bf = pParent->_bf = 0;
	}

	void RotateLR(ptr pParent)
	{
		ptr subL = pParent->_left;
		ptr subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(subL);
		RotateR(pParent);

		if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			pParent->_bf = 0;
		}
		else if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			pParent->_bf = 1;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			pParent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(ptr pParent)
	{
		ptr subR = pParent->_right;
		ptr subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(subR);
		RotateL(pParent);

		if (bf == 1)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			pParent->_bf = -1;
		}
		else if (bf == -1)
		{
			subRL->_bf = 0;
			subR->_bf = 1;
			pParent->_bf = 0;
		}
		else if (bf == 0)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			pParent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	
	ptr _root;
};

完。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/1732.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LeetCode刷题记录---数位DP算法

LeetCode刷题记录---数位DP算法

😄 学会数位dp算法，可以连杀好几道力扣困难题，加油~ 🚀题目： 难度题目困难2376. 统计特殊整数困难1012. 至少有 1 位重复的数字困难233. 数字 1 的个数困难面试题 17.06. 2出现的次数🚀学习资料： 数位dp算法，我是跟着灵神学的，感谢灵神！数位 dp 通用模板参考灵神…
阅读更多...
Python数据分析案例24——基于深度学习的锂电池寿命预测

Python数据分析案例24——基于深度学习的锂电池寿命预测

本期开始案例较为硬核起来了&#xff0c;适合理工科的硕士&#xff0c;人文社科的同学可以看前面的案例。 案例背景 这篇文章是去年就发了&#xff0c;刊物也印刷了&#xff0c;现在分享一部分代码作为案例给需要的同学。 原文链接&#xff08;知网文章 C核&#xff09;&…
阅读更多...
python如何快速采集美~女视频？无反爬

python如何快速采集美~女视频？无反爬

人生苦短 我用python~ 这次康康能给大家整点好看的不~ 环境使用: Python 3.8 Pycharm mou歌浏览器 mou歌驱动 —> 驱动版本要和浏览器版本最相近 <大版本一样, 小版本最相近> 模块使用: requests >>> pip install requests selenium >>> pip …
阅读更多...
不是，到底有多少种图片懒加载方式？

不是，到底有多少种图片懒加载方式？

一、也是我最开始了解到的 js方法&#xff0c;利用滚动事件&#xff0c;判断当时的图片位置是否在可视框内&#xff0c;然后进行渲染。 弊端&#xff1a;代码冗杂&#xff0c;你还要去监听页面的滚动事件&#xff0c;这本身就是一个不建议监听的事件&#xff0c;即便是我们做了…
阅读更多...
【selenium学习】数据驱动测试

【selenium学习】数据驱动测试

数据驱动在 unittest 中&#xff0c;使用读取数据文件来实现参数化可以吗&#xff1f;当然可以。这里以读取 CSV文件为例。创建一个 baidu_data.csv 文件&#xff0c;如图所示&#xff1a;文件第一列为测试用例名称&#xff0c;第二例为搜索的关键字。接下来创建 test_baidu_da…
阅读更多...
百度生成式AI产品文心一言邀你体验AI创作新奇迹：百度CEO李彦宏详细透露三大产业将会带来机遇（文末附文心一言个人用户体验测试邀请码获取方法，亲测有效）

百度生成式AI产品文心一言邀你体验AI创作新奇迹：百度CEO李彦宏详细透露三大产业将会带来机遇（文末附文心一言个人用户体验测试邀请码获取方法，亲测有效）

百度生成式AI产品文心一言邀你体验AI创作新奇迹中国版ChatGPT上线发布强大中文理解能力超强的数理推算能力智能文学创作、商业文案创作图片、视频智能生成中国生成式AI三大产业机会新型云计算公司行业模型精调公司应用服务提供商总结获取文心一言邀请码方法中国版ChatGPT上线发…
阅读更多...
贪心算法的原理以及应用

贪心算法的原理以及应用

文章目录0、概念0.1.定义0.2.特征0.3.步骤0.4.适用1、与动态规划的联系1.1.区别1.2.联系2、例子3、总结4、引用0、概念 0.1.定义 贪心算法&#xff08;greedy algorithm &#xff0c;又称贪婪算法&#xff09;是指&#xff0c;在对问题求解时&#xff0c;总是做出在当前看来是…
阅读更多...
Java怎么实现几十万条数据插入(30万条数据插入MySQL仅需13秒)

Java怎么实现几十万条数据插入(30万条数据插入MySQL仅需13秒)

本文主要讲述通过MyBatis、JDBC等做大数据量数据插入的案例和结果。 30万条数据插入插入数据库验证实体类、mapper和配置文件定义User实体mapper接口mapper.xml文件jdbc.propertiessqlMapConfig.xml不分批次直接梭哈循环逐条插入MyBatis实现插入30万条数据JDBC实现插入30万条数…
阅读更多...
第十九天 Maven总结

第十九天 Maven总结

目录 Maven 1. 前言 2. 概述 2.1 介绍 2.2 安装 3. IDEA集成Maven 3.1 集成Maven环境 3.2 创建Maven项目 3.3 Maven坐标详解 3.4 导入maven项目 4. 依赖管理 4.1 依赖配置 4.2 依赖传递 4.3 依赖范围 4.4 生命周期 4.5 插件 Maven 1. 前言 1). 什么是Maven? …
阅读更多...
Linux实操之服务管理

Linux实操之服务管理

文章目录一、服务(service)管理介绍:service管理指令查看服务名服务的运行级别(runlevel):CentOS7后运行级别说明chkconfig指令介绍一、服务(service)管理介绍: 服务(service)本质就是进程&#xff0c;但是是运行在后台的&#xff0c;通常都会监听某个端口&#xff0c;等待其它…
阅读更多...
原力计划来了【协作共赢 成就未来】

原力计划来了【协作共赢 成就未来】

catalogue&#x1f31f; 写在前面&#x1f31f; 新星计划持续上新&#x1f31f; 原力计划方向&#x1f31f; 原力计划拥抱优质&#x1f31f; AIGC&#x1f31f; 参加新星计划还是原力计划&#x1f31f; 创作成就未来&#x1f31f; 写在最后&#x1f31f; 写在前面 哈喽&#x…
阅读更多...
依赖注入~

依赖注入~

依赖注入之setter注入&#xff1a; 依赖注入是IOC具体的一种实现方式&#xff0c; 这是针对资源获取的方式角度来说的&#xff0c;之前我们是被动接受&#xff0c;现在IOC具体的实现叫做依赖注入&#xff0c;从代码的角度来说&#xff0c;原来创建对象的时候需要new&#xff0…
阅读更多...
Phoenix基础命令_视图映射和表映射_数字存储问题---大数据之Hbase工作笔记0036

Phoenix基础命令_视图映射和表映射_数字存储问题---大数据之Hbase工作笔记0036

然后我们再来看看,用Phoenix来操作hbase,的基本用法 具体的其他的命令在官网都能找到,这里就说几个 https://phoenix.apache.org/language/index.html 首先是创建表,这里注意,默认表名给弄成大写的 这里的varchar对应的其实就是hbase中的string 然后这里的id表示行的rowkey 可…
阅读更多...
chatgpt3.5和chatgpt4的区别

chatgpt3.5和chatgpt4的区别

ChatGPT4是基于GPT-3模型的一个实例&#xff0c;但ChatGPT4已经进行了进一步的改进和优化。GPT-3&#xff08;第三代生成式预训练模型&#xff09;是OpenAl开发的一个大型语言模型&#xff0c;它在很多自然语言处理任务中表现出色。ChatGPT4继承了GPT-3的基本架构和能力&#x…
阅读更多...
复旦微ZYNQ7020全国产替代方案设计

复旦微ZYNQ7020全国产替代方案设计

现在国产化进度赶人&#xff0c;进口的芯片只做了个功能验证&#xff0c;马上就要换上国产的。国内现在已经做出来zynq的只有复旦微一家&#xff0c;已经在研制的有上海安路&#xff0c;还有成都华微&#xff08;不排除深圳国威也在做&#xff0c;毕竟这个市场潜力很大&#xf…
阅读更多...
如何在Unity中实现AStar寻路算法及地图编辑器

如何在Unity中实现AStar寻路算法及地图编辑器

文章目录AStar算法简介实现Node节点节点间的估价算法核心邻节点的搜索方式地图编辑器简介实现绘制地图网格障碍/可行走区域地图数据存储AStar算法 简介 Unity中提供了NavMesh导航寻路的AI功能&#xff0c;如果项目不涉及服务端它应该能满足大部分需求&#xff0c;但如果涉及服…
阅读更多...
树莓派（3B）：启动流程，系统初始化配置，引脚图图示说明

树莓派（3B）：启动流程，系统初始化配置，引脚图图示说明

目录 一&#xff0c;树莓派刷机及串口方式登陆 ① 准备工具 ② 操作步骤 二&#xff0c;配置树莓派接入网络 ① 树莓派入网 ② 固定树莓派的ip地址 三&#xff0c;网络SSH方式登陆树莓派 ① 打开树莓派SSH功能 ② 登陆SSH 四&#xff0c;用国内的源更新vim 五&…
阅读更多...
48天C++笔试强训 001

48天C++笔试强训 001

作者&#xff1a;小萌新 专栏&#xff1a;笔试强训 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;讲解48天笔试强训第一天的题目 笔试强训 day1选择题12345678910编程题12选择题 1 以下for循环的执行次数是&#xff08;&#xff…
阅读更多...
手把手教你基于HTML、CSS搭建我的相册（上）

手把手教你基于HTML、CSS搭建我的相册（上）

The sand accumulates to form a pagoda写在前面HTML是什么&#xff1f;CSS是什么&#xff1f;demo搭建写在最后写在前面 其实有过一些粉丝咨询前端该从什么开始学&#xff0c;那当然是我们的前端基础三件套开始学起&#xff0c;HTML、CSS、javaScript&#xff0c;前端的大部分…
阅读更多...
字符函数和字符串函数【下篇】

字符函数和字符串函数【下篇】

文章目录&#x1f396;️1.函数介绍&#x1f4ec;1.8. strstr&#x1f4ec;1.9. strtok&#x1f4ec;1.10. strerror&#x1f4ec;1.11. memcpy&#x1f4ec;1.12. memmove&#x1f4ec;1.13. memcmp&#x1f4ec;1.14. memset&#x1f396;️1.函数介绍 &#x1f4ec;1.8. st…
阅读更多...
最新文章

Copyright @ 2022~2023