技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

一文学会二叉搜索树,AVL树,红黑树

 收录于 未分类
   约 2996 字   预计阅读 6 分钟 
https://bing.ee123.net/img/rand?artid=151314952

一文学会二叉搜索树，AVL树，红黑树

[https://csdnimg.cn/release/blogv2/dist/pc/img/activeVector.png 王者杯·14天创作挑战营·第5期 10w+人浏览 915人参与

https://csdnimg.cn/release/blogv2/dist/pc/img/arrowright-line-White.png]( )

二叉搜索树

也称二叉排序树或二叉查找树

二叉搜索树：可以为空，若不为空满足以下性质
⭐1，非空左子树小于根节点的值
⭐2，非空右子大于根节点的值
⭐3，左右子树都是二叉搜索树
https://i-blog.csdnimg.cn/direct/1b118964a9b54a68a0e653b9483b1fea.png

二叉搜索树节点代码：

template<class K>
struct TreeNode
{
	TreeNode<K>* _left;
	TreeNode<K>* _right;
	K _key;

	TreeNode(const K& key)
		:_left(nullptr),
		_right(nullptr),
		_key(key)
	{
	}
};

查找

a，大于根节点向右找，小于向左找。
b，最多查找高度次，若走到空了，说没没有这个数。

bool find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)
		{
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			cur = cur->_left;
		}
		else
			return true;
	}
	return false;

插入

a, 若树是空=
=，新增节点，将节点赋值给_root;
b, 若树不为空，按二叉搜索树性质==找到插入位置，插入
https://i-blog.csdnimg.cn/direct/9ee4e42198294225853ebbb6a842f0c3.png

bool Insert(const K& key)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	Node* cur = _root;
	Node* parent = _root;
	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
			return false;
	}
	cur = new Node(key);
	if (cur->_key > parent->_key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

删除

删除要分4种情况：
a， 删除节点无左右子树
b， 删除节点只有左子树
c， 删除节点只有右子树
d， 删除节点左右子树都有

实际情况中，a可以和b/c结合起来，因此情况有三种

b：让父亲节点指向左子树（两种情况，要删除的节点是父亲的左节点还是右节点），删除节点
c：让父亲节点指向右子树，删除节点
d：找到左子树最大节点，与根节点值替换（❤因为最大，所以该节点无左子树，或只能有左子树）再按照b方法处理，删除替换的节点。 //////////////或者找右子树最小节点，再按照c方法处理，删除替换节点。

代码实现：

bool Erase(const K& key)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key == key)
			break;
		else if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			parent = cur;
			cur = cur->_left;
		}
	}
	if (cur == nullptr)
		return false;
	//左空 a情况的左右子树都空也进入这里
	if (cur->_left == nullptr)
	{
		if (cur == _root)
			_root = cur->_right;
		else
		{
			if (parent->_left == cur)
			{
				parent->_left = cur->_right;
			}
			else
				parent->_right = cur->_right;
		}
	}
	//右空
	else if (cur->_right == nullptr)
	{
		if (cur == _root)
			_root = cur->_left;
		else
		{
			if (parent->_left == cur)
			{
				parent->_left = cur->_left;
			}
			else
				parent->_right = cur->_left;
		}
	}
	else //替换
	{
		parent = cur;
		Node* leftmax = cur->_left;
		while (leftmax->_right)
		{
			parent = leftmax;
			leftmax = leftmax->_right;
		}
		swap(cur->_key, leftmax->_key);
		if (parent->_left == leftmax)
		{
			parent->_left = leftmax->_left;
		}
		else
			parent->_right = leftmax->_left;
		cur = leftmax;
	}
	delete cur;
	return true;


	return false;
}

```c
template<class K>
class BSTree
{
	typedef TreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{
	}
void Inorder()
{
	_Inorder(_root);
}
void _Inorder(Node* cur)
{
	if (cur == nullptr)
		return;
	_Inorder(cur->_left);
	cout << cur->_key << " ";
	_Inorder(cur->_right);
}
private:
	Node* _root;
};

AVL树

概念

虽然二叉搜索树加快了查找效率，但是如果数据接近顺序，那么二叉树就退化成单侧树了，查找元素就相当于在顺序表查找，效率低下，所以发明了AVL树，
https://i-blog.csdnimg.cn/direct/76e50e6ab3834a009889a866a6abce97.png

struct AVLTreeNode
{
	AVLTreeNode(const T& date = T())
		:
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_date(date),
		_bf(0)
	{}
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	T _date;
	int _bf;
};

插入

AVL树插入分两步
1，按二叉搜索树性质插入节点，
2，调整平衡因子

插入新节点，那父节点平衡因子一定要调整，如果插在父节点左子树，则父节点平衡–，反之++
接下来会有三种情况：
a，如果父节点平衡因子=0，说明平衡了，不用再调整了
b，如果父节点等于±1，说明还需要向上调整，祖父节点的平衡因子也要调整
c，如果父节点平衡因子等于±2，说明不平衡了，需要旋转。

旋转

旋转分4种
1，如果新节点插在较高左子树左侧：左左，右单旋
https://i-blog.csdnimg.cn/direct/1ed077be15024c6d8183a6436947ab73.png

如果新插入节点是60，则父子为0，
根据新插入节点左右子树不同，平衡因子更新不同

4，如果新节点插在较高右子树左侧：右左，先右单旋再左单旋
https://i-blog.csdnimg.cn/direct/e820e07c2930455cb98de5452ca765ef.png

参考左右单旋

总结：

  • 当父节点等于2时，

若子节点=1，则左单旋
若子节点=-1，则右单旋再单旋

  • 当父节点等于-2

若字节点=-1，则右单旋
若子节点=1，则左右单旋

代码实现：

template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	AVLTree()
		:_root(nullptr)
	{
	}
	bool Insert(const T& date)
	{
		if (nullptr == _root)
		{
			_root = new Node(date);
			return true;
		}
		Node* pCur = _root;
		Node* pParent = nullptr;
		while (pCur)
		{
			if (pCur->_date < date)
			{
				pParent = pCur;
				pCur = pCur->_right;
			}
			else if (pCur->_date > date)
			{
				pParent = pCur;
				pCur = pCur->_left;
			}
			else
			{
				return false;
			}
		}
		pCur = new Node(date);
		if (pParent->_date > date)
		{
			pParent->_left = pCur;
		}
		else if (pParent->_date < date)
		{
			pParent->_right = pCur;
		}
		pCur->_parent = pParent;
		while (pParent)
		{
			if (pParent->_left == pCur)
			{
				pParent->_bf--;
			}
			else
				pParent->_bf++;
			if (pParent->_bf == 0)
				break;
			else if (pParent->_bf == -1 || pParent->_bf == 1)
			{
				pCur = pParent;
				pParent = pParent->_parent;
			}
			else if (pParent->_bf == 2 || pParent->_bf == -2)
			{
				if (pParent->_bf == 2 && pCur->_bf == 1)
				{
					RotateL(pParent);
				}
				else if (pParent->_bf == -2 && pCur->_bf == -1)
				{
					RotateR(pParent);
				}
				else if (pParent->_bf == 2 && pCur->_bf == -1)
				{
					RotateRL(pParent);
				}
				else if (pParent->_bf == -2 && pCur->_bf == 1)
				{
					RotateLR(pParent);
				}
				else
					return false;
			}
		}
		return true;

	}
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		Node* pnode = parent->_parent;
		parent->_right = curleft;
		if (curleft)
		{
			curleft->_parent = parent;
		}
		cur->_left = parent;
		parent->_parent = cur;

		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (pnode->_right == parent)
			{
				pnode->_right = cur;
			}
			else
				pnode->_left = cur;
			cur->_parent = pnode;
		}
		parent->_bf = cur->_bf = 0;
	}
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		Node* pnode = parent->_parent;

		parent->_left = curright;
		if (curright)
		{
			curright->_parent = parent;
		}
		cur->_right = parent;
		parent->_parent = cur;
		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (pnode->_right == parent)
			{
				pnode->_right = cur;
			}
			else
				pnode->_left = cur;
			cur->_parent = pnode;
		}
		cur->_bf = parent->_bf = 0;
	}
	void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		int bf = curleft->_bf;
		RotateR(cur);
		RotateL(parent);
		if (bf == 0)
		{
			cur->_bf = parent->_bf = curleft->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			cur->_bf = 0;
			curleft->_bf = 0;
		}
		else if (bf == -1)
		{
			cur->_bf = 1;
			curleft->_bf = 0;
			parent->_bf = 0;
		}
		else
			assert(false);
	}
	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		int bf = curright->_bf;
		RotateL(cur);
		RotateR(parent);
		if (bf == 0)
		{
			cur->_bf = parent->_bf = curright->_bf = 0;
		}
		else if (bf == 1)
		{
			cur->_bf = -1;
			parent->_bf = 0;
			curright->_bf = 0;
		}
		else if (bf == -1)

		{
			cur->_bf = 1;
			curright->_bf = 0;
			parent->_bf = 0;
		}
		else
			assert(false);
	}
	void Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		Inorder(root->_left);
		cout << root->_date;
		Inorder(root->_right);
	}
	void Inorder()
	{
		Inorder(_root);
	}
	int Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	bool IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;
		int left = Height(root->_left);
		int right = Height(root->_right);
		if (right - left != root->_bf)
		{
			std::cout << "平衡因子错误" << root->_bf << std::endl;
		}
		return abs(left - right) < 2
			&& IsBalance(root->_left)
			&& IsBalance(root->_right);
	}

private:
	Node* _root;
};

AVL验证

1，中序遍历，如果是升序则说明是二叉平衡树

2，判断左右子树高度差不超过1，确认平衡性

红黑树

概念

AVL树限制比较大，旋转次数多，所以发明了红黑树。
红黑树：一种二叉搜索树，每个节点加了颜色限制红或黑，通过对每一条路径颜色限制，确保红黑树最短路径不会超过最短路径的两倍，因而平衡。

❤红黑树性质：
1，根节点必须是黑色的
2，每个节点不是黑色的就是红色的
3，每一条路径黑色节点数相同
4，如果一个节点是红色的，那么两个孩子都是黑色的（不能出现连续的红色）
5，叶子节点是黑色的（此处叶子节点是空）
https://i-blog.csdnimg.cn/direct/d01d352660084300a177399e18d82349.png

插入

💪如果树是空的，说明插入的是根节点，直接设置为黑，
否则来的节点就设置为红节点，因为每条路径黑节点数相同，如果新来的变为黑，那么整个树都要做调整
如果插入的红节点父亲是黑节点，那么无事发生，但如果父节点也是红，那就违反红黑树性质（红节点的孩子必须是黑节点），需要调整，接下来分两种情况分析
💪1，孩子的叔叔(与父节点相对的另一支)存在且为红，则把叔叔和父亲都设为黑，祖父设为红（依旧保持黑节点数不变），祖父设为红了，还要检查祖父的父亲是否为红，继续向上调整，
https://i-blog.csdnimg.cn/direct/4f5f3e72acd5482c8cbdf3ab4f9d5b72.png
💪2，叔叔节点 不存在/存在且为黑，旋转，旋转又分两种情况，单旋和双旋
https://i-blog.csdnimg.cn/direct/cedc0590e30e497b955d06899d904e56.png
https://i-blog.csdnimg.cn/direct/6d4ba52b469d4d6d817199316a0a841c.png
旋转之后父节点为黑，祖父为红
代码实现：

bool insert(const pair<key,value>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return false;
		}
		cur = new Node(kv);
		cur->_col = RED;
		if (parent->_kv.first <cur->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		while (parent&&parent->_col==RED)
		{
			Node* grandparent = parent->_parent;
			if(grandparent->_left==parent)
			{
				Node* uncle = grandparent->_right;
				//uncle存在且为红
				if (uncle && uncle->_col==RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					cur = grandparent;
					parent = cur->_parent;
				}
				else//uncle不存在或存在且为黑
				{
						if (parent->_left == cur)
						{
       							//g
						      //p
					        //c
							RotateR(grandparent);
							parent->_col = BLACK;
							grandparent->_col = RED;
						}
						else if (parent->_right == cur)
						{
							//g
						  //p
							//c
							RotateL(parent);
							RotateR(grandparent);
							cur->_col = BLACK;
							grandparent->_col = RED;
						}
						break;
				}	
			}
			else
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandparent->_col = RED;

					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandparent);
						grandparent->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}
				
			}
		}
		//把根设为黑
		_root->_col = BLACK;
		return true;
	}
	void RotateL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;

	Node* pnode = parent->_parent;
	parent->_right = curleft;
	if (curleft)
	{
		curleft->_parent = parent;
	}
	cur->_left = parent;
	parent->_parent = cur;

	if (parent == _root)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (pnode->_right == parent)
		{
			pnode->_right = cur;
		}
		else
			pnode->_left = cur;
		cur->_parent = pnode;
	}
	parent->_bf = cur->_bf = 0;
}
void RotateR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	Node* pnode = parent->_parent;

	parent->_left = curright;
	if (curright)
	{
		curright->_parent = parent;
	}
	cur->_right = parent;
	parent->_parent = cur;
	if (parent == _root)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (pnode->_right == parent)
		{
			pnode->_right = cur;
		}
		else
			pnode->_left = cur;
		cur->_parent = pnode;
	}
}

检测

检测是否为二叉树分两步
1，中序遍历是否是升序
2，是否满足红黑树性质

bool checkcolour(Node* root, int blacknum, int benchblack)
	{
	//黑节点数目不一样错误
		if (root == nullptr)
		{
			if (blacknum != benchblack)
				return false;
			return true;
		}
		//遇到黑++
		if (root->_col == BLACK)
		{
			++blacknum;
		}
		//是否连续红节点
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << "flase" << root->_kv.first;
			return false;
		}
		return checkcolour(root->_left,blacknum,benchblack) && checkcolour(root->_right,blacknum,benchblack);
	}
	bool isbalance()
	{
		return isbalance(_root);
	}
	bool isbalance(Node* root)
	{
	  //空树正确
	  //根不黑直接错误
		if (root == nullptr)
			return true;
		if (root->_col != BLACK)
			return false;
		Node* cur = root;
		int benchblack = 0;
		while (cur)
		{
		//确定一条路上的黑节点
			if (cur->_col == BLACK)
				++benchblack;
			cur = cur->_left;			
		}
		return checkcolour(root,0,benchblack);
	}
更新于 2025-09-09
 蓝桥杯, 数据结构, Windows, Python, List, Java, C
返回 | 主页