AVL树解析（基于查找二叉树（dynamicSearchTree））
平衡二叉树：
在查找二叉树的基础上要求每个节点左右字节点的高度差不能超过一。
于是对于节点多了一个数据成员高度来实现这一功能。
- 先附上源代码
#include "dynamicSearchTable.h"
template <class KEY, class OTHER>
struct SET
{
KEY key; //关键字信息
OTHER other; //和其他信息
};
template <class KEY,class OTHER>
class AvlTree :public dynamicSearchTable<KEY, OTHER>
{
struct AvlNode
{
SET<KEY, OTHER>data;
AvlNode* left;
AvlNode* right;
int height;
AvlNode(const SET<KEY, OTHER>& element, AvlNode* lt, AvlNode* rt, int h = 1):data(element),left(lt),right(rt),height(h){}
};
AvNodee* root;
public:
AvlTree() { root = NULL;}
~AvlTree() { makeEmpty(root);}
SET<KEY, OTHER>* find(const KEY& x)const;
void insert(const SET<KEY, OTHER>& x);
void remove(const KEY& x);
private:
void insert(const SET<KEY, OTHER>& x, AvlNode*& t);
bool remove(const KEY& x, AvlNode*& t);
void makeEmpty(AvlNode* t);
int height(AvlNode* t)const { return t == NULL ? 0 : t->height;}
void LL(AvlNode*& t);
void LR(AvlNode*& t);
void RL(AvlNode*& t);
void RR(AvlNode*& t);
int max(int a, int b) { return (a > b) ? a : b;}
bool adjust(AvlNode*& t, int subTree);
};
template <class KEY, class OTHER>
SET<KEY, OTHER>* AvlTree<KEY, OTHER>::find(const KEY& x)const
{
AvlNode* t = root;
while (t != NULL && t->data.key != x)
{
if (t->data.key > x)t = t->left;
else t = t->right;
}
if (t == NULL)return NULL;
else return (SET<KEY, OTHER>*)t;
}
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::LL(AvlNode*& t)
{
AvlNode* t1 = t->left;
t->left = t1->right;
t1->right = t;
t->height = max(height(t->left), height(t->right)) + 1;
t1->height = max(height(t->left), height(t)) + 1;
t = t1;
}
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::RR(AvlNode*& t)
{
AvlNode* t1 = t->right;
t->right = t1->left;
t1->left = t;
t->height = max(height(t->left), height(t->right)) + 1;
t1->height = max(height(t->right), height(t)) + 1;
t = t1;
}
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::LR(AvlNode*& t)
{
RR(t->left);
LL(t);
}
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::RL(AvlNode*& t)
{
LL(t->right);
RR(t);
}
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x)
{
insert(x, root);
}
template <class KEY, class OTHER>
void AvlTree<KEY,OTHER>::insert(const SET<KEY, OTHER>&x, AvlNode*& t)
{
if (t == NULL)
t = new AvlNode(x, NULL, NULL);
else if (x.key < t->data.key)
{
insert(x, t->left);
if (height(t->left) - height(t->right) == 2)
if (x.key < t->left->data.key)LL(t);
else LR(t);
}
else if (t->data.key < x.key)
{
insert(x, t->right);
if (height(t->right) - height(t->left) == 2)
if (t->right->data.key < x.key)RR(t);
else LR(t);
}
t->height = max(height(t->left), height(t->right)) + 1;
}
template<class KEY,class OTHER>
void AvlTree<KEY, OTHER>::remove(const KEY& x)
{
remove(x, root);
}
template<class KEY, class OTHER>
bool AvlTree<KEY, OTHER>::remove(const KEY& x, AvlNode* & t)
{
if (t == NULL)return true;
if (x == t->data.key)
{
if (t->left == NULL || t->right == NULL)
{
AvlNode* oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
return false;
}
else
{
AvlNode* tmp = t->right;
while (tmp->left != NULL)tmp = tmp->left;
t->data = tmp->data;
if (remove(tmp->data.key, t->right))return true;
return adjust(t, 1);
}
}
if (x < t->data.key)
{
if (remove(x, x->left))return true;
return adjust(t, 0);
}
else
{
if (remove(x, t->right))return true;
return adjust(t, 1);
}
}
template<class KEY, class OTHER>
bool AvlTree<KEY, OTHER>::adjust(AvlNode*& t, int subTree)
{
if (subTree)
{
if (height(t->left) - height(t->right) == 1)return true;
if (height(t->right) == height(t->left))
{
--t->height; return false;
}
if (height(t->left->right) > height(t->left->left))
{
LR(t);
return false;
}
LL(t)
if (height(t->right) == height(t->left))return false;
else return true;
}
else
{
if (height(t->right) - height(t->left) == 1)return true;
if (height(t->right) == height(t->left))
{
--t->height; return false;
}
if (height(t->right->left) > height(t->right->right))
{
RL(t);
return false;
}
RR(t)
if (height(t->right) == height(t->left))return false;
else return true;
}
}
template<class KEY, class OTHER>
void AvlTree<KEY, OTHER>::makeEmpty(AvlNode* t)
{
if (t == NULL)return;
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
基本组成成员
- AvlNode（AVL的树节点）
struct AvlNode
{
SET<KEY, OTHER>data;
AvlNode* left;
AvlNode* right;
int height; //节点的高度
AvlNode(const SET<KEY, OTHER>& element, AvlNode* lt, AvlNode* rt,
int h=1):data(element),left(lt),right(rt),height(h){}
};
多了一个高度，构造函数默认为1（指只有自己）
- 根节点
AvNodee* root;
AVL类的基本数据成员和函数
template <class KEY,class OTHER>
class AvlTree :public dynamicSearchTable<KEY, OTHER>
{
struct AvlNode
{
SET<KEY, OTHER>data;
AvlNode* left;
AvlNode* right;
int height;
AvlNode(const SET<KEY, OTHER>& element, AvlNode* lt, AvlNode* rt, int h = 1):data(element),left(lt),right(rt),height(h){}
};
AvNodee* root;
public:
AvlTree() { root = NULL;}
~AvlTree() { makeEmpty(root);}
SET<KEY, OTHER>* find(const KEY& x)const; //查找函数
void insert(const SET<KEY, OTHER>& x); //插入函数（公有）
void remove(const KEY& x); //删除函数（公有）
private:
void insert(const SET<KEY, OTHER>& x, AvlNode*& t); //插入函数（私有）
bool remove(const KEY& x, AvlNode*& t); //删除函数（私有）
void makeEmpty(AvlNode* t); //清空
int height(AvlNode* t)const { return t == NULL ? 0 : t->height;} //计算当前节点的高度
void LL(AvlNode*& t); //单旋转LL
void LR(AvlNode*& t); //双旋转LR
void RL(AvlNode*& t); //双旋转RL
void RR(AvlNode*& t); //单旋转RR
int max(int a, int b) { return (a > b) ? a : b;} //比较函数
bool adjust(AvlNode*& t, int subTree); //调整节点的结构使其平衡的函数
};
其实private类的函数都是公有类函数的工具函数
函数的实现分析
- 查找函数（find）
template <class KEY, class OTHER>
SET<KEY, OTHER>* AvlTree<KEY, OTHER>::find(const KEY& x)const
{
AvlNode* t = root;
while (t != NULL && t->data.key != x) //循环停止的条件，就是当前节点为空或者就是要找的
{ //小于就换成左节点，反之换成右节点，
if (t->data.key > x)t = t->left;
else t = t->right;
}
if (t == NULL)return NULL; //空就返回
else return (SET<KEY, OTHER>*)t; //这里还是强制转换
}
还是基于二叉查找树的特性，只是没有使用递归函数，这种方式被称为迭代实现
- 插入函数（insert）
在介绍函数之前理解一些东西，关于插入的一些特性：
1. 首先插入还是和二叉查找树一样插入在叶子节点上
2. 一次插入后，只有在插入点到根的路径上的节点才有可能发生平衡度的变化
3. AVL的平衡策略最多只要调整一个节点就可以了
主要分析LL和LR俩种情况
注意：
对于旋转策略的核心是保证节点的高度不发生变化，就是通过旋转变为原来的高度，从而保证对上面节点安全的保证。
一旦改变了数的高度，那需要不断往上检索，直到那个节点的高度没有发生变化
LL：原来A的左子树比右子树高，插入发生在A的左儿子的左子树中，使A的左子树增高
(注意（仅仅对于插入而言，对于删除这个结论反而相反）：平衡度只是一种高度是否平衡的表现形式，真正影响的是节点的高度，主要体现在平衡度向零趋近高度不变，而向俩边增长表明节点高度发生改变)
此图有图
节点平衡度从-1到0但是并不影响上面的节点，因为这个节点的高度并未发生改变，反而0到1表明当前节点的高度发生改变
现在来分析LL的情况
此处有图
首先分析一下一些情况：
1. **首先B的平衡度一定原来是0，然后变为1，
因为我们上面解释过如果是-1到0表明是向零趋近，B的高度不会发生变化，进而不会影响A
若是原来是1，变成2，显然B才是危机节点，处理就不是A了
对于LL解决办法就是向右旋转
此处有图
显然我们发现在旋转后我们发现我们处理的这个树的高度与插入前的高度完全一样，于是不用担心上面节点的平衡度了
思考：
对于这种旋转必然是左右子树未实现满二叉树或者完全二叉树导致，就是有空缺的位置来保证旋转后高度不发生变化
那么假设是满二叉树插入，我们会发现并不影响平衡度都从（0到1或者0到-1）
（其实这就是插入点后的检索过程，虽然高度发生了变化，但是一直向上检索发现平衡度没有打破规则，那么就会检索到根节点结束）
现在附上LL代码图
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::LL(AvlNode*& t) //注意这里传的是原来的指针，估计是父节点的指针，不然改了没意义 A
{
AvlNode* t1 = t->left; //失衡的A，先标记B点为t1（A的左子节点）
t->left = t1->right; //B的右子树，变成A的左子树
t1->right = t; //B的右子节点变成A
t->height = max(height(t->left), height(t->right)) + 1; //此时更新各自的高度（+1是为了包括本身）
t1->height = max(height(t->left), height(t)) + 1;
t = t1; //将t彻底变为B点（B成为t的指向点）
}
有心情的话 可以在这个补一个过程图，看我以后记不记的住吧
*1.*我们发现指针还是引用传递，主要是我要旋转A点，那么就需要修改A的父节点对应的指针从。原理和二叉查找树的原理相同
RR也是同理只是向左旋转
附上RR的代码
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::RR(AvlNode*& t) //这个和上面是一个道理，就是向左转，就像镜像一样
{
AvlNode* t1 = t->right;
t->right = t1->left;
t1->left = t;
t->height = max(height(t->left), height(t->right)) + 1;
t1->height = max(height(t->right), height(t)) + 1;
t = t1;
}
现在来分析LR的情况
为什么要单独讨论这种情况？
因为我们发现仅仅如果使用LL右旋发现只是不过对这个树镜像对称过去了而已，A点仍然是失衡点，只不过是现在是右子树高了
此处有图
我们相对于之前多了一个参考C节点，对于CL和CR谁的高度为h-1并不重要
为了保证根节点的高度不发生变化，我们选择LR的双旋转的方法，对B点进行左旋转（RR），再对A点进行右旋转（LL）
不难发现，C点占据了原来的根节点，且平衡度恢复了0，因为是1到0我们便可认定节点的高度没有发生变化，从而无需再向上检索
过程如下图显示
其实逻辑也很好理解就是让根节点的右边多一个高度来平衡多的那个节点
代码如下
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::LR(AvlNode*& t)
{
RR(t->left); //先对B进行左旋
LL(t); //再对A点进行右旋
}
RL也完全是同理，就是对称了一下
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::RL(AvlNode*& t)
{
LL(t->right);
RR(t);
}
以上我们分析了四种旋转情况接下来就来分析插入函数
前面我们提到了一个关键词回溯
对于代码里面的回溯就是在修改后往回检查，最好想的就是树了，我修改了叶节点，我需要对查找路径上的每一个点进行检查，那么我们在代码中如何往回实现这个功能呢？
答案就是利用
递归
假如我们要进行修改，并检查，可以用如下伪代码实现
插入函数
{
检查当前节点是不是插入点，是就插入
不是就根据于当前节点的大小调用“函数（左节点）/函数（右节点）”
//因为是递归调用，执行到这一样表示递归所有的修改已完成开始回溯了
检查当前节点的平衡度来看是否需要调整，若失衡分类讨论
重新计算高度
}
附上代码
其实我们发现这个回溯必须全部走完，因为要更改高度（尤其是满二叉树那种虽然不影响平衡度，但是路径上所有节点高度都需要+1）
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x)
{
insert(x, root);
}
template <class KEY, class OTHER>
void AvlTree<KEY,OTHER>::insert(const SET<KEY, OTHER>&x, AvlNode*& t)
{
if (t == NULL) //情况1：如果根节点为空就直接放置
t = new AvlNode(x, NULL, NULL);
else if (x.key < t->data.key) //情况2：如果比当前节点小，往左子树插入
{
insert(x, t->left); //向下递归
if (height(t->left) - height(t->right) == 2) //执行到这一步表示左子树全部节点都平衡了，检查自己了
if (x.key < t->left->data.key)LL(t); //当前节点失衡了，只要判断插入节点是在左子节点的左右
//就可以判断是哪种情况
else LR(t);
}
else if (t->data.key < x.key) //这里的逻辑是一样的，参照上面就行了
{
insert(x, t->right);
if (height(t->right) - height(t->left) == 2)
if (t->right->data.key < x.key)RR(t);
else LR(t);
}
t->height = max(height(t->left), height(t->right)) + 1; //在最后插入好，会从底往上重新计算树的高度
}
- 删除函数（remove）
删除节点很有可能导致树变矮，导致二叉树失衡，所以必须要在删除后不断回溯调整平衡
首先这是一个回溯的过程，还有一个关键点就是是否需要再网上回溯的关键是:
的当前节点的高度在调整后或者未调整高度是否发生变换，注意我说的是高度不是平衡度，若往回检索发现有节点高度未发生变化就可以停止检查调整步骤直接return。
这也表明了虽然删除是递归，但是返回值是一个bool表示当前节点高度是否发生变化从而决定上面的节点是否需要检查
删除过程
这一个和二叉查找树没什么区别其实，依旧是分为三种情况（无儿子，一个儿子，俩个儿子）
前俩个可以用一个表达式来代替
t=（t->left!=NULL）:t->left?t-right;
相对后面的情况显示是迭代找到可替换的叶子节点，然后删除叶子节点啦。
检查过程
删除的时候没有插入那么幸运，删除时的调整很有可能导致整棵树高度下降，从而影响路上的所有父节点。
停止条件：只有当某个节点读的高度在删除后不变才无需向上检查调整了
导致树的高度发生变化有以下几种情况
（注意：这里平衡度是在向两边增长节点高度不变，向零靠近节点高度发生变化，因为是删除
（与插入的结论恰恰相反，插入是有可能增高，而删除是有可能降低高度））
此处有五种情况（假设都是在左子树上删除的节点）
此处有图
对于（a）的平衡度既没有失衡，高度也没有发生变化
对于（b）平衡度没有失衡，但是根据平衡度的变化可以发现节点的高度发生变换，需要检查父节点
对于（c）只需要节点P使用左旋（RR）即可，这样根节点的高度就变成了0，虽然平衡了但是平衡度从-1变为0，节点高度发生变化，需要检查父节点
对于（d）显然左旋仍然导致失衡，就像前面的RL的情况一样发生在内侧，这个时候就需要先对P的右子节点先右旋（LL）再对P进行左旋（RR），就会使根节点平衡度变为0.不需要对父节点进行检查
对于（e）对P使用简单的左旋（RR）根节点（原来P的位置）的平衡度变为1（注意平衡度从-1到1，节点的高度并未发生变化，可以认为就像交换了一样）；当然可以使用RL，这样的话根节点的平衡度仍为-1，高度未发生变化。所以俩种方法都不需要检查父节点
对于添加在右子节点的方法对称就好了
附上代码
（指针参数还是引用，原因上面解释过了）
（true表示不用检查，false表示节点的高度发生变化，需要检查节点的高度）
- 删除函数
template<class KEY,class OTHER>
void AvlTree<KEY, OTHER>::remove(const KEY& x)
{
remove(x, root);
}
template<class KEY, class OTHER>
bool AvlTree<KEY, OTHER>::remove(const KEY& x, AvlNode* & t)
{
if (t == NULL)return true; //空树不存在，不用检查父节点
if (x == t->data.key) //情况1：如果是当前节点
{
if (t->left == NULL || t->right == NULL) //删除情况1，2：如果只是有一个子节点或者没有节点
{
AvlNode* oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode; //因为对只有一个节点或者无叶节点的删除必然导致高度变换，肯定是
return false; //要检查的
}
else
{
AvlNode* tmp = t->right; //删除情况三：有俩个子节点
while (tmp->left != NULL)tmp = tmp->left; //迭代找到右子树的最左子节点
t->data = tmp->data; //数据替换
if (remove(tmp->data.key, t->right)) //然后就是删除的目标换成最新的叶节点，从当前的节点右节点开始
return true; //如果这个删除最后返回的是true，表明右子节点的高度未变化
return adjust(t, 1); //1表示删除在右子树上，t表示当前节点失衡，需要调整
}
}
if (x < t->data.key) //情况2：小于则是向左找
{
if (remove(x, x->left))return true; //向左递归
return adjust(t, 0); //如果需要检查，则调用adjust，0表示删除的是左子树
}
else //情况三：大于则是向右找
{
if (remove(x, t->right))return true;
return adjust(t, 1);
}
}
这段逻辑其实挺绕人的，remove函数的返回值主要三种：
1：删除的是只有一个字节点或者无子节点（直接返回true，必然改变高度）
2：向下递归调用remove，如果调用返回的是true，则自己不用调整，也返回true
3：如果调用的remove返回false，则需要返回adjust，一边检查高度是否发生变换+调整，调整后如果高度变化返回false，反之true（具体就是我们讨论的几个调整情况）
- 调整函数（adjust）
参数subTree（subtract Tree）1表示删除的右子树，0表示删除的左子树
0则是我们讨论的那五种情况
1则是完全对称的五种情况
调用adjust不一定高度有变化，但是平衡度一点是发生变化了
template<class KEY, class OTHER>
bool AvlTree<KEY, OTHER>::adjust(AvlNode*& t, int subTree)
{
if (subTree) //如果删除的是右子树，逻辑和下面的只是镜面对称
{
if (height(t->left) - height(t->right) == 1)return true;
if (height(t->right) == height(t->left))
{
--t->height; return false;
}
if (height(t->left->right) > height(t->left->left))
{
LR(t);
return false;
}
LL(t)
if (height(t->right) == height(t->left))return false;
else return true;
}
else //如果删除的是左子树
{
if (height(t->right) - height(t->left) == 1)return true;
//对应（a）删除的左子树，如果是当前平衡度为-1，表示之前的平衡度就是0（如果是-1的话根本不会调用adjust好吧），因为删除是左子树，只有左子树降低高度的可能，（表示根据前面由平衡度判断高度结论判定）当前节点不需要调整+高度也没有发生变化
if (height(t->right) == height(t->left))
{
--t->height; return false;
}
//对应情况（b），根据结论一定是从1到0，高度一定发生变化了，但是平衡度依旧正常，返回false
if (height(t->right->left) > height(t->right->right))
{
RL(t);
return false;
}
//对应情况（d），右子节点的左子树的节点的高度大于右子树进行RL
RR(t)
if (height(t->right) == height(t->left))
return false;
else return true;
//对于（c）和（e）只需要RR（左旋即可），对于这两种情况使用RR后的区别就是（c）调整后平衡度为0，节点高度发生变化return false，对于（e）使用RR，节点应该变为1，但是高度没有发生变化，return true
}
}
到此难的地方已经处理好了其他的构造析构都是完全继承完全二叉树，所以不再赘述了