数据结构之进阶二叉树（二叉搜索树和AVL树、红黑树的实现）超详细解析，附实操图和搜索二叉树的实现过程图

绪论​
“生命有如铁砧，愈被敲打，愈能发出火花。——伽利略”；本章主要是数据结构 二叉树的进阶知识，若之前没学过二叉树建议看看这篇文章一篇掌握二叉树，本章的知识从浅到深的对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解，希望能对你有所帮助。话不多说安全带系好，发车啦（建议电脑观看）。

1.二叉搜索树

1.1二叉搜索树的概念:

在这里插入图片描述
二叉搜索树又称二叉排序树/二叉查找树**，它或者是一棵空树。二叉搜索树还有二叉树的性质不同的是其性质有：
1. 大于子树根节点的值存在根节点的右子树
2. 小于子树根节点的值存在根节点的左子树
3. 左右子树都是二叉搜索树
换种说法：若它的左子树不为空，则左子树上所有节点的值都小于根节点的值、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。

1.2二叉树搜索树一些常用功能（基本功能）

1.2.1 插入数据

有了前面的二叉搜索树的性质后，能很好的想到其插入的实现，只不过其中会有一些小的细节需要注意！
主要是判断当前子树根节点的值和传进来的值进行比较，然后当走到为空时，表示就是为要插入的位置
注意细节：

  1. 当根节点为空时，修改根节点即可。
  2. 我们需要记录父节点然后链接父子节点。

具体见下面代码：

bool Insert(const K& key, const V& val)
{if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key){return false;//不插入相同的值}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}//当循环结束表示已经到了所要插入节点的位置！cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;
}

1.2.2 删除数据

对于删除数据来说有几个不同的情况：

  1. 当删除节点没有左右节点时，我们直接将其节点删除即可
    在这里插入图片描述
  2. 当删除节点只有左节点/右节点时
    将这个左节点/右节点链接到删除节点的父节点在这里插入图片描述
  3. 当删除节点用同时有两个节点
    使用替换删除法（找到删除节点左子树的最右节点（最大节点）/删除节点右子树的最左节点（最小节点）后替换到删除的节点后删除，不过删除的时候要注意链接（2）！）
    在这里插入图片描述
    注意：假如交换的节点有子树那么需要注意将其链接到交换节点的父节点
    在这里插入图片描述

此处可以把1和2情况并到一起写，即当有左为空/右为空时不管右/左为不为空都连接到其父节点
具体代码实现：

bool Erase(const K& key)
{Node* parent = nullptr, * child = nullptr;//删除节点的父亲Node* cur = _root;//所要删除的节点while (cur){if (cur->_key == key) //找到删除节点{//可以把左右为空和 左或右不为空写在一起if (cur->_left == nullptr)//当其左边为空时{if (cur == _root){_root = cur->_right;}else{//即当有左为空时不管删除节点的右为不为空都直接连接到其父节点if (parent->_left == cur)//判断在父节点的左边还是右边{parent->_left = cur->_right;}else// if (parent->_right = cur){parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//当其右边为空时{if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur;}else// if (parent->_right = cur){parent->_right = cur;}}delete cur;}else//当左右同时不为空时{//找到删除节点左子树的最大值/右子树的最小值、与删除节点交换//找到左子树的最右节点Node* tmp = cur->_left;//最右节点Node* p = cur;//最右节点的父节点while (tmp->_right){p = tmp;tmp = tmp->_right;}//父节点链接 最右节点的左节点if (p->_right == tmp) {p->_right = tmp->_left;}else {p->_left = tmp->_left;}swap(tmp->_key, cur->_key);//交换后删除即可delete tmp;}return true;}else if (cur->_key > key)//找不到继续循环{parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}return false;
}

1.2.3查找数据

直接利用二叉搜索树的性质即可很好的写出查找
通过大的在右小的在左的性质，就能最多树的层数次就能找到
若找不到则就会找到空的位置处

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key == key){return cur;//找到返回该节点}else if (cur->_key > key){cur = cur->_left;}else{cur = cur->_right;}}return nullptr;//找不到则返回nullptr
}

1.3二叉树搜索树基本功能用递归式实现

从代码直接分析，若有啥问题可以评论提出喔！

1.3.1插入

bool _InsertR(Node*& root, const K& key)//递归式插入 Recursion
{if (root == nullptr){//此处为引用也就是别名，当修改root就其实就是修改到了树（就不用链接了）root = new Node(key);return true;}if (root->_key == key)//若相等则表示已经插入过了那么返回错误{return false;}else if (root->_key > key)//当root值大于key时往左走{return _InsertR(root->_left, key);}else//当root值小于key时往右走{return _InsertR(root->_right, key);}
}

1.3.2删除

bool _EraseR(Node*& root, const K& key)
{//同样当左右无节点时直接删除//当只有左或者只有右时，链接其右或左到祖先即可//当同时有左右子树时交换删除if (root == nullptr) {//为空表示不存在返回空return false;}if (root->_key > key)//当root值大于key时往左走{return _EraseR(root->_left, key);}else if (root->_key < key)//当root值小于key时往右走{return _EraseR(root->_right, key);}else//找到后{if (root->_left == nullptr){Node* tmp = root;root = root->_right;//因为root是引用，所以当修改root后会影响到整棵树delete tmp;//再将原本的root给释放了return true;}else if (root->_right == nullptr){Node* tmp = root;root = root->_left;//因为root是引用，所以当修改root后会影响到整棵树delete tmp;//再将原本的root给释放了return true;}else{Node* tmp = root->_left;//找到左子树的最大值（最右值）while (tmp->_right){tmp = tmp->_right;}swap(tmp->_key, root->_key);//交换return _EraseR(root->_left, key);//通过递归删除把key删除，里面就包含了链接}}
}

1.3.3查找

此处如果你已经理解了上面的那么这里就非常简单了就不过诉了

Node* _FindR(Node* root, const K& key)
{if (root == nullptr){return nullptr;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}
}

1.4二叉搜索树的源码

如果是要学习的话，建议一定要将整体的结构框架理清楚了，下面是二叉搜索树的整体代码，包括了构造函数、析构函数、以及一些还没交代的函数。

template<class K>
struct BSTreeNode
{BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:BSTree() = default;~BSTree(){_Destory(_root);}//BSTree(const BSTree<K>& t)//{//	_Copy(t._root);//}BSTree(const BSTree<K>& t){_root = _Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){//_Destory(_root);//_Copy(t._root);swap(_root, t._root);//现代写法return *this;}void InOrder(){_InOrder(_root);}bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key){return false;//不插入相同的值}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}//当循环结束表示已经到了所要插入节点的位置！cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key == key){return cur;//不插入相同的值}else if (cur->_key > key){cur = cur->_left;}else{cur = cur->_right;}}return nullptr;}//替换法 删除//找到删除节点的左子树的最大值(最左子树的右节点)/右子树的最小值(右子树的最左节点)后与删除的位置进行交换bool Erase(const K& key){Node* parent = nullptr, * child = nullptr;//删除节点的父亲Node* cur = _root;//所要删除的节点while (cur){if (cur->_key == key){//if (cur->_left == nullptr &&//	cur->_right == nullptr)//{//	delete cur;//}//else if (del->_left && del->_right)//{//	//MaxNode(del->_left);//左子树的最大值//	Node* min = MinNode(del->_right); //右子树的最小值//	swap(del, min);//	delete del;//}//可以把左右为空和 左或右不为空写在一起if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else// if (parent->_right = cur){parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur;}else// if (parent->_right = cur){parent->_right = cur;}}delete cur;}else{//找到删除节点左子树的最大值/右子树的最小值、与删除节点交换//交换后删除即可Node* tmp = cur->_left;Node* p = cur;while (tmp->_right){p = tmp;tmp = tmp->_right;}if (p->_right == tmp) {p->_right = tmp->_left;}else {p->_left = tmp->_left;}swap(tmp->_key, cur->_key);delete tmp;}return true;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}return false;}bool InsertR(const K& key)//递归式插入 Recursion{return _InsertR(_root, key);}Node* FindR(const K& key){return _FindR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}private:void _Destory(Node* root){if (root == nullptr) return;_Destory(root->_left);_Destory(root->_right);delete root;}//void _Copy(Node* root)//{//	if (root == nullptr) return;//	_InsertR(_root, root->_key);//	_Copy(root->_left);//	_Copy(root->_right);//}Node* _Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key);newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);return newRoot;}void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}//判断root->_key 与 keybool _InsertR(Node*& root, const K& key)//递归式插入 Recursion{if (root == nullptr){root = new Node(key);//此处为引用也就是别名，当修改root就其实就是修改到了树return true;}if (root->_key == key){return false;}else if (root->_key > key){return _InsertR(root->_left, key);}else{return _InsertR(root->_right, key);}}Node* _FindR(Node* root, const K& key){if (root == nullptr){return nullptr;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}bool _EraseR(Node*& root, const K& key){//同样当左右无节点时直接删除//当只有左或者只有右时，链接其右或左到祖先即可//当同时有左右子树时交换删除if (root == nullptr) {return false;}if (root->_key > key){return _EraseR(root->_left, key);}else if (root->_key < key){return _EraseR(root->_right, key);}else{if (root->_left == nullptr){Node* tmp = root;root = root->_right;//因为root是引用，所以当修改root后会影响到整棵树delete tmp;//再将原本的root给释放了return true;}else if (root->_right == nullptr){Node* tmp = root;root = root->_left;//因为root是引用，所以当修改root后会影响到整棵树delete tmp;//再将原本的root给释放了return true;}else{Node* tmp = root->_left;//找到左子树的最大值（最右值）while (tmp->_right){tmp = tmp->_right;}swap(tmp->_key, root->_key);//交换return _EraseR(root->_left, key);//通过递归删除把key删除，里面就包含了链接}}}Node* _root;
};

1.5二叉搜索树的应用

  1. k模型，K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。如:给一个单词word，判断该单词是否拼写正确。
  2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：英汉词典就是英文与中文对应关系<English，meaning>、或者统计个数对应的就是元素和个数的关系<ele,count>。

在上面我们写的是就是k模型，下面我们将其修改为kv模型(对于k模型来说大概的都不需要修改只有一部分需要简单修改)
具体代码为：

template<class K, class V>
struct BSTreeNode
{BSTreeNode(const K& key, const V& val):_key(key), _val(val), _left(nullptr), _right(nullptr){}K _key;V _val;BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public:BSTree():_root(nullptr){}void InOrder(){_InOrder(_root);}bool Insert(const K& key, const V& val){//1. 当根节点为空时，修改根节点即可。if (_root == nullptr){_root = new Node(key, val);return true;}//2. 我们需要记录父节点然后链接父子节点。Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == key){return false;//不插入相同的值}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}//当循环结束表示已经到了所要插入节点的位置！cur = new Node(key, val);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key == key){return cur;//不插入相同的值}else if (cur->_key > key){cur = cur->_left;}else{cur = cur->_right;}}return nullptr;}//替换法 删除//找到删除节点的左子树的最大值(最左子树的右节点)/右子树的最小值(右子树的最左节点)后与删除的位置进行交换bool Erase(const K& key){Node* parent = nullptr, * child = nullptr;//删除节点的父亲Node* cur = _root;//所要删除的节点while (cur){if (cur->_key == key) //找到删除节点{if (cur->_left == nullptr)//当其左边为空时{if (cur == _root){_root = cur->_right;}else{//即当有左为空时不管删除节点的右为不为空都直接连接到其父节点if (parent->_left == cur)//判断在父节点的左边还是右边{parent->_left = cur->_right;}else// if (parent->_right = cur){parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//当其右边为空时{if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur;}else// if (parent->_right = cur){parent->_right = cur;}}delete cur;}else//当左右同时不为空时{//找到删除节点左子树的最大值/右子树的最小值、与删除节点交换//找到左子树的最右节点Node* tmp = cur->_left;//最右节点Node* p = cur;//最右节点的父节点while (tmp->_right){p = tmp;tmp = tmp->_right;}//父节点链接 最右节点的左节点if (p->_right == tmp) {p->_right = tmp->_left;}else {p->_left = tmp->_left;}swap(tmp->_key, cur->_key);//交换后删除即可delete tmp;}return true;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}return false;}private:void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << '-' << root->_val << " ";_InOrder(root->_right);}Node* _root = nullptr;
};

英汉词典实现：

int main()
{kv::BSTree<string, string> dict;//插入单词dict.Insert("sort", "种类");dict.Insert("left", "左边");dict.Insert("right", "右边");dict.Insert("insert", "插入");dict.Insert("key", "钥匙");string str;while (cin>>str)//输入所要查找的单词{kv::BSTreeNode<string, string>* ret = dict.Find(str);if (ret){cout << ret->_val << endl;}else{cout << "不存在" << endl;}}return 0;
}

在这里插入图片描述

计数实现：

int main()
{string arr[] = { "苹果", "苹果","梨子", "香蕉", "苹果", "桃子", "哈密瓜", "梨子", "苹果", "西瓜", "哈密瓜", "苹果", "桃子" };kv::BSTree<string, int> countTree;for (auto& e : arr){kv::BSTreeNode<string, int>* ret = countTree.Find(e);if (ret == nullptr){countTree.Insert(e, 1);}else{ret->_val++;}}countTree.InOrder();return 0;
}

在这里插入图片描述

2.键值对、关联式容器、序列式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器。因为其底层为线性序列的数据结构，里面存储的是元素本身。关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。
键值对用来表示具有一 一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
键值对可以用一个新的变量 pair<K,V> 表示
其结构可以看成：

template <class T1, class T2>
struct pair
{T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1& a, const T2& b): first(a), second(b){}
};

有了上面这个类，我们可以定义一个变量为 pair<int,int> _kv
这样就能调用其内部的元素：_kv.first代表第一个元素K、_kv.second表示第二个元素
或者为pair<int,int>* _kv,_kv->first同样代表第一个元素、_kv->second表示第二个元素

3.AVL树

3.1AVL树的概念

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

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

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

3.2AVL树的构造

AVL树是一个三叉树，他的节点有三个指针分别指向左孩子、右孩子、父节点，还有一个值（这个值是kv模型的）和一个平衡因子。

具体如下：

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K,V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}AVLTreeNode<K,V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;   // 节点的平衡因子 balance factor
};

3.3AVL树的基本功能

3.3.1平衡因子

在某个根上其左右子树的高度差（左子树的高度- 右子树的高度）

例子：直接通过下面的图来理解：
在这里插入图片描述

上图中在原图上的左子树的子叶增加元素（可增加该左子树的左边或者右边）
一开始可以看到所有的根的平衡因子都为0因为左右子树的高度一样。

  1. 当在最左边加上一个节点后，其平衡被打破为-1（根的左子树增加一个(所以根的右子树-左子树 = -1)，对于该左子树来说也是其左子树增加所以同样的平衡变成 -1）
  2. 当在左子树的最右加上一个节点后，对于根来说仍然是左子树有变高（所以还是-1），而对于该左子树来说那就是其右子树增加了（那么右子树-左子树=1）

在上面插入新节点的例子中仍然满足平衡二叉树的平衡条件（左右孩子的高度差不超过1），如果出现平衡因子出现问题的话那就需要去旋转！（具体请继续往下看）

3.3.2插入（以及插入中的左旋、右旋、左右双旋、右左双旋的问题）

AVL树的插入本质上还是搜索二叉树的插入，但因为加入了平衡因子的所就可能出现一下问题：当插入一个节点后其平衡因子只可能变成 1，0，-1，-2，2
那么这几个平衡因子产生的情况又能分为几种情况：
附：下面的例子中的长方框表示着子树，而小框就表示新增的节点

  1. 当平衡因子变成了0 ： 那么表示新增节点后使平衡，那么其实是不用做什么的，因为该子树的层数并没有增加，仅仅只需把该子树的平衡因子改成0即可。在这里插入图片描述

  2. 当平衡因子变成了1/-1：那么表示该子树的层数发生了改变，那么连锁的也会导致上方的祖先的平衡因子发生改变。在这里插入图片描述
    如何向上调整：改变cur和parent的关系即可（cur = parent，parent = parent->parent）

  3. 当平衡因子变成-2/2：此时表示在原本高的一方又加了一个节点，那么此时因为平衡因子的错误，那么需要去旋转来解决这个问题。
    旋转又分为多种情况：
    附：在下面多以cur和parent的关系为一棵子树来看。
    1.右旋：当在左子树的左边新增元素（左左），此时因为原本为-1的p再在左边加元素后就变成了-2，此时就需要对cur进行右旋，方法为：将把cur的右子树链接成parent，再把parent的左子树换成cur的右子树（此时就断开了链接）（具体如下图）在这里插入图片描述
    旋转后cur = p = 0
    代码：

void RotateR(Node* parent)
{Node* SubL = parent->_left;//此处就为 curNode* SubLR = SubL->_right;//parent的左换成cur的右parent->_left = SubLR;//把cur的右孩子换成parentSubL->_right = parent;//注意还要修改其父指针Node* Ppnode = parent->_parent;parent->_parent = SubL;if (SubLR)//cur的右边可能为空SubLR->_parent = parent;if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr{_root = SubL;SubL->_parent = nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode->_left == parent){Ppnode->_left = SubL;}else{Ppnode->_right = SubL;}SubL->_parent = Ppnode;}SubL->_bf = 0;parent->_bf = 0;
}

2.左旋：当在右子树的右边新增节点（右右），同样的就是 p就将变成2，此时要用对cur左旋，方法为：将cur的左子树断开链接为p，再把p的右子树断开链接成cur的左子树在这里插入图片描述
旋转后cur = p = 0
代码：

void RotateL(Node* parent)
{Node* SubR = parent->_right;//此处就为 curNode* SubRL = SubR->_left;//parent的右换成cur的左parent->_right = SubRL;//把cur的左孩子换成parentSubR->_left = parent;Node* Ppnode = parent->_parent;//注意 还要修改其父指针parent->_parent = SubR;if (SubRL)//右边可能为空SubRL->_parent = parent;if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr{_root = SubR;SubR->_parent = nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode->_left == parent){Ppnode->_left = SubR;}else{Ppnode->_right = SubR;}SubR->_parent = Ppnode;}SubR->_bf = 0;parent->_bf = 0;
}

3.左右双旋：此处我们先定义p（parent）、subL（parent的左子树）、subLR（subL的右子树），当在左子树的右边新增节点（左右），此时我们先对 subL和subLR 组成的子树进行左旋后，再对p和subLR组成的子树进行右旋。其中有两种可能，当插入到subLR的左边/subLR的右边时他们对平衡因子的影响是不一样的我们需要分开讨论，具体见下图：在这里插入图片描述
旋转后当在subLR的左边插入的话 subLR = subL = 0， p = 1，若在subLR的右边插入的话则subLR = p = 0 ， subL = -1
代码：

void RotateLR(Node* parent)
{Node* subL = parent->_left;//此处就为 curNode* subLR = subL->_right;int bf = subLR->_bf; //先对cur 进行左旋 再对 parent进行右旋RotateL(subL);RotateR(parent);if (bf == 0)//自己为新增{parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == -1){// subRL的左子树新增parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){// subRL的右子树新增parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}
}

4.右左双旋：此处我们先定义p（parent）、subR（parent的右子树）、subRL（subR的左子树），当在右子树的左边新增节点（右左），此时我们先对 subR和subRL 组成的子树进行右旋后，再对p和subRL组成的子树进行左旋。其中有两种可能，当插入到subRL的左边/subRL的右边时他们只是对平衡因子的影响是不一样的我们需要分开讨论，具体见下图：在这里插入图片描述
旋转后当在subLR的左边插入的话 subRL = p = 0， subR = 1，若在subLR的右边插入的话则subRL = subR = 0， p = 1
代码：

void RotateRL(Node* parent)
{Node* subR = parent->_right;//此处就为 curNode* subRL = subR->_left;int bf = subRL->_bf;//先对cur 进行左旋 再对 parent进行右旋RotateR(subR);RotateL(parent);if (bf == 0)//自己为新增{parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == -1){// subRL的左子树新增subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){// subRL的右子树新增subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else{assert(false);}
}

对于插入函数代码：

bool Insert(const pair<K,V>& kv)
{//平衡二叉树 ： 左子树的值都小于根的值 、 右子树的值都大于根的值Node* cur = _root;Node* parent = nullptr;if (!_root) {_root = new Node(kv);return true;}//1.找到所要插入的位置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;}}//2. 确立位置后 ， new出新节点在cur处，然后在建立 链接关系//关系：// cur 没有左右为null// 主要是改变其_parent 和 父亲的left/right, 而要去判断cur 在 _parent的左还是右  通过比较kv.first 和 父亲的kv.first的值//此处parent 为其 父亲cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;//注意此处也要改变 cur 的 _parentcur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent){//建立链接后，因为有了新插入的节点 故需要 先修改平衡因子//某个根节点的平衡因子为 ： 右孩子的_bf（平衡因子） - 左孩子的_bf//插入后 父亲可能的情况为：//-2: 左边高插到了左//-1: 平衡到 插左边 //0 : 1 / -1 -> 插到左或右 // //1 : 平衡插右边//2 : 右 右if (cur == parent->_left){parent->_bf--;}else if (cur == parent->_right){parent->_bf++;}//分析不同的情况对应的修改平衡因子if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1)//当父亲的平衡因子为1，表示该子树的层数有了增加，但任然是满足AVL树的条件{											   //因为子树层数的增加，则对应的会影响到祖先，故需要向上修改祖先的平衡因子cur = parent;parent = parent->_parent;}else if(parent->_bf == 2 || parent->_bf == -2)//当父亲的bf 为 2/-2 时则已经影响到了AVL树的平衡，故需要去通过旋转来保证AVL树{if (parent->_bf == -2 && cur->_bf == -1)//左左{//进行对父节点的右旋RotateR(parent);}if (parent->_bf == -2 && cur->_bf == 1)//左右{//先右旋再左旋RotateLR(parent);}if (parent->_bf == 2 && cur->_bf == 1)//右右{//左旋RotateL(parent);}if (parent->_bf == 2 && cur->_bf == -1)//右左{//先左旋再右旋RotateRL(parent);}//注意此处当旋转完后就直接break跳出循环了，因为其在内部已经将平衡因子调整好了，不用再考虑祖先平衡因子问题// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新break;}else {assert(0);}}return true;
}

3.4AVL树的源码

在其中还包括了一些扩展功能

  1. 求树的高度（_Height）。
  2. 判断而AVL的每个节点是否满足平衡条件（IsBalance），这个函数是用来测试该AVL树是否满足条件的，实现原理为：遍历整个二叉树，并且在过程中判断其左右子树的差是否满足平衡条件。
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K,V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}AVLTreeNode<K,V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;   // 节点的平衡因子 balance factor
};// AVL: 二叉搜索树 + 平衡因子的限制
template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K,V> Node;//通过模板将node确定类型
public:AVLTree():_root(nullptr){}// 在AVL树中插入值为data的节点bool Insert(const pair<K,V>& kv){//平衡二叉树 ： 左子树的值都小于根的值 、 右子树的值都大于根的值Node* cur = _root;Node* parent = nullptr;if (!_root) {_root = new Node(kv);return true;}//1.找到所要插入的位置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;}}//2. 确立位置后 ， new出新节点在cur处，然后在建立 链接关系//关系：// cur 没有左右为null// 主要是改变其_parent 和 父亲的left/right, 而要去判断cur 在 _parent的左还是右  通过比较kv.first 和 父亲的kv.first的值//此处parent 为其 父亲cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;//注意此处也要改变 cur 的 _parentcur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent){//建立链接后，因为有了新插入的节点 故需要 先修改平衡因子//某个根节点的平衡因子为 ： 右孩子的_bf（平衡因子） - 左孩子的_bf//插入后 父亲可能的情况为：//-2: 左边高插到了左//-1: 平衡到 插左边 //0 : 1 / -1 -> 插到左或右 // //1 : 平衡插右边//2 : 右 右if (cur == parent->_left){parent->_bf--;}else if (cur == parent->_right){parent->_bf++;}//分析不同的情况对应的修改平衡因子if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1)//当父亲的平衡因子为1，表示该子树的层数有了增加，但任然是满足AVL树的条件{											   //因为子树层数的增加，则对应的会影响到祖先，故需要向上修改祖先的平衡因子cur = parent;parent = parent->_parent;}else if(parent->_bf == 2 || parent->_bf == -2)//当父亲的bf 为 2/-2 时则已经影响到了AVL树的平衡，故需要去通过旋转来保证AVL树{if (parent->_bf == -2 && cur->_bf == -1)//左左{//进行对父节点的右旋RotateR(parent);}if (parent->_bf == -2 && cur->_bf == 1)//左右{//先右旋再左旋RotateLR(parent);}if (parent->_bf == 2 && cur->_bf == 1)//右右{//左旋RotateL(parent);}if (parent->_bf == 2 && cur->_bf == -1)//右左{//先左旋再右旋RotateRL(parent);}//注意此处当旋转完后就直接break跳出循环了，因为其在内部已经将平衡因子调整好了，不用再考虑祖先平衡因子问题// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新break;}else {assert(0);}}return true;}// AVL树的验证bool IsBalance(){return _IsBalance(_root);}private:// 根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsBalance(Node* root){//主要是平衡因子的判断//此处不同用bf ， 此处应该用height来确定bf是否正确if (!root) return true;int leftbf = _Height(root->_left);int rightbf = _Height(root->_right);if (rightbf - leftbf != root->_bf) {cout << "平衡因子出问题" << endl;}if (abs(rightbf - leftbf) > 1)return false;return _IsBalance(root->_left)&& _IsBalance(root->_right);}size_t _Height(Node* root){if (!root) return 0;int LeftchildTreeHeight = _Height(root->_left);int RightchildTreeHeight = _Height(root->_right);return LeftchildTreeHeight > RightchildTreeHeight ? LeftchildTreeHeight + 1 : RightchildTreeHeight + 1;}// 右单旋// 把cur的右孩子换成parent，parent的左换成cur的右void RotateR(Node* parent){Node* SubL = parent->_left;//此处就为 curNode* SubLR = SubL->_right;//parent的左换成cur的右parent->_left = SubLR;//把cur的右孩子换成parentSubL->_right = parent;//注意还要修改其父指针Node* Ppnode = parent->_parent;parent->_parent = SubL;if (SubLR)//cur的右边可能为空SubLR->_parent = parent;if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr{_root = SubL;SubL->_parent = nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode->_left == parent){Ppnode->_left = SubL;}else{Ppnode->_right = SubL;}SubL->_parent = Ppnode;}SubL->_bf = 0;parent->_bf = 0;}// 左单旋// 同理void RotateL(Node* parent){Node* SubR = parent->_right;//此处就为 curNode* SubRL = SubR->_left;//parent的右换成cur的左parent->_right = SubRL;//把cur的左孩子换成parentSubR->_left = parent;Node* Ppnode = parent->_parent;//注意 还要修改其父指针parent->_parent = SubR;if (SubRL)//右边可能为空SubRL->_parent = parent;if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr{_root = SubR;SubR->_parent = nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode->_left == parent){Ppnode->_left = SubR;}else{Ppnode->_right = SubR;}SubR->_parent = Ppnode;}SubR->_bf = 0;parent->_bf = 0;}// 右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;//此处就为 curNode* subRL = subR->_left;int bf = subRL->_bf;//先对cur 进行左旋 再对 parent进行右旋RotateR(subR);RotateL(parent);if (bf == 0)//自己为新增{parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == -1){// subRL的左子树新增subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){// subRL的右子树新增subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else{assert(false);}}// 对于在 左子树的 右边加元素的情况 ， 用左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;//此处就为 curNode* subLR = subL->_right;int bf = subLR->_bf; //先对cur 进行左旋 再对 parent进行右旋RotateL(subL);RotateR(parent);if (bf == 0)//自己为新增{parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == -1){// subRL的左子树新增parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){// subRL的右子树新增parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}}
private:Node* _root;
};

4.红黑树

4.1红黑树的概念

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

4.2红黑树的性质

红黑树有的性质：

  1. 每个节点不是黑色就是红色
  2. 树的根节点必须是黑色
  3. 如果根节点为红色那么其左右子树必须为黑色节点（不能出现连续的红色节点）
  4. 每条路径的黑色节点个数是一样的

注意：其中路径要包括到null节点处的路径
在这里插入图片描述
红黑树确保没有一条路径会比其他路径长出俩倍：
最短路径：是一条全黑节点的路径
最长路径：是在有相同个黑色节点的前提下穿插着红色节点
具体如下图：
在这里插入图片描述

4.3红黑树结构的定义

结构是由三叉链（包括了左右父链接）、pair<K,V>值，颜色组成。

enum Color
{BLACK,RED
};template<class K , class V>
struct RBTreeNode {RBTreeNode<K,V>* _left = nullptr;RBTreeNode<K,V>* _right = nullptr;RBTreeNode<K,V>* _parent = nullptr;pair<K, V> _kv;Color _col = RED;//默认生成的节点颜色是红色RBTreeNode(const pair<K,V>& kv):_kv(kv){}
};

4.3红黑树结构的基本功能

4.3.1插入数据

在这里插入图片描述
插入数据（此处的红黑树是在cur、parent、grandfather、uncle中来看）后面在这个颗树中主要分为三种情况：
在g的左边插入（其中默认插入的节点是红色节点、旋转和AVL树是一样的）时：

  1. 当p为红，g、u为黑时插入节点cur。此时把p、u改成黑色将g改成红色，再向上调整把（cur = g ， p = g->p）
    在这里插入图片描述
  2. 当p为红，g为黑、u存在且为黑时插入新节点。

当在左边插入时，就先对局部左边进行变色（情况一），变色后向上调整c、p、g、u，再进行右旋（在向上调整后的树上）后再变色（将p变成黑、g变成黑）。
在这里插入图片描述
当在右边插入时，同样先变色（情况一），后向上调整，再进行先左旋和右旋后再进行变色（将g变成红色、c变成黑色）。
在这里插入图片描述
3. 当g为黑，p、c也为红、u为空时
此时先左旋+变色（p变成黑色、g变成红色）在这里插入图片描述
在g的右边插入时：是一样的就不过诉了

下面通过代码来看：

// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
// 注意：为了简单起见，本次实现红黑树不存储重复性元素
bool Insert(const pair<K,V>& kv)
{//此处和AVL平衡二叉树的性质一样找到所要插入节点的位置 大的在右 、 小的在左Node* parent = nullptr;Node* cur = _root;if (cur == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//找到插入的位置！while (cur)//当为null时表示此处就是要插入的位置！{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);//建立新节点//建立链接if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//插入时要判断插入后是否会导致不平衡！对于红黑树来说主要问题有//1. 不能出现连续的红节点//2. 最长路径不超过最短路径的两倍//判断是否需要变色/旋转// //1.当父亲节点为黑色时，当新增了一个红色节点时就结束插入了// //2.当父为红时：//	情况一(仅变色即可)：当parent为红 grandfather为黑 uncle存在且为黑 插入一个新节点// //while (parent && parent->_col == RED){Node* g = parent->_parent;//grandfatherif (g->_left == parent){Node* u = g->_right;//uncleif (u && u->_col == RED)//u存在且为红{//变色即可u->_col = parent->_col = BLACK;g->_col = RED;//向上调整cur = g;parent = g->_parent;//当g 的 父亲为黑时或者为null时停止调整}else //u不存在或者为黑{if (cur == parent->_left)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可{//旋转加变色RotateR(g);parent->_col = BLACK;g->_col = RED;}else{//旋转加变色RotateL(parent);RotateR(g);cur->_col = BLACK;g->_col = RED;}}}else{Node* u = g->_left;//uncleif (u && u->_col == RED)//u存在且为红{//变色即可u->_col = parent->_col = BLACK;g->_col = RED;//向上调整cur = g;parent = g->_parent;//当g 的 父亲为黑时或者为null时停止调整}else //u不存在或者为黑{if (cur == parent->_right)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可{RotateL(g);parent->_col = BLACK;g->_col = RED;}else{RotateR(parent);RotateL(g);cur->_col = BLACK;g->_col = RED;}}}}_root->_col = BLACK;return true;
}

4.3.判断红黑树的正确性

判断红黑树的正确性，主要还是在于其性质是否满足
主要判断下：

  1. 根节点是否为黑
  2. 是否出现连续的红色节点
  3. 最长路径有没有超过最短路径的两倍
  4. 每条路径的黑色节点是否一样

有了这些目标后设计代码（通过注释来解释！）：

bool IsValidRBTRee()
{if (_root == nullptr) return true;//此时无节点为真if (_root->_col == RED) return false;//根节点只能为黑，若为红返回假Node* cur = _root;int blackCount = 0;//记录一条路径的黑色节点个数！while (cur){if (cur->_col == BLACK){blackCount++;}cur = cur->_left;}return _IsValidRBTRee(_root,blackCount,0);
}bool _IsValidRBTRee(Node* root, size_t blackCount, size_t pathBlack)
{if (root == nullptr){if (blackCount != pathBlack)//当为null时表示该路径已经结束，那么判断改路径的黑色节点（pathblack） 和其他路径的黑色节点（blacCount）是否相同{return false;}return true;}if (root->_col == RED){if (root->_left && root->_right && (root->_left->_col == RED || root->_right->_col == RED)){cout << "有连续的红色节点" << endl;return false;}}if (root->_col == BLACK){pathBlack++;//某条路径的黑节点个数}//前序遍历return _IsValidRBTRee(root->_left, blackCount, pathBlack) &&_IsValidRBTRee(root->_right, blackCount, pathBlack);
}

4.4红黑树的源码

#pragma once
#include<iostream>
using namespace std;
// 请模拟实现红黑树的插入--注意：为了后序封装map和set，本文在实现时给红黑树多增加了一个头结点enum Color
{BLACK,RED
};template<class K , class V>
struct RBTreeNode {RBTreeNode<K,V>* _left = nullptr;RBTreeNode<K,V>* _right = nullptr;RBTreeNode<K,V>* _parent = nullptr;pair<K, V> _kv;Color _col = RED;//默认生成的节点颜色是红色RBTreeNode(const pair<K,V>& kv):_kv(kv){}
};template<class K,class V>
class RBTree
{typedef typename RBTreeNode<K,V> Node;
public:// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false// 注意：为了简单起见，本次实现红黑树不存储重复性元素bool Insert(const pair<K,V>& kv){//此处和AVL平衡二叉树的性质一样找到所要插入节点的位置 大的在右 、 小的在左Node* parent = nullptr;Node* cur = _root;if (cur == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//找到插入的位置！while (cur)//当为null时表示此处就是要插入的位置！{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);//建立新节点//建立链接if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//插入时要判断插入后是否会导致不平衡！对于红黑树来说主要问题有//1. 不能出现连续的红节点//2. 最长路径不超过最短路径的两倍//判断是否需要变色/旋转// //1.当父亲节点为黑色时，当新增了一个红色节点时就结束插入了// //2.当父为红时：//	情况一(仅变色即可)：当parent为红 grandfather为黑 uncle存在且为黑 插入一个新节点// //while (parent && parent->_col == RED){Node* g = parent->_parent;//grandfatherif (g->_left == parent){Node* u = g->_right;//uncleif (u && u->_col == RED)//u存在且为红{//变色即可u->_col = parent->_col = BLACK;g->_col = RED;//向上调整cur = g;parent = g->_parent;//当g 的 父亲为黑时或者为null时停止调整}else //u不存在或者为黑{if (cur == parent->_left)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可{//旋转加变色RotateR(g);parent->_col = BLACK;g->_col = RED;}else{//旋转加变色RotateL(parent);RotateR(g);cur->_col = BLACK;g->_col = RED;}}}else{Node* u = g->_left;//uncleif (u && u->_col == RED)//u存在且为红{//变色即可u->_col = parent->_col = BLACK;g->_col = RED;//向上调整cur = g;parent = g->_parent;//当g 的 父亲为黑时或者为null时停止调整}else //u不存在或者为黑{if (cur == parent->_right)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可{RotateL(g);parent->_col = BLACK;g->_col = RED;}else{RotateR(parent);RotateL(g);cur->_col = BLACK;g->_col = RED;}}}}_root->_col = BLACK;return true;}void Inorder(){_Inorder(_root);cout << endl;}//
//	// 获取红黑树最左侧节点Node* LeftMost(){Node* cur = _root;while (cur){if(cur->_left == nullptr){return cur;}cur = cur->_left;}return nullptr;}
//
//	// 获取红黑树最右侧节点Node* RightMost(){Node* cur = _root;while (cur){if (cur->_right == nullptr){return cur;}cur = cur->_right;}return nullptr;}
//
//	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测//	1.每条路径中的黑色节点个数是否一样//	2.最长路径不超过最短路径的两倍//	3.不能出现连续的红色节点//	4.根节点为黑色//bool IsValidRBTRee(){if (_root == nullptr) return true;//此时无节点为真if (_root->_col == RED) return false;//根节点只能为黑，若为红返回假Node* cur = _root;int blackCount = 0;//记录一条路径的黑色节点个数！while (cur){if (cur->_col == BLACK){blackCount++;}cur = cur->_left;}return _IsValidRBTRee(_root,blackCount,0);}int Height(){if (_root == nullptr) return 0;return _Height(_root);}int Size(){if (_root == nullptr) return 0;return _Size(_root);}//检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptrNode* Find(const K val){Node* cur = _root;while (cur){if (cur->_kv.first == val){return cur;}else if (cur->_kv.first > val){cur = cur->_left;}else {cur = cur->_right;}}return nullptr;}private:int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) +_Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int lefthight = _Height(root->_left);int righthight = _Height(root->_right);return lefthight > righthight ? lefthight + 1 : righthight + 1;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " " ;_Inorder(root->_right);}bool _IsValidRBTRee(Node* root, size_t blackCount, size_t pathBlack){if (root == nullptr){if (blackCount != pathBlack)//当为null时表示该路径已经结束，那么判断改路径的黑色节点（pathblack） 和其他路径的黑色节点（blacCount）是否相同{return false;}return true;}if (root->_col == RED){if (root->_left && root->_right && (root->_left->_col == RED || root->_right->_col == RED)){cout << "有连续的红色节点" << endl;return false;}}if (root->_col == BLACK){pathBlack++;//某条路径的黑节点个数}//前序遍历return _IsValidRBTRee(root->_left, blackCount, pathBlack) &&_IsValidRBTRee(root->_right, blackCount, pathBlack);}//	// 为了操作树简单起见：获取根节点//Node*& GetRoot();void RotateR(Node* parent){Node* SubL = parent->_left;//此处就为 curNode* SubLR = SubL->_right;//parent的左换成cur的右parent->_left = SubLR;//把cur的右孩子换成parentSubL->_right = parent;//注意还要修改其父指针Node* Ppnode = parent->_parent;parent->_parent = SubL;if (SubLR)//cur的右边可能为空SubLR->_parent = parent;if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr{_root = SubL;SubL->_parent = nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode->_left == parent){Ppnode->_left = SubL;}else{Ppnode->_right = SubL;}SubL->_parent = Ppnode;}}// 左单旋// 同理void RotateL(Node* parent){Node* SubR = parent->_right;//此处就为 curNode* SubRL = SubR->_left;//parent的右换成cur的左parent->_right = SubRL;//把cur的左孩子换成parentSubR->_left = parent;Node* Ppnode = parent->_parent;//注意 还要修改其父指针parent->_parent = SubR;if (SubRL)//右边可能为空SubRL->_parent = parent;if (_root == parent)//如果parent为根节点，则需要把subR改变成根节点并且其父亲为nullptr{_root = SubR;SubR->_parent = nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode->_left == parent){Ppnode->_left = SubR;}else{Ppnode->_right = SubR;}SubR->_parent = Ppnode;}}private:Node* _root = nullptr;
};

本章完。预知后事如何，暂听下回分解。

如果有任何问题欢迎讨论哈！

如果觉得这篇文章对你有所帮助的话点点赞吧！

持续更新大量C++细致内容，早关注不迷路。

​

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

linux 内核的 lru_list 的结构

linux 内核的 lru_list 的结构

在linux的slab分配的入口slab_alloc有一个传入参数lru&#xff0c;它的作用是使每个slab对象在unused&#xff0c;但可能后面继续使用的时候&#xff0c;不需要free&#xff0c;可以先放在lru_list上。lru_list的结构为&#xff1a; struct list_lru {struct list_lru_node *n…
阅读更多...
DiffUtil + RecyclerView 在 Kotlin中的使用

DiffUtil + RecyclerView 在 Kotlin中的使用

很惭愧, 做了多年的Android开发还没有使用过DiffUtil这样解放双手的工具。 文章目录 1 DiffUtil 用来解决什么问题?2 DiffUtil 是什么?3 DiffUtil的使用4 参考文章 1 DiffUtil 用来解决什么问题? List发生变化, 我们使用 RecyclerView.Adapter.notifyDataChanged很熟练了 …
阅读更多...
WiFi+蓝牙物联网定制方案——五大核心难点

WiFi+蓝牙物联网定制方案——五大核心难点

WiFi蓝牙物联网定制方案可以根据具体需求进行定制&#xff1a; 1、设备连接方案&#xff1a;采用WiFi和蓝牙技术&#xff0c;将物联网设备与智能手机、平板电脑等设备进行连接&#xff0c;实现数据传输和远程控制。 2、数据传输方案&#xff1a;通过WiFi和蓝牙技术&#xff0c;…
阅读更多...
Vue表格中鼠标移入移出input显示隐藏 ,有输入值不再隐藏

Vue表格中鼠标移入移出input显示隐藏 ,有输入值不再隐藏

Vue表格中鼠标移入移出input显示隐藏 , 不再隐藏的效果 <el-tableref"table":data"tableDatas"borderstyle"width: 100%":span-method"arraySpanMethod"id"table"row-key"id"cell-mouse-enter"editCell&q…
阅读更多...
Laravel框架使用phpstudy本地安装的composer用Laravel 安装器进行安装搭建

Laravel框架使用phpstudy本地安装的composer用Laravel 安装器进行安装搭建

一、首先需要安装Laravel 安装器 composer global require laravel/installer 二、安装器安装好后&#xff0c;可以使用如下命令创建项目 laravel new sys 三、本地运行 php artisan serve 四、 使用Composer快速安装Laravel5.8框架 安装指定版本的最新版本&#xff08;推荐&a…
阅读更多...
C#合并多个Word文档（微软官方免费openxml接口）

C#合并多个Word文档（微软官方免费openxml接口）

g /// <summary>/// 合并多个word文档&#xff08;合并到第一文件&#xff09;/// </summary>/// <param name"as_word_paths">word文档完整路径</param>/// <param name"breakNewPage">true(默认值)&#xff0c;合并下一个…
阅读更多...
Linux：ACL 权限控制

Linux：ACL 权限控制

ACL 概述 ACL&#xff08;Access Control List&#xff09;&#xff0c;主要作用可以提供除属主、属组、其他人的 rwx 权限之外的 细节权限设定。 ACL 的权限控制 &#xff08;1&#xff09;使用者&#xff08;user&#xff09; &#xff08;2&#xff09;群组&#xff08;grou…
阅读更多...
如何使用 Helm 在 K8s 上集成 Prometheus 和 Grafana｜Part 1

如何使用 Helm 在 K8s 上集成 Prometheus 和 Grafana｜Part 1

本系列将分成三个部分&#xff0c;您将学习如何使用 Helm 在 Kubernetes 上集成 Prometheus 和 Grafana&#xff0c;以及如何在 Grafana 上创建一个简单的控制面板。Prometheus 和 Grafana 是 Kubernetes 最受欢迎的两种开源监控工具。学习如何使用 Helm 集成这两个工具&#x…
阅读更多...
类和对象

类和对象

1 类定义&#xff1a; class ChecksumAccumulator {// class definition goes here } 你就能创建 ChecksumAccumulator 对象&#xff1a;new CheckSumAccumulator 注&#xff1a;1scala类中成员默认是public类型&#xff0c;若设为私有属性则必须加private关键字。在scala中是…
阅读更多...
NLP论文阅读记录 - | 使用 BRIO 训练范式进行抽象文本摘要

NLP论文阅读记录 - | 使用 BRIO 训练范式进行抽象文本摘要

文章目录 前言0、论文摘要一、Introduction二.相关工作三.本文方法四 实验效果4.1数据集4.2 对比模型4.3实施细节4.4评估指标4.5 实验结果标准抽象模型微调抽象模型微调抽象模型和 BRIO微调抽象模型和 BRIO-Loop 五 总结结论局限 前言 Abstractive Text Summarization Using th…
阅读更多...
OpenCV | 告别人工目检：深度学习技术引领工业品缺陷检测新时代

OpenCV | 告别人工目检：深度学习技术引领工业品缺陷检测新时代

文章目录 机器视觉缺陷检测工业上常见缺陷检测方法内容简介作者简介目录读者对象如何阅读本书获取方式 机器视觉 机器视觉是使用各种工业相机&#xff0c;结合传感器跟电气信号实现替代传统人工&#xff0c;完成对象识别、计数、测量、缺陷检测、引导定位与抓取等任务。其中工…
阅读更多...
【项目问题解决】% sql注入问题

【项目问题解决】% sql注入问题

目录 【项目问题解决】% sql注入问题 1.问题描述2.问题原因3.解决思路4.解决方案1.前端限制传入特殊字符2.后端拦截特殊字符-正则表达式3.后端拦截特殊字符-拦截器 5.总结6.参考 文章所属专区 项目问题解决 1.问题描述 在处理接口入参的一些sql注入问题&#xff0c;虽然通过M…
阅读更多...
flutter开发windows应用的库

flutter开发windows应用的库

一、window_manager 这个插件允许 Flutter 桌面应用调整窗口的大小和位置 地址&#xff1a;https://github.com/leanflutter/window_manager二、win32 一个包&#xff0c;它使用FFI包装了一些最常见的Win32 API调用&#xff0c;使Dart代码可以访问这些调用&#xff0c;而不需…
阅读更多...
node.js mongoose index（索引）

node.js mongoose index（索引）

目录 简介 索引类型 单索引 复合索引 文本索引 简介 在 Mongoose 中&#xff0c;索引&#xff08;Index&#xff09;是一种用于提高查询性能的数据结构&#xff0c;它可以加速对数据库中文档的检索操作 索引类型 单索引、复合索引、文本索引、多键索引、哈希索引、地理…
阅读更多...
useConsole的封装,vue,react，htmlscript标签，通用

useConsole的封装,vue,react，htmlscript标签，通用

之前用了接近hack的方式实现了console的封装&#xff0c;目标是获取console.log函数的执行&#xff08;调用栈所在位置&#xff09;所在的代码行数。 例如以下代码&#xff0c;执行window.mylog(1)时候&#xff0c;console.log实际是在匿名的箭头函数()>{//这里执行的} con…
阅读更多...
使用HTTP协议有哪些风险？HTTP与HTTPS的区别是什么

使用HTTP协议有哪些风险？HTTP与HTTPS的区别是什么

作为两种常见的网络协议&#xff0c;HTTP和HTTPS都是用于在浏览器和服务器之间传输数据的。然而在保障数据安全性方面&#xff0c;HTTPS远远优于HTTP。在网络安全愈发重要的当下&#xff0c;HTTP协议的不安全性使得其逐渐被淘汰弃用。那么使用HTTP协议有哪些风险呢&#xff1f;…
阅读更多...
Backend - Django 项目创建 运行

Backend - Django 项目创建 运行

目录 一、配置环境 二、创建 Django 项目 &#xff08;一&#xff09;新建文件夹 &#xff08;二&#xff09;打开文件夹 &#xff08;三&#xff09;打开运行终端 &#xff08;四&#xff09;创建基础项目 &#xff08;五&#xff09;创建app 1. 安装Django &#xf…
阅读更多...
ASP.NET Core MVC依赖注入理解（极简个人版）

ASP.NET Core MVC依赖注入理解（极简个人版）

依赖注入 文献来源&#xff1a;《Pro ASP.NET Core MVC》 Adam Freeman 第18章 依赖注入 1 依赖注入原理 所有可能变化的地方都用接口在使用接口的地方用什么实体类通过在ConfigureService中注册解决注册的实体类需要指定在何种生命周期中有效 TransientScopedSingleton 2…
阅读更多...
磁盘类型选择对阿里云RDS MySQL的性能影响

磁盘类型选择对阿里云RDS MySQL的性能影响

测试说明 这是一个云数据库性能测试系列&#xff0c;旨在通过简单标准的性能测试&#xff0c;帮助开发者、企业了解云数据库的性能&#xff0c;以选择适合的规格与类型。这个系列还包括&#xff1a; * 云数据库(RDS MySQL)性能深度测评与对比 * 阿里云RDS标准版(x86) vs 经济…
阅读更多...
远舢智能入选国家智慧能源产业联盟理事单位 远舢OS擘画绿色能源新蓝图

远舢智能入选国家智慧能源产业联盟理事单位 远舢OS擘画绿色能源新蓝图

近日&#xff0c;中关村智慧能源产业联盟2023年会员大会暨数字技术赋能能源转型论坛在京召开。大会审议通过了北京远舢智能科技有限公司&#xff08;以下简称“远舢智能”&#xff09;成为联盟新任理事单位&#xff0c;将与国务院发展研究中心、国家电投、清华大学等国家重点单…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023