AVL树，全称平衡搜索二叉树。
要认识AVL树，先认识二叉搜索树。
目录
二叉搜索树
先来介绍一下搜索二叉树。AVL树是在二叉搜索树的基础上建立的。
对于搜索二叉树而言，任意一个根节点的左子树上的Key值都比根节点的Key值小，右子树上的Key值都比根节点上的Key值大。
定义：二叉搜索树是一颗二叉树，可能为空。
但是对于一颗非空的二叉搜索树而言，其满足以下特征
- 每个元素都哦于一个关键字，并且任意两个元素的关键字都是不同的。也就是说二叉搜索树中，所有元素的关键字都是不同的，都是唯一的。
- 在根节点的左子树中，元素的关键字（如果存在的话）都小于根节点的关键字
- 在根节点的右子树中，元素的关键字（如果存在的话）都大于根节点的关键字
- 根节点的左右子树都是二叉树，也都满足这4个特征
会存在二叉搜索树中关键字存在一样的特殊的二叉搜索树，但是和不存在一样的关键字的二叉搜索树是大同小异的，这个后面再讨论。
对于一颗二叉树，除了对节点的值的分布有些要求，其他的和普通的二叉树没什么区别。
理解、认识二叉搜索树
根据描述的二叉搜索树的特征而言，也就是说，当我们去找一个节点时，拿目标值去与遍历到的节点的值去比较，
- 如果相等，那么找到了
- 如果目标值小于节点值，那么我们就可以去节点的左子树去查找
- 如果目标值大于节点值，那么我们就可以去节点的右子树去查找
对于二叉搜索树而言，其就是用来查找数据而设计的，用于快速查找数据。
对于一个数组而言，如果是一个有序数组，我们可以考虑使用二分法来快速查找数据，时间复杂度O(logN)。但是现实情况是，有序是数组并不是一个常见的情况，反而无序数组才是常见的情况。
而，二叉搜索树这个情况，并不是特意构建的结构，而是根据二叉搜索树的定义，去构建了这个结构，只不过顺便变成了这个类似有序的情况
对于一颗二叉搜索树进行查找某个元素，每完成一个节点的比较，就要排除掉一层节点。对于一颗N个节点的二叉树，其高度大概为 logN 。所以，对于一颗N个节点的二叉搜索树的查找，那么最多查找 logN 次。无论找到，还是没找到。
所以，二叉搜索树查找的时间复杂度就是O(logN)。
当然，也存在一些极端的情况，例如
这样的二叉树的结构，其查找的时间复杂度就会退化成O(N)。这个在AVL树中就不会出现这种极端情况，AVL树很好的解决了这个问题。
二叉搜索树的结构
这个二叉搜索树的结构和普通的二叉树并没有说明区别，
依旧是一个Key值，
一个指针指向左子树，
一个指针指向右子树。
维护二叉搜索树的节点的类
//维护节点的类
template <class T>
struct BinarySearchTreeNode
{
T _key;
BinarySearchTreeNode<T>* _left = nullptr;
BinarySearchTreeNode<T>* _right = nullptr;
BinarySearchTreeNode(T val = 0)
:_key(val)
,_left(nullptr)
,_right(nullptr)
{}
~BinarySearchTreeNode()
{
_left = _right = nullptr;
}
};
定义了一个struct类，这个类默认是public，可以被类外访问的。
维护二叉搜索树的类
需要一个类来维护二叉搜素树的节点之间的关系，也就是对二叉搜索树进行封装。我们之后使用就直接使用这个类来创建一可二叉搜索树，直接使用即可，不用使用者去维护节点之间的关系。
//维护二叉树结构的类
template <class T>
class BinarySearchTree
{
typedef BinarySearchTreeNode<T> Node;
public:
BinarySearchTree()
:_root(nullptr)
, _size(0)
{}
~BinarySearchTree()
{
_root = nullptr;
}
private:
Node* _root;
size_t _size = 0;
};
对于这个类的成员变量，一个指向二叉搜索树的指针即可，然后再来一个计算二叉搜索树的结点数。
其构造函数与析构函数都是对_root节点操作即可
二叉搜索树实现查找
根据我们上面描述的，与根节点去比较，比根节点的Key值大，就去右子树找，比Key小就去左子树找，如果遍历到空节点，那就说明根本就没有目标值，就找不到。
Node* Find(const T& key_val) const
{
Node* p = _root;
while (p)
{
if (p->_key < key_val)
p = p->_right;
else if (p->_key > key_val)
p = p->_left;
else
return p;
}
return nullptr;
}
如果找到了，就返回指向那个节点的指针，找不到就返回空指针。
二叉搜索树的结构优势
二叉搜索树为什么能查找的这么快？
这个完全取决于二叉搜索树的结构，也就是二叉搜索树的插入与删除。
我们通常所说的对于一个数据结构要完成的四个最基本的操作增、删、查、改。对于查和改，只要实现了查找，修改就也实现了。
二叉搜索树的插入
二叉树的操作基本都能靠递归和迭代来完成，但这里我们只实现迭代版本，递归大同小异。
二叉搜索树的插入也算要按照规矩来，满足二叉搜索树的特征。
对于一颗二叉搜索树去查找插入一个节点，其一就要与二叉树的节点进行比较，如果比节点的Key值大，那就往右边，如果小，就往左边。这个实际上就是一个查找到过程，当查找不到的时候，也就是移动到空指针处，就是可以插入了。但是还有一个问题，如果仅仅考查找来完成，那么只是知道有个nullptr，那么是没有用的，还需要知道其待插入到节点的根节点的位置，才能实现节点插入。
bool Insert(const T& val_key)
{
if (_root == nullptr)//空树
{
_root = new Node(val_key);
_size++;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_key < val_key)
cur = cur->_right;
else if (cur->_key > val_key)
cur = cur->_left;
else//有一样的，不用插入，插入失败
return false;
}
cur = new Node(val_key);
_size++;
if (parent->_key > val_key)
parent->_left = cur;
else
parent->_right = cur;
return true;
}
准备一个父指针来保存cur节点的父节点。同时还要防备如果这是一颗空树的情况。
还有最关键的就是对于节点是根节点的左子树还是右子树的判断，这需要一个操作来判断，最简单就是看Key值。
二叉搜索树的删除
对于删除节点操作，即插入要复杂一些，因为对于一个要删除的节点，我们存在多种情况，不处理会破坏二叉搜索树的结构，我们要保证无论怎样操作，搜索树的结构是正常的。
要删除的节点，简称目标节点
- 目标节点没有左右子树
- 目标节点只有一颗子树
- 目标节点有左右子树
如果，要删除的目标节点没有左右子树，那么通过Key值直接找那个节点，然后直释放空间，然后把其根节点的指针置空即可。
如果目标节点有一棵子树的话，那么只需将其根节点指向目标节点的指针指向其子树的根节点即可，然后delete掉目标节点
对于目标节点有左右两颗子树时，就要找一个新的符合条件的节点来代替这个位置。综合考虑搜索树节点之间的关系，有两个方案，实际上差不多。目标节点的
左子树的最右节点（最大的Key值节点）或者
右子树的最左节点（最小的Key值节点）
把某个节点移动到目标节点的位置，然后删除目标节点，同时把目标节点与其他节点之间的关系给新移上来的节点。然后把移动节点的某个子树处理一下，即可。
这里选用了右子树的最左节点
但是我们并不用想理论上描述的如此复炸，可以找到右子树的最小节点，然后和目标节点做一个Key值的交换，这样就不用去处理节点之间的关系，然后下一步，就是删除交换后的右子树的最小值节点，这个删除就是删除只有一颗子树的根节点的模式。
bool Erase(const T& val_key)
{
//先要找到删除节点的位置
if (_root == nullptr)
return false;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > val_key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < val_key)
{
parent = cur;
cur = cur->_right;
}
else//找到了
break;
}
Node* root = cur;
if (cur == nullptr)//没找到
return false;
if (cur->_left != nullptr && cur->_right != nullptr)//情况3
{
//方案一：右子树的最小值,右子树的最左边
Node* p = cur->_right;
Node* pt = cur;
while (p->_left)
{
pt = p;
p = p->_left;
}
//p就是右子树的最小值,pt是其父节点
cur->_key = p->_key;//替换
//删掉右子树的最小节点
Node* tmp;
if (p->_left)
tmp = p->_left;
else
tmp = p->_right;
if (pt->_left == p)
pt->_left = tmp;
else
pt->_right = tmp;
//
delete p;
p = nullptr;
_size--;
return true;
}
Node* tmp;
if (cur->_left)
tmp = cur->_left;
else
tmp = cur->_right;
if (cur == _root)//防止删除根节点，且情况一二的样子
_root = tmp;
else
{
if (parent->_left == cur)
parent->_left = tmp;
else
parent->_right = tmp;
}
_size--;
delete cur;
cur = nullptr;
return true;
}
虽然情况一与情况二是两种情况，但是实际上都是可以通过代码一起操作的。
对于要删除的节点，可以加一个判断，如果目标节点cur->left==nullptr，那么parent可以指向cur->right，反之，依然。如果是情况一，这样会直接指向空，符合要求，二情况而，这样是为了找出子树，然后接入根节点。
而对于情况三，先找到目标节点的右子树的最左节点，然后将其与其根节点保存记录下来。将在这个节点的Key赋值给目标节点。剩下的操作就是执行情况一与情况二的操作，将保留下来的节点删除。
但是如果删除的是整个搜索树的根节点的话，那么还要将_root指针指向更新后的节点。
这样就介绍完了关于二叉搜索树的全部操作了。同时还可以介绍一点，如果对二叉搜索树进行中序遍历，那么得到的是一个有序的数组，所以可以通过中序遍历去验证是否是一颗二叉搜索树。
对于有相同关键字节点的二叉搜索树
如果想要达到这个条件，只需要对插入进行一点修改即可，把判断存在的条件删除，让等于关键字的条件并入大于等于的判断条件中。
注意点
对于一颗二叉搜索树而言，如果插入Key的顺序不一样的话，这个树的结构也可能不一样，不然为什么会出现上面极端的情况。可以自己举例试试。
K模型与KV模型
这个也不是什么复杂的知识。
这个主要是针对二叉树的节点的值的。
Key - 关键字
Value - 值
就是加一个成员变量的是，不过也可以考虑使用**pair<K,V>**连表示这个KV成员变量。
不过对于搜索树的操作，都是使用Key进行比较，对于Value都是不使用的。
二叉搜索树的封装BinarySearchTree.h
#pragma once
/*
* 需要维护一个节点的类
* 还有一个维护节点之间关系的类
*/
//维护节点的类
template <class T>
struct BinarySearchTreeNode
{
T _key;
BinarySearchTreeNode<T>* _left = nullptr;
BinarySearchTreeNode<T>* _right = nullptr;
BinarySearchTreeNode(T val = 0)
:_key(val)
,_left(nullptr)
,_right(nullptr)
{}
~BinarySearchTreeNode()
{
_left = _right = nullptr;
}
};
//维护二叉树结构的类
template <class T>
class BinarySearchTree
{
typedef BinarySearchTreeNode<T> Node;
public:
BinarySearchTree()
:_root(nullptr)
, _size(0)
{}
~BinarySearchTree()
{
_root = nullptr;
}
//二叉搜索数的查找-非递归版本
//遵循左子树小于根，右子树大于根
Node* Find(const T& key_val) const
{
Node* p = _root;
while (p)
{
if (p->_key < key_val)
p = p->_right;
else if (p->_key > key_val)
p = p->_left;
else
return p;
}
return nullptr;
}
//插入节点-非递归版本
bool Insert(const T& val_key)
{
if (_root == nullptr)//空树
{
_root = new Node(val_key);
_size++;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_key < val_key)
cur = cur->_right;
else //if (cur->_key > val_key)
cur = cur->_left;
//else//有一样的，不用插入，插入失败
//return false;
}
cur = new Node(val_key);
_size++;
if (parent->_key > val_key)
parent->_left = cur;
else
parent->_right = cur;
return true;
}
//删除节点-非递归版本
/*节点有三种情况
* 1，叶子节点：左右都是空
* 2，左右只有一边有一个子树
* 3，左右子树都有
*
* 实际上删除时，
* 1和2都是一样的操作，将其原本指向其的指针指向本节点的下一个（左或者右）
*
* 3需要找到其左子树的最大节点（左子树的最右节点）或 右子树的最小节点（右子树的最左边节点）
*/
/*
* 对于情况3，最重要的是删除替换节点，处理好替换节点的父节点与替换节点的关系
*/
bool Erase(const T& val_key)
{
//先要找到删除节点的位置
if (_root == nullptr)
return false;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > val_key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < val_key)
{
parent = cur;
cur = cur->_right;
}
else//找到了
break;
}
Node* root = cur;
if (cur == nullptr)//没找到
return false;
if (cur->_left != nullptr && cur->_right != nullptr)//情况3
{
//方案一：右子树的最小值,右子树的最左边
Node* p = cur->_right;
Node* pt = cur;
while (p->_left)
{
pt = p;
p = p->_left;
}
//p就是右子树的最小值,pt是其父节点
cur->_key = p->_key;//替换
//删掉右子树的最小节点
Node* tmp;
if (p->_left)
tmp = p->_left;
else
tmp = p->_right;
if (pt->_left == p)
pt->_left = tmp;
else
pt->_right = tmp;
//
delete p;
p = nullptr;
_size--;
return true;
}
Node* tmp;
if (cur->_left)
tmp = cur->_left;
else
tmp = cur->_right;
if (cur == _root)//防止删除根节点，且情况一二的样子
_root = tmp;
else
{
if (parent->_left == cur)
parent->_left = tmp;
else
parent->_right = tmp;
}
_size--;
delete cur;
cur = nullptr;
return true;
}
size_t size(void)
{
return _size;
}
void _InOderR(Node* root)
{
if (root == nullptr)
return;
_InOderR(root->_left);
cout << root->_key << " ";
_InOderR(root->_right);
}
void InOderR()
{
_InOderR(_root);
}
private:
Node* _root;
size_t _size = 0;
};
AVL树
前面已经介绍了，AVL树是建立在二叉搜索树的基础上，全称叫平衡搜索二叉树。
二叉搜索树的结构思想是一个非常优秀的结构。可以用于快速查找。但是对于某些情况，光靠一个二叉搜索树是完全不够用的，就比如上面举的一个极端的情况。
这两种虽然也是搜索二叉树，但这种结构并不适合快速搜索。
所以，平衡搜索二叉树提供了一个解决方案来处理这个不能支持快速搜索的问题。也就是说AVL树提供了解决这种极端结构的方法。
AVL树建立的逻辑
如果搜索树的高度总时满足O(logN)，我们就能保证查找、插入和删除的时间为O(logN)。则最坏的情况下高度依旧是O(logN)的树称为平衡树。
定义：一颗空的二叉树是AVL树
如果有一颗非空的二叉树，那么L与R分别是其左子树与右子树，当改非空二叉树满足以下条件时，是一颗AVL树
- L与R都是AVL树
- | HR-HL |小于等于1，左右子树的高度差的绝对值小于等于1
AVL树具有以下特征
- 一颗n元AVL树，其高度是O(logN)
- 对于AVL树而言，任意结点数都满足AVL树的条件
- 对于一颗n元的AVL树，其增删查改的时间复杂度都是O(高度)=O(logN)
AVL树增加了一个平衡因子的概念.
平衡因子用于计算右子树高度与左子树的高度差，保存在根节点。
对于一个正常的AVL树而言，其平衡因子的取值为-1、0、1。
如果平衡因子不满足这些取值，那么就意味着，二叉树已经不是AVL树了，则就需要对其进行修正。而AVL树的修正被称为 “旋转”。
AVL树的查找就很搜索二叉树的查找是一样的，我们只需要研究AVL树的插入和删除即可。
AVL树有一个指向根节点的指针
虽然这个指向根节点的指针可以用其他方法来替代，这个是为了更方便的寻找路径，从当前节点到根节点的路径，也可以考虑使用栈来代替，不过我觉得不好用。这个后面会介绍作用。
维护AVL节点的类
template <class K,class V>
struct AVLTreeNode
{
typedef AVLTreeNode<K, V> Node;
AVLTreeNode<K, V>* _left;//指向左子树
AVLTreeNode<K, V>* _right;//指向右子树
AVLTreeNode<K, V>* _parent;//指向父节点
pair<K, V> _val;//节点终端索引值K以及value值V
int _bf;//平衡因子
AVLTreeNode(pair<K,V>& val)//构造
:_val(val)
,_bf(0)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{}
AVLTreeNode(const AVLTreeNode& node)//拷贝构造
{
_val = node._val;
_bf = node._bf;
_left = node._left;
_right = node._right;
_parent = node._parent;
}
~AVLTreeNode()
{
_left = _parent = _right = nullptr;
}
};
AVL树的插入
右单旋
沿着节点去修改节点平衡因子的值，如果某个节点的平衡因子>=|2|,那么就说明，以此节点作为根节点的搜索树不符合AVL树的结构了，就需要以此为节点进行旋转，我们称为右单旋。
讲解一下实现原理。
我们通过搜索树的结构完成对AVL树的插入，然后由于新的节点的插入，所以这个AVL树的高度结构可能会被破坏，所以我们要去检查。
从插入到节点处开始，这个节点的平衡因子是0，因为是新插入的节点，左右子树为空。然后利用指向父节点的指针，去遍历父节点，如果新插入的节点是根节点的左子树，那么就说明根节点的左子树高度要加1，然后其平衡因子_bf=H_ r-H_ l-1，则平衡因子的值减1，
- 如果现在的平衡因子的数是0，说明其左右子树高度差为0，也就没必要继续向上遍历了，因为从其根节点看这棵子树的高度没有变换。
- 如果现在的平衡因子是-1/1的话，那说明这棵子树的高度发生了变化，则从当前节点的根节点来看这个子树的高度发生了变化，则要继续向上遍历。
- 如果现在的平衡因子是-2/2的话，则说明以当前节点作为根节点的搜索树不在符合AVL树的结构了，则此说明需要对此树的结构进行修正。
则修正就有“旋转”：分为左单旋、右单旋、左右双旋以及右左双旋
实际上双选是由两个单旋组合而成的。
右单旋，当出现某个节点的平衡因子是-2(命名为：parent)，且parent->left->_bf==-1，则说明这棵搜索树旋进行右单旋进行修正AVL树结构。
如上图，让leftSon的右子树作为parent的左子树，
然后让parent作为leftSon的右子树，因为parent以及其右子树都是比leftSon要大的，这也是满足要求的。
然后让leftSon作为这颗二叉树的新的根节点。别忘了，更改每个节点的_parent指针，然后修改平衡因子，都是0。
这样就修正回了一颗AVL树。
同时，还要注意某些指针可能是空指针的问题，比如leftSon->_left就有可能是空指针。
void Rotate_Right(Node* parent)
{
Node* Sub = parent->_left;//leftSon
Node* SubR = Sub->_right;
Node* grand = parent->_parent;
parent->_left = SubR;
//要注意一个问题，对于被旋转的节点与子树，更改了树的指针式，都需要考虑其parent指针的改变
if (SubR)
{
SubR->_parent = parent;
}
Sub->_right = parent;
parent->_parent = Sub;
Sub->_parent = grand;
if (grand)//是某棵树的子树
{
if (grand->_left == parent)
grand->_left = Sub;
else
grand->_right = Sub;
}
else//root为根节点
{
_root = Sub;
}
//要考虑这个问题树是某个树的一个子树，还是，这就是整颗树的情况
Sub->_bf = 0;
parent->_bf = 0;
}
左单旋
与右单旋类似的步骤
左单旋，当出现某个节点的平衡因子是-2(命名为：parent)，且 parent->right->_bf==1，则说明这棵搜索树旋进行左单旋进行修正AVL树结构。
如上图，让rightSon的左子树作为parent的右子树，
然后让parent作为rightSon的左子树，因为parent以及其左子树都是比rightSon要小的，这也是满足要求的。
然后让rightSon作为这颗二叉树的新的根节点。别忘了，更改每个节点的_parent指针，然后修改平衡因子，都是0。
几乎与右单旋是相反的操作与思路
void Rotate_Left(Node* parent)
{
Node* Sub = parent->_right;//rightSon
Node* SubL = Sub->_left;
Node* grand = parent->_parent;
//处理SubL
parent->_right = SubL;
if (SubL)
{
SubL->_parent = parent;
}
//处理parent节点
Sub->_left = parent;
parent->_parent = Sub;
//处理Sub节点
Sub->_parent = grand;
if (grand)//子树
{
if (grand->_left == parent)
grand->_left = Sub;
else
grand->_right = Sub;
}
else
{
_root = Sub;
}
Sub->_bf = 0;
parent->_bf = 0;
}
左右双旋
对于双旋而言，需要注意这三种情况，都是可能存在的值。
实际就是两个单旋的结合
void Rotate_LR(Node* parent)
{
Node* Sub = parent->_left;
Node* SubR = Sub->_right;
Rotate_Left(Sub);
Rotate_Right(parent);
if (SubR->_bf == -1)
{
parent->_bf = 1;
Sub->_bf = 0;
SubR->_bf = 0;
}
else if (SubR->_bf == 1)
{
parent->_bf = 0;
Sub->_bf = -1;
SubR->_bf = 0;
}
else if (SubR->_bf == 0)
{
parent->_bf = 0;
Sub->_bf = 0;
SubR->_bf = 0;
}
}
这个关键的就是grandpa、parent、Son节点的平衡因子的赋值问题，三种情况就是三种不同的赋值。
右左双旋
void Rotate_RL(Node* parent)
{
Node* Sub = parent->_right;
Node* SubR = Sub->_left;
Rotate_Right(Sub);
Rotate_Left(parent);
if (SubR->_bf == -1)
{
parent->_bf = 0;
Sub->_bf = 1;
SubR->_bf = 0;
}
else if (SubR->_bf == 1)
{
parent->_bf = -1;
Sub->_bf = 0;
SubR->_bf = 0;
}
else if (SubR->_bf == 0)
{
parent->_bf = 0;
Sub->_bf = 0;
SubR->_bf = 0;
}
}
插入的成员函数
pair<Node*, bool> Insert(pair<K,V> val)
{
Node* node = new Node(val);
if (_root == nullptr)
{
_root = node;
return make_pair(_root, true);
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_val.first > val.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val.first < val.first)
{
parent = cur;
cur = cur->_right;
}
else//找到了一摸一样的
{
return make_pair(cur, false);
}
}
if (parent->_val.first > node->_val.first)
parent->_left = node;
else
parent->_right = node;
node->_parent = parent;//节点进入二叉树后，还要把其指向父的指向也要修改
cur = node;
Node* ret = cur;
//沿着路径对节点的bf因子进行修正
while (parent)
{
if (parent->_left == cur)//平衡因子更新
{
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)//进行旋转修正AVL树的结构
{
if (parent->_bf == -2)
{
if (parent->_left->_bf == -1)//左边高，需要右旋
{
Rotate_Right(parent);//传递出问题的子树的根节点
}
else if (parent->_left->_bf == 1)//先左旋，在右旋
{
Rotate_LR(parent);
}
}
else if (parent->_bf == 2)
{
if (parent->_right->_bf == 1)//右边子树高，需要左旋
{
Rotate_Left(parent);
}
else if (parent->_right->_bf == -1)//先右旋，再左旋
{
Rotate_RL(parent);
}
}
break;
}
else
{
assert(false);
}
}
return make_pair(ret, true);
}
AVL树的删除
AVL树毕竟是一颗二叉搜索树，所以，其删除元素与二叉搜索树大同小异，都有三种节点的情况要考虑。
- 删除节点是一个叶子节点
- 删除节点有且只有一颗子树
- 删除节点有左右子树
先找到目标节点。
然后对目标节点分情况进行删除处理。然后是关键的，要保证删除后的二叉树依旧是是AVL树的结构。
所以，就需要再删除玩节点后，沿着根节点的路径一路遍历上去，这就是为了检查树的结构。
如果需要修改数对结构就是利用4个旋转去完成AVL树结构的修正。
对于叶子节点的删除操作
Node* parent = cur->_parent;
Node* del = cur;
if (cur->_left == nullptr && cur->_right == nullptr)//情况一
{
if (_root == del)
{
delete del;
_root = nullptr;
return true;
}
if (parent->_left == del)
{
parent->_bf++;
parent->_left = nullptr;
}
else
{
parent->_bf--;
parent->_right = nullptr;
}
delete del;
}
删除节点的时候，要防备删除的节点是根节点的情况，也就是_root要进行指向更改。
当如果是情况一，是删除的根节点，且正好是要修改_root的指向，直接赋值空指针即可。
想想实际会出现这种情况的，就是这个AVL树只剩下一个根节点。
对于删除普通的叶子节点，找到叶子节点的父节点，然后确定左右指针，然后直接置空。同时对于父节点，
如果叶子节点是其左子树，那么删除左子树的节点，会导致（H右-H左+1），所以父节点的平衡因子加一。
如果叶子节点是其右子树，那么删除右子树的节点，会导致（H右-H左-1），所以父节点的平衡因子减一。
对于单子树根节点的删除
else if (cur->_left == nullptr || cur->_right == nullptr)//情况二
{
Node* pnext;//指向删除节点的子树
if (cur->_left == nullptr)//有右子树
{
pnext = cur->_right;
}
else//有左子树
{
pnext = cur->_left;
}
if (_root == cur)
{
_root = pnext;
return true;//也可以避免parent为空的情况
}
if (parent->_left == cur)//左子树
{
parent->_left = pnext;
pnext->_parent = parent;
parent->_bf++;
}
else
{
parent->_right = pnext;
pnext->_parent = parent;
parent->_bf--;
}
delete del;
cur = pnext;
}
首先，我们知道，右一个子树的节点的删除，只需要找到那个子树，然后把父节点指向子树，然后删除节点即可
所以，要先找出子树。
然后加一个判断，用来判断删除的节点是AVL树的根节点，如果是，那么_root直接指向子树即可。
如果不是，那么找出父节点指向删除节点的指针，然后指向删除节点，同时，还要把子树的父指针指向父节点。（这个很关键，我就出了这样的bug）
然后，修改父节点的平衡因子，删左边，平衡因子+1.删右边，平衡因子-1。
对左右子树的根节点的删除
else//情况三
{
//找右子树最左边的节点
Node* snode = cur->_right;
Node* pare = cur;
while (snode)
{
pare = snode;
snode = snode->_left;
}
//找到了交换点
cur->_val = pare->_val;
//然后删除交换点
Node* ppare = pare->_parent;
if (pare->_right)
{
if (ppare->_left == pare)
{
ppare->_left = pare->_right;
pare->_right->_parent = ppare;
ppare->_bf++;
}
else
{
ppare->_right = pare->_right;
pare->_right->_parent = ppare;
ppare->_bf--;
}
}
else
{
if (ppare->_left == pare)
{
ppare->_left = nullptr;
ppare->_bf++;
}
else
{
ppare->_right = nullptr;
ppare->_bf--;
}
}
delete pare;
parent = ppare;
}
情况三，就直接经典操作，找删除节点的右子树的最左节点。这个好一些，直接赋值即可，对于删除节点就处理完毕了。平衡因子都不用修改，因为结构没变。
然后，将交换节点进行删除操作。对于这个节点，记为ppare。只有两种情况，有右子树的（情况二），没有右子树的（情况一）。
还是这种操作。对于情况二的处理，别忘记将子树的父指针修正。
沿着路径去修改平衡因子以及修正树的结构
由于，这个修正和插入里的修正方法不太一样，因为我们要再遍历节点前就已经修改过parent节点的平衡因子了，所以要先判断算法要继续向上遍历。而且这个判断条件也存在不同。
插入里，是|_bf |==1就继续向上遍历，_bf= =0就可以退出，不用遍历了。
不过对于删除，
if (parent->_bf == 0)//反而要向上更新,其子树的高度出现了降低
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -1 || parent->_bf == 1)//不用向上更新，对于根节点而言，其高度没有变化
{
break;
}
因为是删除操作，_bf的值变成0，就只有从-1或者1变成的0。那么，在原先是-1/1的高度差的情况下，变成了0，就是说，这个子树的高度发生了改变，可能会对根节点造成影响，所以需要继续向上修正。
反而-1/1就可以直接退出来，因为，变成-1/1也就是只有原先是0的情况下，虽然存在高度差了，但是这颗子树的高度并没有改变。所以不会影响AVL树的结构。
而-2/2的情况，就跟插入一样，就可以直接旋转。
在更新完parent后，对平衡因子进行修改，最好加一个if (parent == nullptr)break;。修改原则依旧是左边加一，右边减一的情况。
while (parent)
{
if (parent->_bf == 0)//反而要向上更新,其子树的高度出现了降低
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -1 || parent->_bf == 1)//不用向上更新，对于根节点而言，其高度没有变化
{
break;
}
else if (parent->_bf == -2 || parent->_bf == 2)//进行旋转修正AVL树的结构
{
if (parent->_bf == -2)
{
if (parent->_left->_bf == -1)//左边高，需要右旋
{
Rotate_Right(parent);//传递出问题的子树的根节点
}
else if (parent->_left->_bf == 1)//先左旋，在右旋
{
Rotate_LR(parent);
}
}
else if (parent->_bf == 2)
{
if (parent->_right->_bf == 1)//右边子树高，需要左旋
{
Rotate_Left(parent);
}
else if (parent->_right->_bf == -1)//先右旋，再左旋
{
Rotate_RL(parent);
}
}
break;
}
else
{
assert(false);
}
if (parent == nullptr)
break;
if (cur->_bf == 0)//才需要更新节点的平衡因子
{
if (parent->_left == cur)//平衡因子更新
{
parent->_bf++;
}
else
{
parent->_bf--;
}
}
}
erase成员函数
/*
* 与搜索二叉树类似，要考虑
* 情况一：叶子节点
* 情况二：有一个子树的节点
* 情况三：左右子树都存在的节点
* 然后，还要根据删除的位置i宠幸沿着路经去检查平衡因子
*
*/
bool erase(const K& key)
{
//先找到
Node* cur = _root;
while (cur)
{
if (cur->_val.first < key)
cur = cur->_right;
else if (cur->_val.first > key)
cur = cur->_left;
else//找到了
break;
}
if (cur == nullptr)//没有这个节点，直接退出
return false;
//找到key节点了
Node* parent = cur->_parent;
Node* del = cur;
if (cur->_left == nullptr && cur->_right == nullptr)//情况一
{
if (_root == del)
{
delete del;
_root = nullptr;
return true;
}
if (parent->_left == del)
{
parent->_bf++;
parent->_left = nullptr;
}
else
{
parent->_bf--;
parent->_right = nullptr;
}
delete del;
}
else if (cur->_left == nullptr || cur->_right == nullptr)//情况二
{
Node* pnext;
if (cur->_left == nullptr)//有右子树
{
pnext = cur->_right;
}
else//有左子树
{
pnext = cur->_left;
}
if (_root == cur)
{
_root = pnext;
return true;//也可以避免parent为空的情况
}
if (parent->_left == cur)//左子树
{
parent->_left = pnext;
pnext->_parent = parent;
parent->_bf++;
}
else
{
parent->_right = pnext;
pnext->_parent = parent;
parent->_bf--;
}
delete del;
cur = pnext;
}
else//情况三
{
//找右子树最左边的节点
Node* snode = cur->_right;
Node* pare = cur;
while (snode)
{
pare = snode;
snode = snode->_left;
}
//找到了交换点
cur->_val = pare->_val;
//然后删除交换点
Node* ppare = pare->_parent;
if (pare->_right)
{
if (ppare->_left == pare)
{
ppare->_left = pare->_right;
pare->_right->_parent = ppare;
ppare->_bf++;
}
else
{
ppare->_right = pare->_right;
pare->_right->_parent = ppare;
ppare->_bf--;
}
}
else
{
if (ppare->_left == pare)
{
ppare->_left = nullptr;
ppare->_bf++;
}
else
{
ppare->_right = nullptr;
ppare->_bf--;
}
}
delete pare;
parent = ppare;
}
while (parent)
{
if (parent->_bf == 0)//反而要向上更新,其子树的高度出现了降低
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -1 || parent->_bf == 1)//不用向上更新，对于根节点而言，其高度没有变化
{
break;
}
else if (parent->_bf == -2 || parent->_bf == 2)//进行旋转修正AVL树的结构
{
if (parent->_bf == -2)
{
if (parent->_left->_bf == -1)//左边高，需要右旋
{
Rotate_Right(parent);//传递出问题的子树的根节点
}
else if (parent->_left->_bf == 1)//先左旋，在右旋
{
Rotate_LR(parent);
}
}
else if (parent->_bf == 2)
{
if (parent->_right->_bf == 1)//右边子树高，需要左旋
{
Rotate_Left(parent);
}
else if (parent->_right->_bf == -1)//先右旋，再左旋
{
Rotate_RL(parent);
}
}
break;
}
else
{
assert(false);
}
if (parent == nullptr)
break;
if (cur->_bf == 0)//才需要更新节点的平衡因子
{
if (parent->_left == cur)//平衡因子更新
{
parent->_bf++;
}
else
{
parent->_bf--;
}
}
}
return true;
}
AVLTree.h（封装AVL树）
#pragma once
template <class K,class V>
struct AVLTreeNode
{
typedef AVLTreeNode<K, V> Node;
AVLTreeNode<K, V>* _left;//指向左子树
AVLTreeNode<K, V>* _right;//指向右子树
AVLTreeNode<K, V>* _parent;//指向父节点
pair<K, V> _val;//节点终端索引值K以及value值V
int _bf;//平衡因子
AVLTreeNode(pair<K,V>& val)//构造
:_val(val)
,_bf(0)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{}
AVLTreeNode(const AVLTreeNode& node)//拷贝构造
{
_val = node._val;
_bf = node._bf;
_left = node._left;
_right = node._right;
_parent = node._parent;
}
~AVLTreeNode()
{
_left = _parent = _right = nullptr;
}
};
template <class K,class V>
class AVLTree
{
public:
typedef AVLTreeNode<K, V> Node;
AVLTree()
:_root(nullptr)
{}
void _Onder(Node* root)
{
if (root == nullptr)
return;
_Onder(root->_left);
cout << root->_val.first << ":" << root->_val.second << endl;
_Onder(root->_right);
}
void Onder()
{
_Onder(_root);
}
pair<Node*, bool> Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_val.first)
cur = cur->_left;
else if (key > cur->_val.first)
cur = cur->_right;
else//找到了
{
return make_pair(cur, true);
}
}
return make_pair(nullptr, false);
}
pair<Node*, bool> Insert(pair<K,V> val)
{
Node* node = new Node(val);
if (_root == nullptr)
{
_root = node;
return make_pair(_root, true);
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_val.first > val.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val.first < val.first)
{
parent = cur;
cur = cur->_right;
}
else//找到了一摸一样的
{
return make_pair(cur, false);
}
}
if (parent->_val.first > node->_val.first)
parent->_left = node;
else
parent->_right = node;
node->_parent = parent;//节点进入二叉树后，还要把其指向父的指向也要修改
cur = node;
Node* ret = cur;
//沿着路径对节点的bf因子进行修正
while (parent)
{
if (parent->_left == cur)//平衡因子更新
{
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)//进行旋转修正AVL树的结构
{
if (parent->_bf == -2)
{
if (parent->_left->_bf == -1)//左边高，需要右旋
{
Rotate_Right(parent);//传递出问题的子树的根节点
}
else if (parent->_left->_bf == 1)//先左旋，在右旋
{
Rotate_LR(parent);
}
}
else if (parent->_bf == 2)
{
if (parent->_right->_bf == 1)//右边子树高，需要左旋
{
Rotate_Left(parent);
}
else if (parent->_right->_bf == -1)//先右旋，再左旋
{
Rotate_RL(parent);
}
}
break;
}
else
{
assert(false);
}
}
return make_pair(ret, true);
}
void Rotate_LR(Node* parent)
{
Node* Sub = parent->_left;
Node* SubR = Sub->_right;
Rotate_Left(Sub);
Rotate_Right(parent);
if (SubR->_bf == -1)
{
parent->_bf = 1;
Sub->_bf = 0;
SubR->_bf = 0;
}
else if (SubR->_bf == 1)
{
parent->_bf = 0;
Sub->_bf = -1;
SubR->_bf = 0;
}
else if (SubR->_bf == 0)
{
parent->_bf = 0;
Sub->_bf = 0;
SubR->_bf = 0;
}
}
void Rotate_RL(Node* parent)
{
Node* Sub = parent->_right;
Node* SubR = Sub->_left;
Rotate_Right(Sub);
Rotate_Left(parent);
if (SubR->_bf == -1)
{
parent->_bf = 0;
Sub->_bf = 1;
SubR->_bf = 0;
}
else if (SubR->_bf == 1)
{
parent->_bf = -1;
Sub->_bf = 0;
SubR->_bf = 0;
}
else if (SubR->_bf == 0)
{
parent->_bf = 0;
Sub->_bf = 0;
SubR->_bf = 0;
}
}
void Rotate_Right(Node* parent)
{
Node* Sub = parent->_left;
Node* SubR = Sub->_right;
Node* grand = parent->_parent;
parent->_left = SubR;
//要注意一个问题，对于被旋转的节点与子树，更改了树的指针式，都需要考虑其parent指针的改变
if (SubR)
{
SubR->_parent = parent;
}
Sub->_right = parent;
parent->_parent = Sub;
Sub->_parent = grand;
if (grand)//是某棵树的子树
{
if (grand->_left == parent)
grand->_left = Sub;
else
grand->_right = Sub;
}
else//root为根节点
{
_root = Sub;
}
//要考虑这个问题树是某个树的一个子树，还是，这就是整颗树的情况
Sub->_bf = 0;
parent->_bf = 0;
}
void Rotate_Left(Node* parent)
{
Node* Sub = parent->_right;
Node* SubL = Sub->_left;
Node* grand = parent->_parent;
//处理SubL
parent->_right = SubL;
if (SubL)
{
SubL->_parent = parent;
}
//处理parent节点
Sub->_left = parent;
parent->_parent = Sub;
//处理Sub节点
Sub->_parent = grand;
if (grand)//子树
{
if (grand->_left == parent)
grand->_left = Sub;
else
grand->_right = Sub;
}
else
{
_root = Sub;
}
Sub->_bf = 0;
parent->_bf = 0;
}
V& operator[](const K& key)
{
pair<Node*, bool> ret = Insert(make_pair(key, V()));
return ret.first->_val.second;
}
void Level_Traversal(void)
{
queue<Node*> st;
int len;
st.push(_root);
while (!st.empty())
{
len = st.size();
for (int i = 0; i < len; i++)
{
Node* cur = st.front();
st.pop();
if (cur)
{
st.push(cur->_left);
st.push(cur->_right);
cout << cur->_val.first << " ";
}
else
cout << "NULL ";
}
cout << endl;
}
cout << endl;
}
/*
* 与搜索二叉树类似，要考虑
* 情况一：叶子节点
* 情况二：有一个子树的节点
* 情况三：左右子树都存在的节点
* 然后，还要根据删除的位置i宠幸沿着路经去检查平衡因子
*
*/
bool erase(const K& key)
{
//先找到
Node* cur = _root;
while (cur)
{
if (cur->_val.first < key)
cur = cur->_right;
else if (cur->_val.first > key)
cur = cur->_left;
else//找到了
break;
}
if (cur == nullptr)//没有这个节点，直接退出
return false;
//找到key节点了
Node* parent = cur->_parent;
Node* del = cur;
if (cur->_left == nullptr && cur->_right == nullptr)//情况一
{
if (_root == del)
{
delete del;
_root = nullptr;
return true;
}
if (parent->_left == del)
{
parent->_bf++;
parent->_left = nullptr;
}
else
{
parent->_bf--;
parent->_right = nullptr;
}
delete del;
}
else if (cur->_left == nullptr || cur->_right == nullptr)//情况二
{
Node* pnext;
if (cur->_left == nullptr)//有右子树
{
pnext = cur->_right;
}
else//有左子树
{
pnext = cur->_left;
}
if (_root == cur)
{
_root = pnext;
return true;//也可以避免parent为空的情况
}
if (parent->_left == cur)//左子树
{
parent->_left = pnext;
pnext->_parent = parent;
parent->_bf++;
}
else
{
parent->_right = pnext;
pnext->_parent = parent;
parent->_bf--;
}
delete del;
cur = pnext;
}
else//情况三
{
//找右子树最左边的节点
Node* snode = cur->_right;
Node* pare = cur;
while (snode)
{
pare = snode;
snode = snode->_left;
}
//找到了交换点
cur->_val = pare->_val;
//然后删除交换点
Node* ppare = pare->_parent;
if (pare->_right)
{
if (ppare->_left == pare)
{
ppare->_left = pare->_right;
pare->_right->_parent = ppare;
ppare->_bf++;
}
else
{
ppare->_right = pare->_right;
pare->_right->_parent = ppare;
ppare->_bf--;
}
}
else
{
if (ppare->_left == pare)
{
ppare->_left = nullptr;
ppare->_bf++;
}
else
{
ppare->_right = nullptr;
ppare->_bf--;
}
}
delete pare;
parent = ppare;
}
while (parent)
{
if (parent->_bf == 0)//反而要向上更新,其子树的高度出现了降低
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -1 || parent->_bf == 1)//不用向上更新，对于根节点而言，其高度没有变化
{
break;
}
else if (parent->_bf == -2 || parent->_bf == 2)//进行旋转修正AVL树的结构
{
if (parent->_bf == -2)
{
if (parent->_left->_bf == -1)//左边高，需要右旋
{
Rotate_Right(parent);//传递出问题的子树的根节点
}
else if (parent->_left->_bf == 1)//先左旋，在右旋
{
Rotate_LR(parent);
}
}
else if (parent->_bf == 2)
{
if (parent->_right->_bf == 1)//右边子树高，需要左旋
{
Rotate_Left(parent);
}
else if (parent->_right->_bf == -1)//先右旋，再左旋
{
Rotate_RL(parent);
}
}
break;
}
else
{
assert(false);
}
if (parent == nullptr)
break;
if (cur->_bf == 0)//才需要更新节点的平衡因子
{
if (parent->_left == cur)//平衡因子更新
{
parent->_bf++;
}
else
{
parent->_bf--;
}
}
}
return true;
}
private:
Node* _root;
};
注意
AVL树最关键的就是插入与删除的逻辑，与4种旋转实现的逻辑。