简介
自平衡二叉树（AVL）属于二叉平衡树的一类，此类树主要完成一个从键到值的查找过程，即字典（或映射），它维护树高度的方式与其他数据结构不同。
自平衡规则：
- AVL树的左、右子树都是AVL树
- 左、右子树的高度差不超过1
在数据结构中，最常见的数据间关系的抽象就是集合（Collection）和字典（Dictionary）。
集合就是线性表（元素允许重复），而字典是一种非多键映射关系（键不允许重复）。
对集合而言，一个班中的所有学生构成一个集合，可以是有序的（有序集合）也可以是无序的（无序集合），查找的时间复杂度一般是O(n)，很低。集合的典型就是C#中的List，STL中的vector。集合主要用于存储数据，很少用于查找。如要用于查找，那么可以选择基于有序表的二分查找，相应时间复杂度是O(logn)，而要想从无序表转变为有序表，就是各种排序算法的使命了。
而对字典而言，如同根据一个学生的学号找到他这次考试的成绩一样，主要是用于查找的。这是从键到值的单值映射，键不能重复，值可以重复。根据键找到值是字典的工作。如果是平衡查找树，就为O(logn)，实现一般以红黑树为主（比AVL简单），如Java的TreeMap、STL的map；如果是哈希表，就为O(1)，如Java的HashMap。
源码
由于网上的算法通常是以递归形式出现的，且结点有父指针，更加*。但是在这里，没有递归，没有父指针，这就意味着，算法的实现难度要更高，算法的维护与调试用了两天时间。
解决递归问题靠栈，解决无父指针问题靠栈，殊途同归。
avltree.h(AVL Tree) AVL树模版
baltree.h(Balance Tree) 平衡树基类
btree.cpp(Binary Tree and Console) main函数
树的建立
在这里，只讲元素的插入，而对于删除操作，由于其复杂性，暂且不能实现，参考网上关于树的旋转等资料，实现了删除操作，但没有进行完整测试。
结点的数据结构为：
template<class T>
struct AVLNode
{
T data;
AVLNode *lchild, *rchild;
int BF; // 平衡因子
};
前面与二叉树一样，BF用于累计高度差，因为查询高度是一个枯燥的递归操作。
这里用到了数学归纳的知识，一开始，树的BF是满足要求的，那么，我们对树的每个操作若可以保证BF满足条件要OK，由于后面的操作建立在前面的操作之上，只要保证了每一步操作的可靠性，那么BF的正确性就是可以保障的。这就要求对于每一个插入和删除操作，要保证类似于数据库那样的ACID特性中的一致性，类比数据库，只要一步操作出错，就算后面的操作是正确的，数据库也没法正常使用了。
创建结点：
template<class T, class N>
N* AVLTree<T, N>::New()
{
N* newp = BiTree<T, N>::New();
newp->BF = 0;
return newp;
}
按数组插入：
template<class T, class N>
AVLTree<T, N>::AVLTree(const vector<T>& s)
{
if (s.empty()) throw "数组不能为空";
root = new N;
root->data = s[0];
root->BF = 0;
root->lchild = NULL;
root->rchild = NULL;
for (int i = 1; i < s.Length(); i++) Insert(s[i]);
}
树的旋转
1）LL
template<class T, class N>
inline TStatus AVLTree<T, N>::RotateLL(N *&p, N *&parent, N *ancestor)
{
// 前
// A(parent,root),BF(2)
// |
// B(p),BF(1)__________|_____AR
// |
// BL(X)_____|_____BR // 后
// B(p,root),BF(0)
// |
// BL(X)_____|___________________A(parent),BF(0)
// |
// BR_____|_____AR bool descent = !parent->rchild;
this->RotateRight(p, parent, ancestor); parent->BF = p->BF == 1 ? 0 : 1;
p->BF--;
N *swap; swap = p; p = parent; parent = swap;
return (ancestor && descent) ? parent == ancestor->lchild ? T_DECL : T_DECR : T_OK;
}
2）RR
template<class T, class N>
inline TStatus AVLTree<T, N>::RotateRR(N *&p, N *&parent, N *ancestor)
{
// 前
// A(parent,root),BF(-2)
// |
// AL_____|___________________|
// B(p),BF(-1)
// BL_____|_____BR(X) // 后
// B(p,root),BF(0)
// |
// A(parent),BF(0)_____|_____BR(X)
// |
// AL_____|_____BL bool descent = !parent->lchild;
this->RotateLeft(p, parent, ancestor); parent->BF = p->BF == -1 ? 0 : -1;
p->BF++;
N *swap; swap = p; p = parent; parent = swap;
return (ancestor && descent) ? parent == ancestor->lchild ? T_DECL : T_DECR : T_OK;
}
3）LR
template<class T, class N>
inline TStatus AVLTree<T, N>::RotateLR(N *&p, N *&parent, N *ancestor)
{
////////////////////////////////////////////////////////////////////////// // >>>> 情况一 // 前
// A(parent,root),BF(2)
// |
// B(p),BF(-1)_________|_____AR
// |
// BL_____|_____C(pc),BF(1)
// |
// CL(X)______|______CR // 后（减少一层）
// C(pc,root),BF(0)
// |
// B(p),BF(0)____|_____A(parent),BF(-1)
// | |
// BL_____|_____CL(x) CR_____|_____AR ////////////////////////////////////////////////////////////////////////// // >>>> 情况二 // 前
// A(parent,root),BF(2)
// |
// B(p),BF(-1)_________|_____AR
// |
// BL_____|_____C(pc),BF(-1)
// |
// CL______|______CR(X) // 后（减少一层）
// C(pc,root),BF(0)
// |
// B(p),BF(1)____|_____A(parent),BF(0)
// | |
// BL_____|_____CL CR(x)_____|_____AR N *pc = p->rchild;
this->RotateLeft(pc, p, parent);
this->RotateRight(pc, parent, ancestor); if (pc->BF == 1)
{
p->BF = 0;
parent->BF = -1;
pc->BF = 0;
}
else if (pc->BF == -1)
{
p->BF = 1;
parent->BF = 0;
pc->BF = 0;
}
else
{
parent->BF = 0;
p->BF = 0;
}
parent = pc;
return ancestor ? parent == ancestor->lchild ? T_DECL : T_DECR : T_OK;
}
4）RL
template<class T, class N>
inline TStatus AVLTree<T, N>::RotateRL(N *&p, N *&parent, N *ancestor)
{
////////////////////////////////////////////////////////////////////////// // >>>> 情况一 // 前
// A(parent,root),BF(-2)
// |
// AL_____|___________________B(p),BF(1)
// |
// C(pc),BF(-1)__|______BR
// |
// CL_____|_____CR(X) // 后（减少一层）
// C(pc,root),BF(0)
// |
// A(parent),BF(1)|_____B(p),BF(0)
// | |
// AL_____|_____CL CR(x)_____|_____BR ////////////////////////////////////////////////////////////////////////// // >>>> 情况二 // 前
// A(parent,root),BF(-2)
// |
// AL_____|___________________B(p),BF(1)
// |
// C(pc),BF(1)___|______BR
// |
// CL(X)_____|_____CR // 后（减少一层）
// C(pc,root),BF(0)
// |
// A(parent),BF(0)|_____B(p),BF(-1)
// | |
// AL_____|_____CL(x) CR_____|_____BR N *pc = p->lchild;
this->RotateRight(pc, p, parent);
this->RotateLeft(pc, parent, ancestor); if (pc->BF == -1)
{
parent->BF = 1;
p->BF = 0;
pc->BF = 0;
}
else if (pc->BF == 1)
{
parent->BF = 0;
p->BF = -1;
pc->BF = 0;
}
else
{
parent->BF = 0;
p->BF = 0;
}
parent = pc;
return ancestor ? parent == ancestor->lchild ? T_DECL : T_DECR : T_OK;
}
5）左旋
template<class T, class N>
void BALTree<T, N>::RotateLeft(N *p, N *parent, N *ancestor)
{
// 前
// A(parent,root)
// |
// AL_____|___________________|
// B(p)
// BL_____|_____BR(X) // 后
// B(p,root)
// |
// A(parent)___________|_____BR(X)
// |
// AL_____|_____BL parent->rchild = p->lchild;
p->lchild = parent; if (ancestor != NULL)
{
if (ancestor->lchild == parent) // 修改p的双亲为ancestor
ancestor->lchild = p;
else
ancestor->rchild = p;
}
else
{
this->root = p;
}
}
6）右旋
template<class T, class N>
void BALTree<T, N>::RotateRight(N *p, N *parent, N *ancestor)
{
// 前
// A(parent,root)
// |
// B(p)________________|_____AR
// |
// BL(X)_____|_____BR // 后
// B(p,root)
// |
// BL(X)_____|___________________A(parent)
// |
// BR_____|_____AR parent->lchild = p->rchild;
p->rchild = parent; if (ancestor != NULL)
{
if (ancestor->lchild == parent) // 修改p的双亲为ancestor
ancestor->lchild = p;
else
ancestor->rchild = p;
}
else
{
this->root = p;
}
}
结点的插入
对于AVL，结点的插入是一项复杂的工作。由于插入操作，树原本的平衡被破坏，需要重新调整一次。
基本步骤是：
- 二分查找，找到相应的空位置，并插入（若已存在则忽略），同时存储查找路径
- 从路径逆着向上找到第一个最小不平衡子树的根结点的父结点，接下来就是对这个子树进行调整
- 调整子树，有LL、LR、RL、RR四种情况
1）添加结点
template<class T, class N>
bool BALTree<T, N>::Insert(T data)
{
N* newp; if (this->root == NULL)
{
newp = this->New();
newp->data = data;
this->root = newp;
this->HandleRoot();
return true;
} stack<N*> path; // 存储插入前的查找路径（便于回溯） //////////////////////////////////////////////////////////////////////////
// 插入操作
N *p = this->root;
while (true)
{
path.push(p);
if (data < p->data) // 插入值小于根结点，入左子树
{
if (p->lchild != NULL)
{
p = p->lchild; // 值小于LL，则递归入L
}
else
{
newp = this->New();
newp->data = data;
path.push(newp);
p->lchild = newp;
break; // 根结点无左孩子，正好插入
}
}
else if (data > p->data) // 插入值大于根结点，入右子树
{
if (p->rchild != NULL)
{
p = p->rchild; // 值大于RR，则递归入R
}
else
{
newp = this->New();
newp->data = data;
path.push(newp);
p->rchild = newp;
break; // 根结点无右孩子，正好插入
}
}
else // 插入值等于根结点，返回
{
return false;
}
} // 插入完毕 ////////////////////////////////////////////////////////////////////////// // 调整插入路径上的结点
BalanceAfterInsert(path);
return true;
}
2）插入后的平衡
template<class T, class N>
void BALTree<T, N>::BalanceAfterInsert(stack<N*>& path)
{
N *child = NULL; // *child作为*p的孩子结点
N *p = path.top();
path.pop();
N *parent = path.top(); // *parent是*p的父结点
path.pop();
N *ancestor;
while (true)
{
ancestor = path.empty() ? NULL : path.top();
TStatus status = CheckPathAfterInsert(child, p, parent, ancestor);
switch (status)
{
case T_OK:
return;
case T_BREAK:
BalanceInternalAfterInsert(child, p, parent, ancestor);
return;
case T_CONTINUE:
break;
} if (path.empty())
return; child = p;
p = parent;
parent = path.top(); // 由path向上回溯
path.pop();
}
}
3）检查平衡
template<class T, class N>
TStatus AVLTree<T, N>::CheckPathAfterInsert(N *child, N *p, N *parent, N *ancestor)
{
if (parent->lchild == p) // p是parent的左孩子，那么parent的BF++
parent->BF++; // BF的变化：-1->0->1->2
else // p是parent的右孩子，那么parent的BF--
parent->BF--; // BF的变化：1->0->-1->-2 if (parent->BF == 2 || parent->BF == -2) // *parent是失衡结点（第一个|BF|>=2）
return T_BREAK; // 找到最小不平衡子树的根结点 if (parent->BF == 0) // 在插入新结点后，*parent的左右子树高度相等（BF为0），说明以*parent为根的子树高度未增加
return T_OK; // 所以路径中的其余祖先结点无需调整BF return T_CONTINUE;
}
4）调整平衡
template<class T, class N>
TStatus AVLTree<T, N>::BalanceInternalAfterInsert(N *child, N *p, N *parent, N *ancestor)
{
////////////////////////////////////////////////////////////////////////// if (parent->BF == 2 && p->lchild == child) // LL
{
RotateLL(p, parent, ancestor);
} ////////////////////////////////////////////////////////////////////////// else if (parent->BF == -2 && p->rchild == child) // RR
{
RotateRR(p, parent, ancestor);
} ////////////////////////////////////////////////////////////////////////// else if (parent->BF == 2 && p->rchild == child) // LR
{
RotateLR(p, parent, ancestor);
} ////////////////////////////////////////////////////////////////////////// else if (parent->BF == -2 && p->lchild == child) // RL
{
RotateRL(p, parent, ancestor);
} ////////////////////////////////////////////////////////////////////////// return T_OK;
}
调整过程全部是旋转操作
结点的删除
结点的删除比插入要复杂得多。删除某一结点后，可能需要多次调整。
基本步骤是：
- 二分查找，找到要删除的结点，并用最近的结点替换掉它，然后删除它，调整BF
- 从路径逆着向上找到第一个最小不平衡子树的根结点的父结点，接下来就是对这个子树进行调整
- 调整子树，有LL、LR、RL、RR四种情况，如果调整后子树高度下降（即父结点BF改变），那么跳到步骤2
1）定位结点
template<class T, class N>
bool BALTree<T, N>::Delete(T data)
{
if (this->root == NULL)
{
return false;
} stack<N*> path; // 存储删除前的查找路径（便于回溯） //////////////////////////////////////////////////////////////////////////
// 查找操作
N *p = this->root;
while (true)
{
path.push(p);
if (data < p->data) // 插入值小于根结点，入左子树
{
if (p->lchild != NULL)
{
p = p->lchild; // 值小于LL，则递归入L
}
else
{
return false; // 没找到
}
}
else if (data > p->data) // 插入值大于根结点，入右子树
{
if (p->rchild != NULL)
{
p = p->rchild; // 值大于RR，则递归入R
}
else
{
return false; // 没找到
}
}
else // 找到
{
break;
}
} // 定位成功 ////////////////////////////////////////////////////////////////////////// // 调整删除路径上的结点
BalanceAfterDelete(path);
return true;
}
2）删除结点
template<class T, class N>
void BALTree<T, N>::BalanceAfterDelete(stack<N*>& path)
{
// 替代结点
Replace(path); if (path.empty())
return; // 删除结点并平衡 N *p = NULL;
N *child = NULL; // *child作为*p的孩子结点
N *parent = path.top(); // *parent是*p的父结点
path.pop();
N *ancestor;
TStatus status = T_OK;
while (true)
{
ancestor = path.empty() ? NULL : path.top();
if (status == T_CONTINUE_STATUS)
status = ancestor ? parent == ancestor->lchild ? T_DECL : T_DECR : T_OK;
status = CheckPathAfterDelete(child, p, parent, ancestor, status);
switch (status)
{
case T_OK:
return;
case T_BREAK:
status = BalanceInternalAfterDelete(child, p, parent, ancestor);
if (status == T_OK)
return;
break;
case T_CONTINUE:
status = T_OK;
break;
case T_CONTINUE_STATUS:
break;
} if (path.empty())
return; child = p;
p = parent;
parent = path.top(); // 由path向上回溯
path.pop();
}
}
3）替换结点
删除结点前，先将结点与其他结点进行替换，使得对于结点的删除转变为对于叶子结点的删除。
template<class T, class N>
void AVLTree<T, N>::Replace(stack<N*>& path)
{
N *p = path.top();
path.pop();
N *parent = path.empty() ? NULL : path.top();
if (!p->lchild && !p->rchild) // p为叶子结点，直接删除
{
if (!parent) // 根结点
{
this->root = NULL;
}
else if (parent->lchild == p)
{
parent->lchild = NULL;
parent->BF--;
}
else
{
parent->rchild = NULL;
parent->BF++;
}
}
else if (p->lchild && p->rchild) // 双子树，转化为单子树
{
// 注意：替换时，BF也要替换
if (p->lchild->rchild) // 替换左子树最右结点
{
vector<N*> new_path;
new_path.push_back(p->lchild);
N *lr = p->lchild->rchild;
while (lr)
{
new_path.push_back(lr);
lr = lr->rchild;
}
path.push(new_path.back());
lr = path.top();
new_path.pop_back();
for (vector<N*>::iterator it = new_path.begin(); it != new_path.end(); it++)
{
path.push(*it);
}
lr->BF = p->BF;
if (!parent) // 根结点
this->root = lr;
else if (parent->lchild == p)
parent->lchild = lr;
else
parent->rchild = lr;
path.top()->rchild = lr->lchild;
path.top()->BF++;
lr->lchild = p->lchild;
lr->rchild = p->rchild;
}
else if (p->rchild->lchild) // 替换右子树最左结点
{
vector<N*> new_path;
new_path.push_back(p->rchild);
N *rl = p->rchild->lchild;
while (rl)
{
new_path.push_back(rl);
rl = rl->lchild;
}
path.push(new_path.back());
rl = path.top();
new_path.pop_back();
for (vector<N*>::iterator it = new_path.begin(); it != new_path.end(); it++)
{
path.push(*it);
}
rl->BF = p->BF;
if (!parent) // 根结点
this->root = rl;
else if (parent->lchild == p)
parent->lchild = rl;
else
parent->rchild = rl;
path.top()->lchild = rl->rchild;
path.top()->BF--;
rl->lchild = p->lchild;
rl->rchild = p->rchild;
}
else // 替代孩子
{
if (!parent) // 根结点
{
if (this->root->BF != -1)
{
this->root = p->lchild;
this->root->rchild = p->rchild;
this->root->BF = p->BF - 1;
}
else
{
this->root = p->rchild;
this->root->lchild = p->lchild;
this->root->BF = p->BF + 1;
}
}
else if (parent->lchild == p)
{
if (parent->BF != -1)
{
parent->lchild = p->lchild;
parent->lchild->rchild = p->rchild;
parent->lchild->BF = p->BF - 1;
}
else
{
parent->lchild = p->rchild;
parent->lchild->lchild = p->lchild;
parent->lchild->BF = p->BF + 1;
}
path.push(parent->lchild);
}
else
{
if (parent->BF != -1)
{
parent->rchild = p->lchild;
parent->rchild->rchild = p->rchild;
parent->rchild->BF = p->BF - 1;
}
else
{
parent->rchild = p->rchild;
parent->rchild->lchild = p->lchild;
parent->rchild->BF = p->BF + 1;
}
path.push(parent->rchild);
}
}
}
else if (p->lchild) // 左单子树
{
if (!parent) // 根结点
{
this->root = p->lchild;
}
else
{
if (parent->lchild == p)
{
parent->lchild = p->lchild;
parent->BF--;
}
else
{
parent->rchild = p->lchild;
parent->BF++;
}
}
}
else // 右单子树
{
if (!parent) // 根结点
{
this->root = p->rchild;
}
else
{
if (parent->lchild == p)
{
parent->lchild = p->rchild;
parent->BF--;
}
else
{
parent->rchild = p->rchild;
parent->BF++;
}
}
}
delete p;
}
4）检查平衡
template<class T, class N>
TStatus AVLTree<T, N>::CheckPathAfterDelete(N *child, N *p, N *parent, N *ancestor, TStatus status)
{
if (status == T_OK)
{
if (p && p->BF == 0)
{
if (parent->lchild == p) // p是parent的左孩子，p的BF为0，说明p层数减少一，故parent的BF--
parent->BF--;
else // p是parent的右孩子，p的BF为0，说明p层数减少一，故parent的BF++
parent->BF++;
}
}
else
{
if (status == T_DECL) //平衡后，子树高度减少，那么要向上检查平衡性
{
parent->BF--;
return parent->BF == 0 ? T_CONTINUE_STATUS : T_OK;
}
else if (status == T_DECR) //平衡后，子树高度减少，那么要向上检查平衡性
{
parent->BF++;
return parent->BF == 0 ? T_CONTINUE_STATUS : T_OK;
}
} if (parent->BF == 2 || parent->BF == -2) // *parent是失衡结点（第一个|BF|>=2）
return T_BREAK; // 找到最小不平衡子树的根结点 if (parent->BF != 0) // 在删除结点后，*parent的左右子树高度差绝对值为1（|BF|为1），说明以*parent为根的子树高度未改变
return T_OK; // 所以路径中的其余祖先结点无需调整BF return T_CONTINUE;
}
5）调整平衡
template<class T, class N>
TStatus AVLTree<T, N>::BalanceInternalAfterDelete(N *child, N *p, N *parent, N *ancestor)
{
////////////////////////////////////////////////////////////////////////// if (parent->BF == 2 && (!p || parent->rchild == p)) // L
{
p = parent->lchild; if (p->BF == -1) // LR
{
return RotateLR(p, parent, ancestor);
}
else // LL
{
return RotateLL(p, parent, ancestor);
}
} ////////////////////////////////////////////////////////////////////////// else if (parent->BF == -2 && (!p || parent->lchild == p)) // R
{
p = parent->rchild; if (p->BF == 1) // RL
{
return RotateRL(p, parent, ancestor);
}
else // RR
{
return RotateRR(p, parent, ancestor);
}
} //////////////////////////////////////////////////////////////////////////
return T_OK;
}
总结
虽然算法的实现思路很简单，但实际要考虑很多因素，稍微一个小错误都可能导致结果不一致的现象（BF未调整）。然而，在理解AVL上的基础上，理解红黑树就不那么困难了。
相比较AVL的递归算法而言，可以看出，递归算法是具有简洁美的，这是由二叉树的递归性质决定的。
由于AVL操作的复杂性，因而不常用AVL，现在主要使用红黑树（RBT），它们的区别是：
- AVL讲究整体平衡，因而要求严格、操作复杂 ，子树高度差不大于1
- RBT追求局部平衡，因而实现较AVL简单，最长路径比上最短路径小于2