二叉查找树 (BST) 与 二叉平衡树 (AVL) 是两种树形数据结构，后者通过对前者的改良实现更优的时间复杂度，是经典的数据结构之一。
二叉查找树
对于一颗二叉查找树，一个结点的左子树上的数据完全小于根节点，右子树上的数据完全大于根节点，通过一次中序遍历可以得到一个有序序列。
因此该数据结构也可以用来排序。
根据不同的情景左右子树谁大谁小可以改变，等号是否取到也可以变化。
常用操作
- 查找
- 插入、建树
- 删除
查找
查找操作根据定义进行递归，直到搜索到想要的值或者是到空结点。
struct node
{
int data;
node *l,*r;
node()
{
l=NULL;
r=NULL;
}
}
node* search(node *root,int key)
{
if(!root)//已经搜索完了叶子结点，没有可能的值了，返回NULL
return NULL;
if(root->data==key)//找到了这个值，返回这个结点
{
return node;
}
if(root->data>key)//没有找到，开始递归，如果大于key向左子树查找，反之向右子树查找
{
return search(root->l,key);
}else{
return search(root->r,key);
}
}
插入及建树
插入操作通过递归寻找到合适的结点（叶子结点的左孩子或右孩子）进行插入。
建树使用插入操作完成。
node* insert(node *root,int key)
{
if(!root) //搜索到了合适的位置，开始插入。
{
root=new node;
root->data=key;
return root;
}
if(root->data>key)//寻找合适的结点
{
return insert(root->l,key);
}else{
return insert(root->r,key);
}
}
//以下是主函数部分，模拟输入插入的过程
a[100];
node *root;
for(int i=0;i<100,i++)
{
cin>>a[i];
root=insert(root,a[i]);
}
删除
分两种情况：
- 叶子结点，没有孩子结点，可以直接删除
- 不是叶子结点，有左右子树
对于第二种情况，需要找到待删除结点的前驱或者后继（以下描述的前提是该查找树是左子树小于根节点，右子树大于根节点）
- 前驱：比根节点小的最大结点，通过递归遍历根节点左子树的右子树直至叶子结点，即为根节点的前驱
- 后继：比根节点大的最小结点，通过递归遍历根节点右子树的左子树直至叶子结点，即为根节点的后继
实际上前驱和后继是按照中序遍历后，该节点在中序序列前后的两个结点。
struct node
{
int data;
node *l,*r;
node()
{
l=NULL;
r=NULL;
}
}
node* search(node *root,int key);
//寻找前驱结点
int findpre(node *root)
{
if(root->r)
{
return findpre(root->r);
}else{
int k=root->data;
root=root->l;
return k;
}
}
//寻找后继节点
int findpost(node *root)
{
if(root->l)
{
return findpost(root->l);
}else{
int k=root->data;
root=root->r;
return k;
}
}
//删除操作(有点问题，暂时忽略)
void del(node *root,int key)
{
node *d=search(root,key);//找到要删除的结点
if(!d)//如果没找到要删除的结点
return ;
if(!d->r&&!d->l)//如果左右子树都为空，直接修改为NULL
{
d=NULL;
}else if(root->r)
{
root->data=findpre(root->l)
}else {
root->data=findpost(root->r);
}
}
二叉平衡树
在二叉查找树的基础上，每次插入元素是控制树的高度，使其仍能保持**O(logn)**的级别。
因此，平衡二叉树满足二叉查找树的性质，但是在其基础上增加了维护操作。
对于任意结点来说 AVL 树的左右子树高度差不超过1（高度差称为平衡因子），维护平衡因子不大于 1 的过程就是在维护平衡二叉树。
名词解释
平衡因子
平衡因子就是左右子树的高度差。
任意结点的平衡因子不能实时记录，只能通过记录树的高度然后动态计算，所以在结构体中需要增加一个 h 作为存储树高。
因为平衡二叉树的性质，因此当从叶子结点向上更新时，第一次出现失衡结点（平衡因子）后，其后计算的所有结点都是失衡的，此时需要调整最下方（距离插入结点最近的）失衡节点到平衡状态，即可保证整棵树的合法。
树形
当出现失衡结点时，以失衡结点为根节点，树有4种不同形态，分为LL、LR、RR、RL四种形态，对应了四种不同的维护方式。
这四种代号分别代表从失衡节点到深度最深的子树的遍历路径的前两次选择。
- LL型：失衡结点左子树的左子树最深，可以通过一次右旋达到平衡
- LR型：失衡结点左子树的右子树最深，先对左子树左旋形成LL，再进行右旋
- RR型：失衡结点右子树的右子树最深，可以通过一次左旋达到平衡
- RL型：失衡结点右子树的左子树最深，先对右子树右旋形成RR，再进行左旋
基本操作
- 平衡因子及高度的维护
- 左旋
- 右旋
- 树形的判断
- 平衡因子的维护
- 插入
- 建树
平衡因子及高度
平衡因子是根节点左右子树高度的差值，在插入新节点后会改变子树的高度，因此要对其进行维护。
int get_h(node *root)//该函数的意义是防止指针的越界访问
{
if(root) return root->h;//如果结点不为空返回树的高度
else return 0;
}
int get_bal(node *root)//计算平衡因子，需要通过get_h()函数，因为可能结点为空，所以需要判断
{
return get_h(root->l)-get_h(root->r);
}
void updata_h(node *root)//更新当前结点的高度
{
root->h=max(get_h(root->l),get_h(root->r))+1;
//不能直接使用指针调用左右子树的h，当root=NULL时可能会引起非法操作
}
左旋
某一结点n1,与其右子树的根节点n2，在左旋操作后n2成为新的根节点，此时：n2的左孩子为n1、右孩子不变；n1的左孩子不变，右孩子为原n2的左孩子。
整个过程实际上是两个结点进行了变化：
- n1的右孩子 -> 变为了n2的左孩子
- n2的左孩子 -> 变为了n1
//以下是主函数中的调用，结点旋转后返回新的根节点
root=turn_left(root);
//左旋函数
node *turn_left(node *root)
{
node *t=root->r;//找到n3结点
root->r=t->l;//n1的右孩子变成n2的左孩子
t->l=root;//n2的左孩子变成n1
//以下是更新两个结点的高度
updata_h(root);
updata_h(t);
return t;
}
在旋转之后进行了更新，需要注意，先更新n1（即代码中的root）再更新n2（即t），因为此时t是root的父亲节点，root更新后才是正确的高度。
为什么更新是正确的？
因为树的高度是从下向上计算的，修改一个结点只会影响这个结点之上的高度，这个结点的子树高度是不变的，这一点在看过插入部分后会更加明了。
右旋
与左旋是互逆操作。
某一结点n1与其左子树根节点n2，在右旋操作后n2成为新的根节点，此时：n2的左孩子不变，右孩子为n1；n1的左孩子为原n2的右孩子，n1的右孩子不变。
整个过程实际上是两个结点进行了变化：
- n1的左孩子 -> 变为了n2的右孩子
- n2的右孩子 -> 变为了n1
//以下是主函数中的调用，结点旋转后返回新的根节点
root=turn_right(root);
//右旋函数
node *turn_right(node *root)
{
node *t=root->l;//找到n2
root->l=t->r;//n1的左孩子变为n2的右孩子
t->r=root;//n2的右孩子变为n1
//以下是更新两个结点的高度
updata_h(root);
updata_h(t);
return t;
}
树形的判断
树形的LL、LR、RR、RL等等实际上是指的从失衡结点开始左右子树哪个高度更高，我们规定,get_bal()函数是左子树的高度减去右子树高度，因此可以通过失衡结点的正负来判断树形。
显然：
如果得到的平衡因子为正数，说明左子树高于右子树，如果得到的平衡因子为负数，说明左子树低于右子树。
总的来说：
- 当失衡结点的平衡因子为2，则左孩子的高度更高，第一个字母为L
- 计算左孩子的平衡因子，如果为1，则说明左孩子的左子树高于右子树，为LL，否则为LR
- 当失衡结点的平衡因子为-2，则右孩子的高度更高，第一个字母为R
- 计算右孩子的平衡因子，如果为1，则说明左孩子的左子树高于右子树，为RL，否则为RR
注意，失衡结点的左右孩子的平衡因子不会出现0或±2。
平衡因子的维护
当我们完成一个插入或者旋转操作后需要对平衡因子（树高）进行更新。
由于采用的是递归的方式进行插入，因此在维护的时候，可以在找到结点并插入后，边回溯边更新高度并检查平衡因子直到失衡结点或者根结点为止。
这样做的合理性在左旋部分有所提及，因为树高是从下向上计算的，所以对于所有变化的结点，它的子树高度是不改变的，改变的只是从这个结点之上的所有结点。
因此每次出现插入（旋转）操作后我们都需要更新这个结点与其父节点及所有祖先结点。
我们插入一个元素，会使用递归从上向下寻找合适的位置进行插入，因此，插入结束后回溯的同时更新平衡因子即可。
插入
插入操作根据二叉查找树的定义进行插入，然后需要从插入的结点向上回溯直至失衡结点或根节点
在插入时需要结合上述几点，进行
判断树形->更新平衡因子->寻找失衡结点->旋转
的大致过程（如果没有失衡结点也就不需要进行旋转了）。
注意下面给出的示例代码，其中平衡因子的判断部分：
当新节点向左子树插入时只判断了是否为2，并没有判断-2，这是因为2代表LR或LL型，向左插入只会增加左子树的高度，所以一定是L( )型；向右子树插入的时候同理.
node *insert(ndoe* root,int key)
{
if(!root)//如果合适的位置是一个空节点，那么直接插入就好了
{
root=new node;
root->data=key;
root->h=1;//初始化树高为1；
root->l=NULL;
root->r=NULL;
return root;
}else if(key<root->data)//递归寻找的过程
{
root->l=insert(root->l,key);
/* 以下是插入后对树高的更新、树形的判断 */
updata_h(root);//首先更新结点高度
if(get_bal(root)==2)//判断平衡因子,并进行旋转
{
if(get_bal(root->l)==1)
{
root=turn_right(root);
}else if(get_bal(root->l)==-1){
root->l=turn_left(root->l);
root=turn_right(root);
}
}
}else {
root->r=insert(root->r,key);
updata_h(root);
/* 以下是插入后对树高的更新、树形的判断 */
if(get_bal(root)==-2)
{
if(get_bal(root->r)==-1)
{
root=turn_left(root);
}else if(get_bal(root->r==1)){
root->r=turn_right(root->r);
root=turn_left(root);
}
}
}
}
其中判断树形的部分我们也可以写成switch的形式，下面以L( )型为例：
switch(get_bal(root->l))
{
case -1:root->l=turn_left(root->l);//利用switch特性，减少代码行数
case 1;root=turn_right(root);
}
建树
建树和BST树一样，由于维护操作都写在insert函数中，建树只需要循环读入就可以
node *root;
for(int i=0;i<n;i++)
{
cin>>a[i];
root=insert(root,a[i]);
}
评论