从二叉搜索树、AVL树到红黑树，长文总结

原创

曾高飞

修改于 2026-06-08 11:26:19

930

前言

这次打算由浅入深的从搜索树到红黑树的内容一次性总结整理出来，都是c++代码，但思路为重，希望大家在看完本片博客后都能够掌握好这一部分的内容，第二部分的题目意图在于一起锻炼代码能力和思路，为模拟实现AVL树和红黑树的代码能力打个基础。

Ⅰ、二叉搜索树

1.0二叉搜索树重要部分

二叉搜索树的考察重点在于二叉搜索树的删除操作，进行画图分类讨论好非常重要。

1.1二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

3.它的左右子树也分别为二叉搜索树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PBQnq0ss-1677399534579)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230222144754615.png)]

如图便是一棵二叉搜索树，左子树节点都比父节点小，右子树节点都比父节点大。

1.2二叉搜索树的操作

1.2.1二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

**时间复杂度：**最优情况（logN）,最坏情况（N）。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Kkp5dsTF-1677399534580)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230222145554165.png)]

如何解决这种问题呢？有第三部分AVL树和第四部分红黑树两种方法进行解决。

1.2.2二叉搜索树的插入

插入的具体过程如下：

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Atu0ZlaW-1677399534581)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230222150140166.png)]

1.2.3二叉搜索树的删除（重点）

二叉搜索树的删除操作是这一部分内容的大头，如何分类讨论好就显得非常重要，删除节点时由于不能破坏搜索树的结构，因此在有的情况下需要我们进行调整。

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除。

情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除

情况d：替换法删除，找待删除节点的左子树中的最大值，或者右子树中的最小值来进行替换，将待删除节点的值修改为该值，再删除节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OuaevbnF-1677399534581)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230222152515080.png)]

思路讲解便到此为止，接下来便进行二叉搜索树的模拟实现了

1.3二叉搜索树的模拟实现

1.3.1代码实现的一些心得和细节

1.善用模板和typedef.

2.类与对象部分内容得掌握好

3.删除操作不仅需要明白思路，而且需要考虑好特殊情况

1.3.2模拟实现代码

#include<iostream>
using namespace std;

template<class K>
struct BSTNode        //二叉搜索树的节点
{
	BSTNode(const K& data)        //构造函数   
		:_Left(nullptr)           //初始化列表
		, _Right(nullptr)
		, _data(data)
	{ }

	BSTNode* _Left;
	BSTNode* _Right;
	K _data;
};

template<class K>
class BSTree
{
public:
	typedef BSTNode<K> Node;
	BSTree()                   //默认构造
		:_root(nullptr)
	{}
	~BSTree()            //析构函数
	{
		Destory(_root);      //额外定义一个私有成员函数Destory来递归删除
		_root = nullptr;
	}
	// ....拷贝构造 和赋值运算符重载等就暂时省略了
	//查找接口
	bool Find(const K& data)
	{
		//return _Find(data, _root);  //递归实现
		Node* cur = _root;
		while (cur)     //为空退出，说明没找到
		{
			if (data == cur->_data)       //找到了返回真
			{
				return true;
			}
			else if (data < cur->_data)    //小去左子树找
			{
				cur = cur->_Left;
			}
			else                       //大去右子树找
			{
				cur = cur->_Right;
			}
		}
		return false;
	}

	//插入
	bool Insert(const K& data)       //不支持插入相同的重复数字
	{
		if (nullptr == _root)        //树为空
		{
			_root = new Node(data);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;  
		while (cur)      //找到待插入位置
		{
			parent = cur;
			if (data < cur->_data)
			{
				cur = cur->_Left;
			}
			else if (data > cur->_data)
			{
				cur = cur->_Right;
			}
			else
			{
				return false;   
			}
		}
		if (data < parent->_data)
		{
			parent->_Left = new Node(data);
		}
		else
		{
			parent->_Right = new Node(data);
		}
		return true;
	}
	//删除接口（重点）
	bool Erase(const K& data)
	{
		if (nullptr == _root)
		{
			return false;
		}
		Node* cur = _root;
		Node* parent = _root;   //考虑特殊情况
		while (cur)      //找到待删除位置
		{
			if (data < cur->_data)
			{
				parent = cur;
				cur = cur->_Left;
			}
			else if (data > cur->_data)
			{
				parent = cur;
				cur = cur->_Right;
			}
			else     //找到了
			{
				//情况1可以合并进2或者3
				if (nullptr == cur->_Left)  //没有左孩子的情况
				{
					if (parent == cur)   //特殊情况，删除的是根节点
					{
						_root = cur->_Right;

					}
					else
					{
						if (cur == parent->_Left)      
						{
							parent->_Left = cur->_Right;
						}
						else
						{
							parent->_Right = cur->_Right;
						}	
					}	
					delete cur;
				}
				else if (nullptr == cur->_Right) //没有右孩子的情况
				{
					if (parent == cur)
					{
						_root = cur->_Left;
					}
					else
					{
						if (cur == parent->_Left)
						{
							parent->_Left = cur->_Left;
						}
						else
						{
							parent->_Right = cur->_Left;
						}
					}
					delete cur;
				}
				else                         //左右孩子都存在的情况(重点)
				{
					//找右子树中最小的节点,右子树中最左边的节点
					Node* Rmin = cur->_Right;  
					while (Rmin->_Left)
					{
						parent = Rmin;          //存储寻找到节点的父节点
						Rmin = Rmin->_Left;
					}
					cur->_data = Rmin->_data;
					if (parent == cur)          
					{
						parent->_Right = Rmin->_Right;
					}
					else
					parent->_Left = Rmin->_Right;
					delete Rmin;
				}
				return true;
			}	
		}
		return false; //没找到

	}
	void Inorder()   //中序遍历该树
	{
		_Inorder(_root);
		cout << endl;
	}

private:
	void _Inorder(Node* root)
	{
		if (nullptr == root)
		{
			return;
		}
		_Inorder(root->_Left);
		cout << root->_data << " ";
		_Inorder(root->_Right);
	}
	bool _Find(const K& data,Node* root)
	{
		if (nullptr == root)
		{
			return false;
		}
		if (root->_data == data)
		{
			return true;
		}
		else if (data > root->_data)
		{
			return _Find(data, root->_Right);
		}
		else
		{
			return _Find(data, root->_Left);
		}
	}
	void Destory(Node* root)
	{
		if (nullptr == root)
		{
			return;
		}
		Destory(root->_Left);
		Destory(root->_Right);
		delete root;
	}

	Node* _root;
};

int main()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t1;
	for (auto e : a)
	{
		t1.Insert(e);
	}
	t1.Inorder();
	for (auto e : a)
	{
		t1.Erase(e);
		t1.Inorder();
	}
	return 0;
}
一键获取完整项目代码c++123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aqrgCTsb-1677399534582)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230222172115132.png)]

在本次模拟实现二叉搜索树中，其中最麻烦的部分便是删除，删除还需要考虑好删除节点为根节点的特殊情况，很容易出差错.

1.4二叉搜索树的应用

1.4.1 k模型和KV模型

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

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

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。

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

1.4.2 KV模型的代码实现

只需要在原本的二叉搜索树上稍加修改即可

通过key查找和修改value

template<class K, class V >
struct BSTNode        //二叉搜索树的节点
{
	BSTNode(const K& key =K(),const V& value = K())  //默认以K和V迭代默认构造进行构造  
		:_Left(nullptr)           //初始化列表
		, _Right(nullptr)
		, _key(key)
		, _value(value)
	{ }

	BSTNode* _Left;
	BSTNode* _Right;
	K _key;
	V _value;
};

template<class K,class V>
class BSTree
{
public:
	typedef BSTNode<K,V> Node;
	BSTree()                   //默认构造
		:_root(nullptr)
	{}
	~BSTree()            //析构函数
	{
		Destory(_root);      //额外定义一个私有成员函数Destory来递归删除
		_root = nullptr;
	}
	// ....拷贝构造 和赋值运算符重载等就暂时省略了
	//查找接口
	Node* Find(const K& data)
	{
		//return _Find(data, _root);  //递归实现
		Node* cur = _root;
		while (cur)     //为空退出，说明没找到
		{
			if (data == cur->_key)       //找到了返回真
			{
				return cur;
			}
			else if (data < cur->_key)    //小去左子树找
			{
				cur = cur->_Left;
			}
			else                       //大去右子树找
			{
				cur = cur->_Right;
			}
		}
		return nullptr;
	}

	//插入
	bool Insert(const K& data,const V& value)       //不支持插入相同的重复数字
	{
		if (nullptr == _root)        //树为空
		{
			_root = new Node(data,value);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)      //找到待插入位置
		{
			parent = cur;
			if (data < cur->_key)
			{
				cur = cur->_Left;
			}
			else if (data > cur->_key)
			{
				cur = cur->_Right;
			}
			else
			{
				return false;
			}
		}
		if (data < parent->_key)
		{
			parent->_Left = new Node(data,value);
		}
		else
		{
			parent->_Right = new Node(data,value);
		}
		return true;
	}

	//删除接口（重点）
	bool Erase(const K& data)
	{
		if (nullptr == _root)
		{
			return false;
		}
		Node* cur = _root;
		Node* parent = _root;   //考虑特殊情况
		while (cur)      //找到待删除位置
		{
			if (data < cur->_key)
			{
				parent = cur;
				cur = cur->_Left;
			}
			else if (data > cur->_key)
			{
				parent = cur;
				cur = cur->_Right;
			}
			else     //找到了
			{
				//情况1可以合并进2或者3
				if (nullptr == cur->_Left)  //没有左孩子的情况
				{
					if (parent == cur)   //特殊情况，删除的是根节点
					{
						_root = cur->_Right;

					}
					else
					{
						if (cur == parent->_Left)
						{
							parent->_Left = cur->_Right;
						}
						else
						{
							parent->_Right = cur->_Right;
						}
					}
					delete cur;
				}
				else if (nullptr == cur->_Right) //没有右孩子的情况
				{
					if (parent == cur)
					{
						_root = cur->_Left;
					}
					else
					{
						if (cur == parent->_Left)
						{
							parent->_Left = cur->_Left;
						}
						else
						{
							parent->_Right = cur->_Left;
						}
					}
					delete cur;
				}
				else                         //左右孩子都存在的情况(重点)
				{
					//找右子树中最小的节点,右子树中最左边的节点
					Node* Rmin = cur->_Right;
					while (Rmin->_Left)
					{
						parent = Rmin;          //存储寻找到节点的父节点
						Rmin = Rmin->_Left;
					}
					cur->_key = Rmin->_key;
					if (parent == cur)
					{
						parent->_Right = Rmin->_Right;
					}
					else
						parent->_Left = Rmin->_Right;
					delete Rmin;
				}
				return true;
			}
		}
		return false; //没找到

	}

	void Inorder()   //中序遍历该树
	{
		_Inorder(_root);
		cout << endl;
	}


private:
	void _Inorder(Node* root)
	{
		if (nullptr == root)
		{
			return;
		}
		_Inorder(root->_Left);
		cout << root->_key << ":"<<root->_value<<" ";
		_Inorder(root->_Right);
	}

	void Destory(Node* root)
	{
		if (nullptr == root)
		{
			return;
		}
		Destory(root->_Left);
		Destory(root->_Right);
		delete root;
	}

	Node* _root;
};



int main()
{
	BSTree<string, int> countTree;
	//统计水果的出现次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		// 2、在，则查找到的节点中水果对应的次数++
		//BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == nullptr)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.Inorder();
	countTree.Erase("苹果");
	countTree.Inorder();
	countTree.Erase("香蕉");
	countTree.Inorder();
	countTree.Erase("西瓜");
	countTree.Inorder();
	return 0;
}
一键获取完整项目代码c++123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CWRI3fcD-1677399534582)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230223112152922.png)]

1.5二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HCc4TdNC-1677399534583)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230223112351347.png)]

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：logN

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们马上要学习的AVL树和红黑树就可以上场了。

Ⅱ、经典二叉树题目

2.1二叉树创建字符串。

根据二叉树创建字符串 - 力扣（LeetCode）

这题要求我们采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。。

class Solution {
public:
    void FrontOreder(TreeNode* root,string& s1)
    {
        if(nullptr == root)
        {
            return;
        }       
        s1+="(";
        s1+=to_string(root->val);  //将数字转化为string
        if(nullptr == root->left&& nullptr!=root->right) //特殊情况，左为空 右不为空，需要补上（）
        {
            s1+="()";
        }
        FrontOreder(root->left,s1);
        FrontOreder(root->right,s1);
       s1+=")";
    }

    string tree2str(TreeNode* root) {
        if(nullptr == root)
        {
            return string();     //空直接返回string的默认构造
        }
        string s1;
        s1+=to_string(root->val);
        if(nullptr == root->left&& nullptr!=root->right) //检查特殊情况 根左为空，根右不为空
        {
            s1+="()";
        }
        FrontOreder(root->left,s1); //递归左子树
        FrontOreder(root->right,s1); //递归右子树
        return s1;
    }
};
一键获取完整项目代码c++1234567891011121314151617181920212223242526272829303132333435

2.2二叉树的分层遍历1。

二叉树的层序遍历 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
       vector<vector<int>> vv;
       if(nullptr == root)       //判断是否为空
       {
           return vv;
       }
        queue<TreeNode*>q1;     //存放根节点的队列
        q1.push(root);
        while(!q1.empty())       //队列不为空就继续
        {
            int i = q1.size();  //当前队列存放的节点数，即该层的节点个数
            vector<int> v;
            while(i--)     //只取出当前层的节点，
            {
                TreeNode* tmp = q1.front();
                q1.pop();     //出队列后，如果左右孩子不为空就入队列
                v.push_back(tmp->val);
                if(tmp->left)
                q1.push(tmp->left);
                if(tmp->right)
                q1.push(tmp->right); 
            }
            vv.push_back(v);   //将该层的数据保存
        }
        return vv;
    }
};
一键获取完整项目代码c++1234567891011121314151617181920212223242526272829

2.3二叉树的分层遍历2。

复用第二题的代码，最后加一个逆置即可。

2.4给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

二叉树的最近公共祖先 - 力扣（LeetCode）

该题目有两种思路

思路1：找规律

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IfnAGrVT-1677399534584)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230223154308239.png)]

由规律可知，我们只需要从根节点开始，判断左右子树中是否存在节点即可，不满足公共祖先的特点，再在存在节点的子树中寻找。

class Solution {
public:
    bool isExist(TreeNode*root,TreeNode*p,TreeNode*q) //检查是否存在节点
    {
        if(nullptr == root)
        {
            return false;
        }
        if(root == p || root ==q)
        {
            return true;
        }
        return isExist(root->left,p,q)||isExist(root->right,p,q);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p||root ==q)  //情况1，自己是节点之一直接 返回
        {
            return root;
        }
        bool ad1 = isExist(root->left,p,q);
        bool ad2 = isExist(root->right,p,q);
        if(ad1&&ad2)  //左右子树分别存在节点 返回
        {
            return root;
        }
        if(ad1)   //左边有去左边找
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        if(ad2)  //右边有去右边找
        {
            return lowestCommonAncestor(root->right,p,q);
        }

        return nullptr;  //按理不存在找不到的情况，除非不在同一个二叉树
    }
};
一键获取完整项目代码c++12345678910111213141516171819202122232425262728293031323334353637

这种方法比较简单，但因为检查是否存在节点需要多次递归寻找，因此效率不高。

思路2：找路径

两条路径的相交点即是公共祖先

思路，用两个栈分别存放对应的路径，大的栈先出栈二者相差次，再同时pop，栈顶相同时即是公共祖先。

class Solution {
public:
    bool getPath(TreeNode* root,TreeNode* node,stack<TreeNode*>& s)      //获取路径  需要使用引用
    {
        if(nullptr == root)     
        {
            return false;
        }
        s.push(root);        //遇到节点入栈
        if(root == node)      
        {
            return true;
        }
        if(getPath(root->left,node,s))   //看左子树有无节点
        {
            return true;
        }
        if(getPath(root->right,node,s))  //看右子树有无节点
        {
            return true;
        }
        s.pop();       //左右子树无节点，将当前节点出栈
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
      stack<TreeNode*> s1;
      stack<TreeNode*> s2;
      getPath(root,p,s1);
      getPath(root,q,s2);
      int count = 0;
      int size1 = s1.size();
      int size2 = s2.size();
      if(size1>size2)          //开始准备出栈找公共祖先
      {
          count = size1 - size2;
          while(count--)
          {
              s1.pop();
          }
      }
      else
      {
          count = size2 - size1;
          while(count--)
          {
              s2.pop();
          }
      }

        while(!s1.empty()&&!s2.empty())
          {
              if(s1.top()==s2.top())
              {
                  return s1.top();
              }
              s1.pop();
              s2.pop();

            }
            return nullptr;
    }
};
一键获取完整项目代码c++123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263

这个方法的效率就大幅提高了。

2.5二叉树搜索树转换成排序双向链表。

思路1：中序遍历，用vector存储节点再

class Solution {
public:
	void InOrdersave(TreeNode* root,vector<TreeNode*>& v)//中序遍历搜索树，并将节点按序存入v中
	{
		if(nullptr == root)
		{
			return;
		}
		InOrdersave(root->left,v);
		v.push_back(root);
		InOrdersave(root->right,v);
	}

    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(nullptr == pRootOfTree）  //检查特殊情况
		{
			return nullptr;
		}
		vector<TreeNode*> v;
		InOrdersave(pRootOfTree,v);
		for(int i = 0;i<v.size()-1;++i)
		{
			v[i]->right = v[i+1];
		}
		for(int i = 1;i<v.size();++i)
		{
			v[i]->left = v[i-1];
		}
		return v[0];
    }
};
一键获取完整项目代码c++12345678910111213141516171819202122232425262728293031

缺陷：虽然方法容易，但是使用了额外的空间

思路2：直接进行转换

要想按着顺序进行转换，我们就必须按中序遍历，因此我们需要两个指针来记录位置，一个记录前一个位置，一个记录当前位置。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zRxT7Bsy-1677399534584)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230224144245573.png)]

cur的顺序是4—>6—>8…

prev初始为nullptr

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5oiwH80l-1677399534585)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230224144600171.png)]

该方法的要点在于先搞定left, 在cur到下一个位置后在通过prev来改变right.

class Solution {
public:
	void InOrderConvert(TreeNode* cur,TreeNode*& prev)//prev要用引用
	{
		if(nullptr == cur)
		{
			return;
		}
		InOrderConvert(cur->left,prev);
		cur->left = prev;
		if(prev)
		{
			prev->right = cur;
		}
		prev = cur;
		InOrderConvert(cur->right,prev);
	}

    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(nullptr == pRootOfTree)
		{
			return nullptr;
		}
		TreeNode* prev = nullptr;
		InOrderConvert(pRootOfTree,prev);
		while(pRootOfTree->left)       //找到头节点
		{
			pRootOfTree = pRootOfTree->left;
		}
		return pRootOfTree;
    }
};
一键获取完整项目代码c++1234567891011121314151617181920212223242526272829303132

2.6根据一棵树的前序遍历与中序遍历构造二叉树。

从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Sw3Ktg7T-1677399534585)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230224151411733.png)]

关键：递归，区间分治，跟快排很像

class Solution {
public:
    TreeNode* CreatTree(vector<int>& preorder, vector<int>& inorder,int& prei,int begin, int end)
    {
        if(begin>end)
        {
            return nullptr;
        }
        //找到左右子树的区间
        int rooti = begin;
        while(rooti <= end)
        {
            if(preorder[prei] == inorder[rooti])
            {
                break;
            }
            rooti++;
        }
        //创建根节点，prev++，指向下一个根
        TreeNode* root = new TreeNode(preorder[prei++]);
        root->left = CreatTree(preorder,inorder,prei,begin,rooti-1);
        root->right = CreatTree(preorder,inorder,prei,rooti+1,end);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return CreatTree(preorder,inorder,i,0,inorder.size()-1);
    }
};
一键获取完整项目代码c++123456789101112131415161718192021222324252627282930

2.7根据一棵树的中序遍历与后序遍历构造二叉树。

从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IV1lM6jn-1677399534585)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230224155332286.png)]

第七题与第六题相差不大，一方面我们是通过后序来确定根，另一方面则是先得弄右子树再弄左子树。

class Solution {
public:
    TreeNode* CreatTree(vector<int>& inorder, vector<int>& postorder,int& posi,int begin, int end)
    {
        if(begin>end)
        {
            return nullptr;
        }
        //找到左右子树的区间
        int rooti = begin;
        while(rooti <= end)
        {
            if(postorder[posi] == inorder[rooti])
            {
                break;
            }
            rooti++;
        }
        //创建根节点，posi--，指向下一个根
        TreeNode* root = new TreeNode(postorder[posi--]);
        root->right = CreatTree(inorder,postorder,posi,rooti+1,end);
        root->left = CreatTree(inorder,postorder,posi,begin,rooti-1);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int posi = postorder.size()-1;
        return CreatTree(inorder,postorder,posi,0,inorder.size()-1);
    }
};
一键获取完整项目代码c++123456789101112131415161718192021222324252627282930

2.8二叉树的前序遍历，非递归迭代实现。

二叉树的前序遍历 - 力扣（LeetCode）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tdWOiMJH-1677399534586)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230224160923693.png)]

将树分为两个部分来解决。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> v;
        TreeNode* cur = root;
        //左路节点入栈，同时存储值
        while(cur)
        {
            s.push(cur);
            v.push_back(cur -> val);
            cur = cur->left;
        }
        while(!s.empty())
        {
            TreeNode* tmp = s.top();  
            s.pop();
            tmp = tmp->right;
            while(tmp)     //将右子树的左路节点入栈
            {
                s.push(tmp);
                v.push_back(tmp->val);
                tmp = tmp->left;
            }
        }
        return v;
    }
};
一键获取完整项目代码c++12345678910111213141516171819202122232425262728

2.9二叉树中序遍历，非递归迭代实现。

二叉树的中序遍历 - 力扣（LeetCode）

方法与8相同，注意数据放入容器vector的时机即可

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        while(cur||!s.empty())
        {
            //左路节点入栈
            while(cur)
            {
                s.push(cur);
                cur = cur->left;
            }
            TreeNode* tmp = s.top();
            v.push_back(tmp->val);   //存储数据
            s.pop();
            cur = tmp->right;
        }
        return v;
    }
};
一键获取完整项目代码c++12345678910111213141516171819202122

2.10二叉树的后序遍历，非递归迭代实现。

二叉树的后序遍历 - 力扣（LeetCode）

要点，如何判断节点是否需要出栈。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-j782kFYU-1677399534586)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230224201240599.png)]

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> v;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while(cur||!s.empty())
        {
            while(cur)
            {
                s.push(cur);
                cur = cur->left;
            }
            TreeNode* top = s.top();
            if((nullptr == top->right) || (prev == top->right))//判断节点是否能出栈，看右子树是否为空或者右子树已经入过栈。
            {
                s.pop();
                v.push_back(top->val);
                prev = top;
            }
            else
            {
                cur = top->right;
            }
        }
        return v;
    }
};
一键获取完整项目代码c++1234567891011121314151617181920212223242526272829

十道题目做完，大家应该收获不少，接下来就要开始啃硬骨头了。

Ⅲ、AVL树

3.1键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

SGI-STL中关于键值对的定义：

template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};
一键获取完整项目代码c++123456789101112

为什么要说键值对？因为接下来我们在节点中存储的数据都按照键值对的形式来存储，为了与map和set相匹配。

3.2AVL树的概念

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

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1.它的左右子树都是AVL树

2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ld2IF0Pv-1677399534587)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225085138949.png)]

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(logN),搜索时间复杂度O(logN)。

3.3AVL树节点的定义

template<class K,class V>
struct AVLTreeNode
{
	pair<K, V> _kv;        
	AVLTreeNode<K,V>* _left;  
	AVLTreeNode<K,V>* _right;
	AVLTreeNode<K,V>* _parent;     //指向父节点的指针
	int _bf;           //平衡因子
	AVLTreeNode(const pair<K,V>& kv)   //构造函数
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_buf(0)
	{}

};
一键获取完整项目代码C++1234567891011121314151617

首先我们增加了一个平衡因子，用来表示树的平衡与否，因为插入节点后需要修改上一节点的平衡因子，所以我们增加了指向父节点的指针（因为每个孩子都只有一个父亲）

3.4AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3vJ5jLyU-1677399534588)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225094639632.png)]

	bool Insert(const pair<K, V>& kv)
	{
		//1.按二叉搜索树的规则插入节点
		//2.进行平衡因子的调节 
		if (nullptr == _root)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		//修改平衡因子。新增节点在左子树，bf--, 新增节点在右子树,bf++,向父节点
		/*此时：_parent的平衡因子可能有三种情况：0，正负1， 正负2
			1. 如果_parent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整
			成0，此时满足AVL树的性质，插入成功
			2. 如果_parent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
			新成正负1，此时以_parent为根的树的高度增加，需要继续向上更新
			3. 如果_parent的平衡因子为正负2，则_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 = parent;
				parent = parent->_parent;
			}
			else if(parent->_bf == -2|| parent->_bf == 2)
			{
				//_bf为+-2,需要进行旋转操作，并在操作后更新平衡因子。
				if (parent->_bf == 2 && parent->_right->_bf == 1)  //左单旋的情况 
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && parent->_left->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && parent->_left->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && parent->_right->_bf == -1)
				{
					RotateRL(parent);
				}
				break;     //记得退出循环，否则会再次进入循环造成平衡因子异常
			}
			else
			{
				assert(false);
			}

		}


		return true;
	}
一键获取完整项目代码c++123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

3.5AVL树的旋转

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uL1ZIeQv-1677399534588)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225094703528.png)]

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

1.左单旋

注意点：

为了方便改平衡因此，我们给节点添加了指向父亲节点的指针，而这一点也使得我们旋转时会复杂不少。

进行左单旋的情况，失衡节点平衡因子为2（右子树高），失衡节点的右子树的根的平衡因子为1（右子树高）此时可进行左单旋

注意判断subRL是否为空，再更改subRL->_parent, 防止对空指针解引用，导致程序崩溃

if (parent->_bf == 2 && parent->_right->_bf == 1)  //左单旋的情况 
{
	RotateL(parent);
}
一键获取完整项目代码c++1234

旋转完成后记得更新平衡因子。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qKmvGEAh-1677399534588)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225113117030.png)]

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;    //subR,parent的右子树
		Node* subRL = subR->_left;       //subRL, parent右子树的左子树
		Node* ppNode = parent->_parent;

		parent->_right = subRL; //parent的右指向subR的左子树
		if (subRL)                //记得判断subRL是否存在，易错点
		{
			subRL->_parent = parent;
		}
		subR->_left = parent; //subR的左，指向parent
		parent->_parent = subR;

		if (nullptr == ppNode) //parent本身是这棵树的根节点
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else    //改变parent 的父节点的指向
		{
			subR->_parent = ppNode;
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
		}
		parent->_bf = subR->_bf = 0;     //更新平衡因子
	}
一键获取完整项目代码c++12345678910111213141516171819202122232425262728293031323334

2.右单旋

注意事项和左单旋相同

有单旋的条件：失衡节点平衡因子为-2，subL的平衡因子为-1；

else if (parent->_bf == -2 && parent->_left->_bf == -1)
{
	RotateR(parent);
}
一键获取完整项目代码c++1234

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y9vZiSHw-1677399534589)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225115419971.png)]

void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppNode = parent->_parent;

		parent->_left = subLR;
		if (subLR)              //记得判断subLR是否存在，防止对空指针解引用
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		parent->_parent = subL;
		
		if (nullptr == ppNode)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			subL->_parent = ppNode;
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
		}
		parent->_bf = subL->_bf = 0;
	}
一键获取完整项目代码c++123456789101112131415161718192021222324252627282930313233

3.先左单旋再右单旋

注意点：

先左单旋再右单旋的条件：失衡节点平衡因子为-2，且subL的平衡因子为1，即新增节点在左子树的右子树上

这种情况不能单纯的右单旋，因为我们需要将subL的右子树放到原根节点的左边，旋转后树就会依然不平衡.

else if (parent->_bf == -2 && parent->_left->_bf == 1)
	{
		RotateLR(parent);
	}
一键获取完整项目代码c++1234

旋转过程如下图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pOpinVEQ-1677399534589)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225165507485.png)]

旋转完成后真正的麻烦点在于确定好平衡因子

另一种观察模式：

将旋转前的树与旋转完成后的树进行对比，可以发现节点6再将自己的左子树给节点5，把自己的右子树给节点10，然后自己成为根节点，由此我们就可以看出平衡因子的变化规律。

需要提前存储subLR的平衡因子，用以旋转结束后进行情况种类的判断

如何确定好平衡因子有着3种情况：

**情况1：**subLR为-1，即新增节点为subLR的左子树

旋转完成后将subL 和subLR的平衡因子改为0，parent的平衡因子改为1。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uHGjQwVD-1677399534590)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225170610435.png)]

**情况2：**subLR为1，即新增节点为subLR的右子树

旋转完成后将parent 和subLR的平衡因子改为0，subL的平衡因子改为-1。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LHrxQ87U-1677399534590)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225172745304.png)]

情况3：新增节点就是subLR本身，subL的平衡因子改为-1，即subLR的平衡因子为0时的情况，参考QQ靓号。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LXlETVQC-1677399534590)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225172233273.png)]

此时把parent、subL、subLR全部置为0即可

void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(subL);
		RotateR(parent);
		if (0 == bf)  //情况3
		{
			parent->_bf = subL->_bf = subLR->_bf = 0;
		}
		else if (1 == bf)  //情况2
		{
			parent->_bf = subLR->_bf = 0;
			subL->_bf = -1;
		}
		else if (-1 == bf) //情况1
		{
			subL->_bf = subLR->_bf = 0;
			parent->_bf = 1;
		}
		else        //出现异常，结束程序
		{
			assert(false);
		}
	}
一键获取完整项目代码c++1234567891011121314151617181920212223242526

4.先右单旋，再左单旋

实现方法与3类似，大家可以自己尝试分析写出代码，我就直接放上自己的实现了。

void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		RotateR(subR);
		RotateL(parent);
		if (0 == bf)  //情况3
		{
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (1 == bf)  //情况2
		{
			subR->_bf = subRL->_bf = 0;
			parent->_bf = -1;
		}
		else if (-1 == bf) //情况1
		{
			 parent->_bf = subRL->_bf = 0;
			 subR->_bf = 1;
		}
		else        //出现异常，结束程序
		{
			assert(false);
		}
	}
一键获取完整项目代码c++1234567891011121314151617181920212223242526

3.6AVL树模拟实现的代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K,class V>
struct AVLTreeNode
{
	pair<K, V> _kv;        
	AVLTreeNode<K,V>* _left;  
	AVLTreeNode<K,V>* _right;
	AVLTreeNode<K,V>* _parent;     //指向父节点的指针
	int _bf;           //平衡因子
	AVLTreeNode(const pair<K,V>& kv)   //构造函数
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}

};

template<class K,class V>
class AVLTree
{
public:
	typedef AVLTreeNode<K, V> Node;
	AVLTree()
		:_root(nullptr)
	{}

	bool Insert(const pair<K, V>& kv)
	{
		//1.按二叉搜索树的规则插入节点
		//2.进行平衡因子的调节 
		if (nullptr == _root)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		//修改平衡因子。新增节点在左子树，bf--, 新增节点在右子树,bf++,向父节点
		/*此时：_parent的平衡因子可能有三种情况：0，正负1， 正负2
			1. 如果_parent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整
			成0，此时满足AVL树的性质，插入成功
			2. 如果_parent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
			新成正负1，此时以_parent为根的树的高度增加，需要继续向上更新
			3. 如果_parent的平衡因子为正负2，则_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 = parent;
				parent = parent->_parent;
			}
			else if(parent->_bf == -2|| parent->_bf == 2)
			{
				//_bf为+-2,需要进行旋转操作，并在操作后更新平衡因子。
				if (parent->_bf == 2 && parent->_right->_bf == 1)  //左单旋的情况 
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && parent->_left->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && parent->_left->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && parent->_right->_bf == -1)
				{
					RotateRL(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}

		}


		return true;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;    //subR,parent的右子树
		Node* subRL = subR->_left;       //subRL, parent右子树的左子树
		Node* ppNode = parent->_parent;

		parent->_right = subRL; //parent的右指向subR的左子树
		if (subRL)                //记得判断subRL是否存在，易错点
		{
			subRL->_parent = parent;
		}
		subR->_left = parent; //subR的左，指向parent
		parent->_parent = subR;

		if (nullptr == ppNode) //parent本身是这棵树的根节点
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else    //改变parent 的父节点的指向
		{
			subR->_parent = ppNode;
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
		}
		parent->_bf = subR->_bf = 0;     //更新平衡因子
	}


	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppNode = parent->_parent;

		parent->_left = subLR;
		if (subLR)              //记得判断subLR是否存在，防止对空指针解引用
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		parent->_parent = subL;
		
		if (nullptr == ppNode)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			subL->_parent = ppNode;
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
		}
		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 (0 == bf)  //情况3
		{
			parent->_bf = subL->_bf = subLR->_bf = 0;
		}
		else if (1 == bf)  //情况2
		{
			parent->_bf = subLR->_bf = 0;
			subL->_bf = -1;
		}
		else if (-1 == bf) //情况1
		{
			subL->_bf = subLR->_bf = 0;
			parent->_bf = 1;
		}
		else        //出现异常，结束程序
		{
			assert(false);
		}
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		RotateR(subR);
		RotateL(parent);
		if (0 == bf)  //情况3
		{
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (1 == bf)  //情况2
		{
			subR->_bf = subRL->_bf = 0;
			parent->_bf = -1;
		}
		else if (-1 == bf) //情况1
		{
			 parent->_bf = subRL->_bf = 0;
			 subR->_bf = 1;
		}
		else        //出现异常，结束程序
		{
			assert(false);
		}
	}
	void Inorder()
	{
		_Inorder(_root);
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	int Hight(Node* root)
	{
		if (nullptr == root)
		{
			return 0;
		}
		int lh = Hight(root->_left);
		int rh = Hight(root->_right);
		
		return lh > rh ? lh + 1 : rh + 1;
	}

private:

	bool _IsBalance(Node* root)
	{
		if (nullptr == root)
		{
			return true;
		}
		int Lh = Hight(root->_left);
		int Rh = Hight(root->_right);
		if (Rh - Lh != root->_bf)
		{
			cout << root->_kv.first<<"平衡因子异常\n" << endl;
		}

		return abs(Rh - Lh) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
	}


	void _Inorder(Node* root)
	{
		if (nullptr == root)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_Inorder(root->_right);
	}

	Node* _root;
};

一键获取完整项目代码c++123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309

3.7AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

验证其为二叉搜索树

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。

int main()
{
	AVLTree<int,int> t1;
	int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//特殊情况
	//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//常规情况
 	for (auto e : arr)
	{
		t1.Insert(make_pair(e, e));
                                      	}
	t1.Inorder();

	return 0;
}

一键获取完整项目代码c++1234567891011121314

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-M70VGeS2-1677399534591)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230225191432997.png)]

建议大家自己参照两种实例进行验证，也许就会发现一些难以察觉的错误，博主验证时就找出错误了。

验证其为平衡树

每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

节点的平衡因子是否计算正确。

bool IsBalance()      //是否平衡
	{
		return _IsBalance(_root);
	}

	int Hight(Node* root)        //求树的高度
	{
		if (nullptr == root)
		{
			return 0;
		}
		int lh = Hight(root->_left);
		int rh = Hight(root->_right);
		
		return lh > rh ? lh + 1 : rh + 1;
	}

private:
	bool _IsBalance(Node* root)
	{
		if (nullptr == root)
		{
			return true;
		}
		int Lh = Hight(root->_left);
		int Rh = Hight(root->_right);
		if (Rh - Lh != root->_bf)
		{
			cout << root->_kv.first<<"平衡因子异常\n" << endl;
		}

		return abs(Rh - Lh) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
	}

一键获取完整项目代码c++12345678910111213141516171819202122232425262728293031323334

希望大家也能好好的进行验证，博主就从中发现了不少不细看难以知晓的bug，现在放上来的这一版应该是没bug了。

3.8AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log_2 (N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

而这也是现在基本上都是使用红黑树的原因之一。

Ⅳ、红黑树

4.1红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5LPeQC7Q-1677399534591)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226153956073.png)]

红黑树的代码实现与AVL相比简单一点（不需要调节平衡因子），但其更加抽象。

4.2红黑树的性质

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的(此处的叶子结点指的是空结点，即NIL节点)

为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

根据规则4，我们可以知道最短路径的节点全为黑色。

根据规则3我们可以知道最长路径为黑色节点与红色节点相间的情况。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1IXA66v7-1677399534592)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226091404627.png)]

所以最长路径节点个数不会超过最短路径节点个数的两倍。

红黑树查找的时间复杂度：

红黑树查找的最差情况（即最长路径）： O（2lgN）

由此可知红黑树的查找是比严格平衡的AVL树要慢一点的，假设处理10亿个数据，AVL需要找30多次，而红黑树也只需要60多次，这对于计算机而言差别不大，最重要的点在于红黑树不需要进行大量的旋转来不断控制平衡。综合考虑下来，红黑树更加好用，这也是map和set的底层都是红黑树的原因之一。

4.3红黑树节点的定义

在有AVL树的基础下，红黑树节点的定义就很容易了。我们只是去掉平衡因子，增加节点的颜色罢了。

enum Colour         //枚举，节点的颜色
{
	RED,
	BLACK,
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _parent;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	pair<K, V> _kv;
	Colour _colour;

	RBTreeNode(const pair<K, V>& kv)
		:_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_kv(kv)
		,_colour(RED)          //节点颜色默认为红
	{}
};
一键获取完整项目代码c++1234567891011121314151617181920212223

插入节点颜色为什么要默认为红色呢？

首先我们来回顾红黑树的前四个性质。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-do8a2Iok-1677399534592)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226093721014.png)]

假设我们插入的节点默认为黑色，我们会发现无论我们怎么插入，都必定会违反了规则4，导致路径上黑色节点的个数不同，最重要的点在于，这种情况很难处理。

如果我们插入的节点默认为红色，我们如果父亲为黑色，我们依然符合规则，不需要进行不断的调整，如果父亲为红色，我们调整的难度也小很多。

综上考虑，插入节点的颜色默认为红色更合适。

4.4红黑树的插入操作

4.4.1按照二叉搜索树的规则插入节点

这一部分与模拟实现AVL树时的操作相同，注意树为空时，将插入的根节点的颜色置为黑色即可。

	bool Insert(const pair<K,V>& kv)
	{
		if (nullptr == _root)
		{
			_root = new Node(kv);
			_root->_colour = BLACK;
			return true;
		}
		//1.按二叉搜索树的方式插入
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (kv.first > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else
			{
				return false;
			}
			Node* cur = new Node(kv);
			cur->_parent = parent;
			if (kv.first < parent->_kv.first)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}

		//2.看是是否违反了红黑树的规则，没有违反直接退出，违反了进行调整操作。

		}
		//根节点颜色可能修改过，最后置为黑色
		_root->_colour = BLACK;
	}
一键获取完整项目代码c++12345678910111213141516171819202122232425262728293031323334353637383940414243

现在真正需要我们进行研究的就是插入的第二部分内容了，如何将插入的情况分类，和如何正确的修改节点以符合红黑树的规则。

4.4.2检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

红黑树的调整主要涉及4个节点分别为cur、parent、grandfather、uncle，其中最重要的点是uncle

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vk8zq4Ab-1677399534592)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226101044362.png)]

情况1：cur为红，p为红，grandfather为黑，u为红。

此时我们将p和u变黑，g变为红即可。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A5ZxMtgu-1677399534593)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226101343570.png)]

如果g是根节点，我们将g的颜色改为黑色即可。如果g的_parent为红，则我们就需要将g当成cur继续向上调整。

情况2：cur为红，p为红，g为黑，u为黑或者u不存在（单旋）

u的情况有两种

1.u不存在，则cur一定是新增的节点。

不会是情况1调整出来的，因为如果是情况1调整出来的cur原本的位置一定是黑色，违反了红黑树的规则4

2.u存在，则u一定是黑色，cur所在的节点原来也一定是黑色，是由情况1调整变为红色的

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VEOO2Z5Q-1677399534593)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226102831277.png)]

此时就需要进行我们熟悉的旋转操作了，与AVL树的旋转相比不涉及平衡因子的调节，因而会更简便

单旋：

单右旋

旋转要求：

p在g的左边，cur在p的左边

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LSL7D5se-1677399534594)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226103955125.png)]

旋转完成后就结束了，已经符合了红黑树的规则

单左旋和右旋的原理一样，相信这对于我们不是什么问题。

情况3:cur为红，p为红，g为黑，u为黑或者u不存在(双旋)

先左单旋，再右旋：p再g的左边，cur再p的右边

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PszRrUJo-1677399534594)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226105239485.png)]

先右单旋，再做单选就刚好相反了。

针对每种情况我们进行相应的处理即可。

bool Insert(const pair<K,V>& kv)
	{
		if (nullptr == _root)
		{
			_root = new Node(kv);
			_root->_colour = BLACK;
			return true;
		}
		//1.按二叉搜索树的方式插入
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (kv.first > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else
			{
				return false;
			}
			
		}
		cur = new Node(kv);
		cur->_parent = parent;
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//2.看是是否违反了红黑树的规则，没有违反直接退出，违反了进行调整操作。
			while (parent && RED == parent->_colour) //g存在，且parent为红，需要调整，再看u节点的情况进行分类
			{
				Node* grandfather = parent->_parent;
				Node* uncle = nullptr;
				if (parent == grandfather->_left)
				{
					uncle = grandfather->_right;
				}
				else
				{
					uncle = grandfather->_left;
				}

				if (uncle &&uncle->_colour == RED) //情况1，c,p，u为红 , g为黑
				{
					parent->_colour = BLACK;
					uncle->_colour = BLACK;
					grandfather->_colour = RED;

					cur = grandfather;         //继续向上调整
					parent = cur->_parent;
				}
				else  //叔叔不存在，或者叔叔为黑
				{
					if (parent == grandfather->_left && cur == parent->_left) //右单旋
					{
						RotateR(grandfather);
					}
					else if (parent == grandfather->_right && cur == parent->_right) //左单旋
					{
						RotateL(grandfather);
					}
					else if (parent == grandfather->_left && cur == parent->_right)//先左旋再右旋
					{
						RotateL(parent);
						RotateR(grandfather);
					}
					else if (parent == grandfather->_right && cur == parent->_left) //先右旋再左旋
					{
						RotateR(parent);
						RotateL(grandfather);
					}
					else
					{
						assert(false);
					}
					break;
				}

			}

		//根节点颜色可能修改过，最后置为黑色
		_root->_colour = BLACK;
		return true;
	}
void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppNode = parent->_parent;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		parent->_parent = subL;

		if (ppNode)
		{
			subL->_parent = ppNode;
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
		}
		else
		{
			subL->_parent = nullptr;
			_root = subL;
		}
		parent->_colour = RED;
		subL->_colour = BLACK;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppNode = parent->_parent;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		subR->_left = parent;
		parent->_parent = subR;

		if (ppNode)
		{
			subR->_parent = ppNode;
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
		}
		else
		{
			subR->_parent = nullptr;
			_root = subR;
		}
		subR->_colour = BLACK;
		parent->_colour = RED;
	}

一键获取完整项目代码c++123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163

4.5红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)
检测其是否满足红黑树的性质

我们再把红黑树的性质看一遍：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KkR12hB3-1677399534594)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226154036722.png)]

我们需要验证的主要就是2，3，4条性质

bool IsBalance()
	{
		//空树返回true
		if (nullptr == _root)
		{
			return true;
		}
		//条件2，根节点为黑色
		if (_root->_colour != BLACK)
		{
			cout << "违反规则2，根节点为黑色" << endl;
			return false;
		}
		//检查是否含有连续的红色节点，检查红色节点的父亲节点是否是红色。 规则3
		//检查规则4，每条路径的黑色节点个数是否相同
		//上面的两种检查都需要递归树，所以直接一起完成。
		int BlackNum = 0; //记录路径上黑色节点的个数 ， 传值传参给递归函数，相当于每个节点都拥有了记录路径上黑色节点个数的变量
		int ref = 0; //最左路径上黑色节点的个数， 作为参考值进行比对。 也可以用容器存储下每个路径的黑色节点个数，这里更推荐用参考值进行比较
		Node* cur = _root;
		while (cur)
		{
			if (cur->_colour == BLACK)
			{
				++ref;
			}
			cur = cur->_left;
		}

		return CheckRBLaw(_root, BlackNum, ref); //BlackNum 可以直接传0，为了方便理解，传个变量
	}

	bool CheckRBLaw(Node* root, int bnum, int ref)
	{
		if (nullptr == root)
		{
			//到空节点处，一条路径上的黑色节点数已统计完毕
			if (bnum != ref)
			{
				cout << "违反规则4，路径上黑色节点数量异常" << endl;
				return false;
			}
			return true;
		}
		if (root->_colour == RED && root->_parent->_colour == RED)
		{
			cout << "违反规则3，存在连续的红色节点" << endl;
			return false;
		}
		if (root->_colour == BLACK)
		{
			bnum++;
		}

		return CheckRBLaw(root->_left, bnum, ref) && CheckRBLaw(root->_right, bnum, ref);
	}
一键获取完整项目代码c++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jWH5eFtB-1677399534595)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226160021050.png)]

经受住了大量随机数的考验

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fxTd3A1Y-1677399534595)(C:\Users\2119869498\AppData\Roaming\Typora\typora-user-images\image-20230226161437989.png)]

泪目，经受住了测试。

测试案例：

void test1()
{
	RBTree<int, int> t1;
	//int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//特殊情况
	int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//常规情况
	for (auto e : arr)
	{
		t1.Insert(make_pair(e, e));
	}
	t1.Inorder();
	cout << t1.IsBalance();
}

void test2()
{
	RBTree<int, int> t;
	srand(0);
	int N = 1000000;
	while (N--)
	{
		size_t x = rand();
		t.Insert(make_pair(x, x));
	}

	cout << t.IsBalance() << endl;
}
一键获取完整项目代码c++1234567891011121314151617181920212223242526

4.6红黑树的模拟实现

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
enum Colour         //枚举，节点的颜色
{
	RED,
	BLACK,
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _parent;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	pair<K, V> _kv;
	Colour _colour;

	RBTreeNode(const pair<K, V>& kv)
		:_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_kv(kv)
		,_colour(RED)          //节点颜色默认为红
	{}
};

template<class K,class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;
	RBTree()
		:_root(nullptr)
	{}

	bool Insert(const pair<K,V>& kv)
	{
		if (nullptr == _root)
		{
			_root = new Node(kv);
			_root->_colour = BLACK;
			return true;
		}
		//1.按二叉搜索树的方式插入
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (kv.first > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else
			{
				return false;
			}
			
		}
		cur = new Node(kv);
		cur->_parent = parent;
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//2.看是是否违反了红黑树的规则，没有违反直接退出，违反了进行调整操作。
			while (parent && RED == parent->_colour) //g存在，且parent为红，需要调整，再看u节点的情况进行分类
			{
				Node* grandfather = parent->_parent;
				Node* uncle = nullptr;
				if (parent == grandfather->_left)
				{
					uncle = grandfather->_right;
				}
				else
				{
					uncle = grandfather->_left;
				}

				if (uncle &&uncle->_colour == RED) //情况1，c,p，u为红 , g为黑
				{
					parent->_colour = BLACK;
					uncle->_colour = BLACK;
					grandfather->_colour = RED;

					cur = grandfather;         //继续向上调整
					parent = cur->_parent;
				}
				else  //叔叔不存在，或者叔叔为黑
				{
					if (parent == grandfather->_left && cur == parent->_left) //右单旋
					{
						RotateR(grandfather);
					}
					else if (parent == grandfather->_right && cur == parent->_right) //左单旋
					{
						RotateL(grandfather);
					}
					else if (parent == grandfather->_left && cur == parent->_right)//先左旋再右旋
					{
						RotateL(parent);
						RotateR(grandfather);
					}
					else if (parent == grandfather->_right && cur == parent->_left) //先右旋再左旋
					{
						RotateR(parent);
						RotateL(grandfather);
					}
					else
					{
						assert(false);
					}
					break;
				}

			}

		//根节点颜色可能修改过，最后置为黑色
		_root->_colour = BLACK;
		return true;
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppNode = parent->_parent;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		parent->_parent = subL;

		if (ppNode)
		{
			subL->_parent = ppNode;
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
		}
		else
		{
			subL->_parent = nullptr;
			_root = subL;
		}
		parent->_colour = RED;
		subL->_colour = BLACK;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppNode = parent->_parent;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		subR->_left = parent;
		parent->_parent = subR;

		if (ppNode)
		{
			subR->_parent = ppNode;
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
		}
		else
		{
			subR->_parent = nullptr;
			_root = subR;
		}
		subR->_colour = BLACK;
		parent->_colour = RED;
	}

	void Inorder()
	{
		_Inorder(_root);
	}

	bool IsBalance()
	{
		//空树返回true
		if (nullptr == _root)
		{
			return true;
		}
		//条件2，根节点为黑色
		if (_root->_colour != BLACK)
		{
			cout << "违反规则2，根节点为黑色" << endl;
			return false;
		}
		//检查是否含有连续的红色节点，检查红色节点的父亲节点是否是红色。 规则3
		//检查规则4，每条路径的黑色节点个数是否相同
		//上面的两种检查都需要递归树，所以直接一起完成。
		int BlackNum = 0; //记录路径上黑色节点的个数 ， 传值传参给递归函数，相当于每个节点都拥有了记录路径上黑色节点个数的变量
		int ref = 0; //最左路径上黑色节点的个数， 作为参考值进行比对。 也可以用容器存储下每个路径的黑色节点个数，这里更推荐用参考值进行比较
		Node* cur = _root;
		while (cur)
		{
			if (cur->_colour == BLACK)
			{
				++ref;
			}
			cur = cur->_left;
		}

		return CheckRBLaw(_root, BlackNum, ref); //BlackNum 可以直接传0，为了方便理解，传个变量
	}

	bool CheckRBLaw(Node* root, int bnum, int ref)
	{
		if (nullptr == root)
		{
			//到空节点处，一条路径上的黑色节点数已统计完毕
			if (bnum != ref)
			{
				cout << "违反规则4，路径上黑色节点数量异常" << endl;
				return false;
			}
			return true;
		}
		if (root->_colour == RED && root->_parent->_colour == RED)
		{
			cout << "违反规则3，存在连续的红色节点" << endl;
			return false;
		}
		if (root->_colour == BLACK)
		{
			bnum++;
		}

		return CheckRBLaw(root->_left, bnum, ref) && CheckRBLaw(root->_right, bnum, ref);
	}


private:
	void _Inorder(Node* root)
	{
		if (nullptr == root)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_Inorder(root->_right);
	}



	Node* _root;
};
一键获取完整项目代码c++123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279

Ⅴ.总结和体悟

很感谢能看到这里的大家，这篇博客应该是我所写过的最长的一篇博客了，1w2千多的字，从二叉搜索树到改造为kv结构，再到十道经典题目的练手，再到AVL树的模拟实现，最后解决最终Boss红黑树，虽然AVL树和红黑树都只介绍了插入部分，但其中的精髓相信大家都已经体会到了。

学习不是一蹴而就的，最终之所以能坦然解决红黑树，也是前面那么一长段的铺垫所带来的，如果赶紧博主的这篇博客给你带来了感悟的话希望能得到你的赞和收藏，感谢了！

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

1+X 认证

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

1+X 认证