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

2023-12-23 01:01
文章标签 二叉树 进阶 实现 数据结构 搜索 二叉 详细 过程 解析 红黑树 avl 附实 操图

本文主要是介绍数据结构之进阶二叉树（二叉搜索树和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++细致内容，早关注不迷路。

​

这篇关于数据结构之进阶二叉树（二叉搜索树和AVL树、红黑树的实现）超详细解析，附实操图和搜索二叉树的实现过程图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/526156。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
作业提交过程之HDFSMapReduce

作业提交过程之HDFSMapReduce

作业提交全过程详解 （1）作业提交 第1步：Client调用job.waitForCompletion方法，向整个集群提交MapReduce作业。 第2步：Client向RM申请一个作业id。 第3步：RM给Client返回该job资源的提交路径和作业id。 第4步：Client提交jar包、切片信息和配置文件到指定的资源提交路径。 第5步：Client提交完资源后，向RM申请运行MrAp
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2