[SinGuLaRiTy] 平衡树

【SinGuLaRiTy-1009】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.

二叉查找树

二叉查找树是指具有下列性质的非空二叉树：

⑴若根结点的左子树不空，则左子树的所有结点值均小于根结点值；

⑵若根结点的右子树不空，则右子树的所有结点值均不小于根结点值；

⑶根结的左右树也分别为二叉排序树；

显然，对二叉排序树进行中序遍历，可得出结点值递增的排序序列。

eg. 下图即是一棵二叉查找树：

其中序遍历为8，11，23，39，46，68，71，75

建树代码

const int MAXN = ;
struct node {
    int data;        //关键字
    int lch, rch;    // 左、右子指针
};
node bst[MAXN];    // 二叉查找树
int n;
void init()            // 读入数据
{
    int i,t,r=;
    cin >> n;
    for (i=; i<=n; i++)
          {cin>>t;
                  insert(r,t);//将t插入r为根的树中。
                }
}

插入操作

void insert(int &root,int t)
{
   if(root==)
      {bst[cnt++].data=t;
       root=cnt;
      return;
      }
if(t<bst[root].data)
 insert(bst[root].lch,t);
else if(t>bst[root].data)
 insert(bst[root].rch,t);
}

查找操作

二叉查找数的查找操作：find

int find(int root,int x)
{
    if(x==bst[root].data)return root;
    if(root==)return -;
    if(x>bst[root].data)
     return find(bst[root].rch,x);
    else
     return find(bst[root].lch,x);
}

找到该节点，则返回该节点下标;否则返回-1.

删除操作

如果找到该节点，则将该节点删除；如果没有找到，则不做任何事情。

删除操作有些复杂，我们先来分析一下： 如果删除的节点是叶子节点，则直接删除即可。

如果删除的节点只有左儿子或只有右儿子，直接删除，并将该节点的父亲和儿子连接起来，类似于链表的删除。

那么如果删除的节点有左右儿子，该如何处理？这时可以设该节点为x。在x的左子树里边找到最大的节点t, 执行：bst[x].data=bst[t].data; 并将t删除。

void delete(int &root,int vx)
{
   if(root==)return;
   if(bst[root].data>vx)
      delete(bst[root].lc,vx);
   else if(bst[root].data<vx)
     delete(bst[root].rc,vx);
   else
    {
        if(bst[root].lch==||bst[root].rch==)
        root=bst[root].lch+bst[root].rch;
        else
       {
         int t=bst[root].lch;
         int f=root;
           while(t.rch)
             {
                f=t;
                t=bst[t].rch;
             }
             bst[root].data=bst[t].data;
            if(f==root)bst[f].lch=bst[t].lch;
             else bst[f].rch=bst[t].lch;
        }   }}

惰性删除

其实删除操作完全可以粗略地处理。即只将要删除的节点打上标记，并不真正删除。这样的话，简便很多。而在效率上影响不大：如果删除节点很少，完全不会有影响；删除节点即使很多，也不会增加时间复杂度，只是常数上增加而已。

可以看出，在理想情况下，二叉查找数的insert，find，delete等操作的时间复杂度都是O(logN)。但是，如果树退化称为一条链，则insert,find,delete等操作的时间复杂度就是O(N)了。

为了使得在最差情况下，二叉查找数的各项操作也能达到O(logN)的时间复杂度，我们可以将树做一些改进，于是，就有了下面要讲的AVL(平衡树).

平衡树

定义

平衡树（Balanced Tree）：高度为O(logn)的树。

平衡二叉树（Balanced Binary Tree）：由阿德尔森一维尔斯和兰迪斯（Adelson-Velskii and Landis）于1962年首先提出的，所以又称为AVL树。

如果T是一棵非空的二叉搜索树，TL和TR分别是其左子树和右子树，那么当T满足以下条件时，T是一棵AVL树：

1）TL和TR 是AVL树；

2）|hL-hR|≤1，hL和hR分别是左子树和右子树的高度

（空二叉树也是是AVL树）

高度平衡的二叉搜索树

高度不平衡的二叉搜索树

AVL树必须具备的特征

n个元素的AVL树的高度是O(logn)；

一棵n元素的AVL搜索树能在O(高度)=O(logn) 的时间内完成搜索；

将一个新元素插入到一棵n元素的AVL搜索树中，可得到一棵n+1元素的AVL树，这种插入过程可以在O(logn)时间内完成；

从一棵n元素的AVL搜索树中删除一个元素，可得到一棵n-1元素的AVL树，这种删除过程可以在O(logn)时间内完成。

AVL树的高度

假设Nh是一棵高度为h的AVL树中最小的节点数

可以看到Nh的定义与斐波那契数列的定义非常相似

AVL树的平衡因子

为每个节点增加一个平衡因子bf。节点x 的平衡因子bf (x)定义为：bf (x)= hL-hR 。 即：x的左子树的高度-x 的右子树的高度。

从AVL树的定义可以知道，平衡因子的可能取值为-1、0、1。

如果树中任意一个结点的平衡因子的绝对值大于 1，则这棵二叉树就失去平衡。

AVL树的搜索

如果一棵AVL树有n个节点，其高度可以保持在O(logn)，因此平均搜索长度也可以保持在O(logn)。

二叉搜索树的算法完全适用于AVL树。

AVL树的插入

若一棵二叉搜索树是平衡二叉树，插入某个节点后，可能会变成非平衡二叉树，而且只可能是该节点到根的路径上的节点不平衡了。我们可以通过修正来使它恢复平衡，这中操作就是”旋转“。

如下图所示：

我们插入了一个节点后，从该节点向上搜索，找到第一个不平衡的节点，对它进行调整即可。可以预见，调整了该节点过后，所有节点都将达到平衡状态。

让我们把必须重新平衡的节点叫做α。当不平衡时，左右子树的高度差为2.

这种不平衡可能出现在下面四种情况中：

1.对α的左儿子的左子树进行了一次插入

2.对α的左儿子的右子树进行了一次插入

3.对α的右儿子的左子树进行了一次插入

4.对α的右儿子的右子树进行了一次插入

情形1和4是关于α点的镜像对称，而2和3是关于α点的镜像对称。因此，理论上只有两种情况:

第一种情况是发生在“外边”的情况，即左-左的情况或右-右的情况，该情况可以通过对树的一次单旋转而完成调整。

第二种情况是插入发生在“内部”的情况，即（左-右的情况或右-左的情况），该情况通过稍微复杂些的双旋转来处理。

旋转

平衡化旋转有两类：

单旋转（zig—右旋或zag—左旋）

双旋转（zagzig或zigzag旋转）

如果这三个节点处于一条直线上，则采用单旋转进行平衡化。 如果这三个节点处于一条折线上，则采用双旋转进行平衡化。

zig右旋

若在 C 的左子树的左子树上插入 结点，使 C 的平衡因子从 1 增加 至 2， 需要进行一次顺时针旋转。 (以 B 为旋转轴）

zag左旋

若在 A 的右子树的右子树上插入 结点，使 A 的平衡因子从 -1 改变 为 -2，需要进行一次逆时针旋转。(以 B 为旋转轴）

zagzig 双旋转

若在 C 的左子树的右子树上插入 结点，使 C 的平衡因子从 1 增加 至 2， 需要先进行逆时针旋转， 再顺时针旋转。 (以插入的结点 B 为旋转轴）

zagzig 双旋转

若在 A 的右子树的左子树上插入 结点，使 A 的平衡因子从 -1 改变 为 -2，需要先进行顺时针旋转，再逆时针旋转。 (以插入的结点 B 为旋转轴）

注意：调整必须保证二叉排序树的特性不变

zig：新插入节点在不平衡节点的左子树的左子树中；

zag：新插入节点在不平衡节点的右子树的右子树中；

zigzag：新插入节点在不平衡节点的左子树的右子树中；

zagzig：新插入节点在不平衡节点的右子树的左子树中。

zig旋转：右旋——顺时针

在左子树D上插入新节点使其高度增1，导致节点A的平衡因子增到 2，造成了不平衡。

为使树恢复平衡，从A沿插入路径连续取3个节点A、B和D，它们处于一条方向为“/”的直线上，需要做LL旋转。

以节点B为旋转轴，将节点A顺时针旋转成为B的右孩子，B代替原来A的位置，原来B的右孩子E转为A的左孩子。

zig旋转的算法

int zig(int r)//右旋
{
    int t=tree[r].lc;
    tree[r].lc=tree[t].rc;
    tree[t].rc=r;
    tree[r].h=max(tree[tree[r].rc].h,tree[tree[r].lc].h)+;
    tree[t].h=max(tree[tree[t].rc].h,tree[tree[t].lc].h)+;
    return t;
}
//注：假设r一定存在左儿子，右旋过后，t成为根节点。

zag旋转：逆时针

在右子树E中插入一个新节点，该子树高度增1导致节点A的平衡因子变成-2，出现不平衡。

沿插入路径检查三个节点A、C和E。它们处于一条方向为“\”的直线上，需要做zag旋转。

以节点C为旋转轴，让节点A反时针旋转成为C的左孩子，C代替原来A的位置，原来C的左孩子D转为A的右孩子。

左单旋转的算法

int zag(int r) //左旋
{
    int t=tree[r].rc;
    tree[r].rc=tree[t].lc;
    tree[t].lc=r;
    tree[r].h=max(tree[tree[r].rc].h,tree[tree[r].lc].h)+;
    tree[t].h=max(tree[tree[t].rc].h,tree[tree[t].lc].h)+;
    return t;
}
//注：r必存在右儿子。    

zagzig旋转：先左后右双旋转

在子树F或G中插入新节点，该子树的高度增1。节点A的平衡因子变为 2，发生了不平衡。

从节点A起沿插入路径选取3个节点A、B和E，它们位于一条形如“”的折线上，因此需要进行先左后右的双旋转。

首先以节点E为旋转轴，将节点B逆时针旋转，以E代替原来B的位置，做zag旋转。

再以节点E为旋转轴，将节点A顺时针旋转，做zig旋转，使之平衡化。

zagzig旋转的算法

int zagzig(int r) //左子树双旋
{
   tree[r].lc=zag(tree[r].lc);
   return zig(r);
}   

zigzag旋转：先右后左双旋转

右左双旋转是左右双旋转的镜像。

在子树F或G中插入新节点，该子树高度增1。节点A的平衡因子变为-2，发生了不平衡。

从节点A起沿插入路径选取3个节点A、C和D，它们位于一条形如“>”的折线上，需要进行先右后左的双旋转。

首先做LL旋转：以节点D为旋转轴，将节点C顺时针旋转，以D代替原来C的位置。

再做RR旋转：以节点D为旋转轴，将节点A反时针旋转，恢复树的平衡。

zigzag旋转的算法

int zigzag(int r)//右子树双旋两次
{
    tree[r].rc=zig(tree[r].rc);
    return zag(r);
}

建立一棵AVL树

从一棵空树开始，通过输入一系列对象的关键值，逐步建立AVL树，在插入新节点时使用前面所给的算法进行平衡旋转。

例：输入关键值序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，构造一棵AVL树

插入操作代码

int insert(int x,int r)
{
  if(r==)//到了叶子节点，
  {
      tree[++cnt].v=x;
      tree[cnt].h=;
      return cnt;
  }

  if(x<tree[r].v)//情况1或情况2
  {
       tree[r].lc=insert(x,tree[r].lc);
      if(tree[tree[r].lc].h==tree[tree[r].rc].h+)
      {
          if(x<tree[tree[r].lc].v)r=zig(r);//情况1
          else if(x>tree[tree[r].lc].v)r=zagzig(r);//情况2
      }
  }
  else if(x>tree[r].v)//情况3或情况4
  {
      tree[r].rc=insert(x,tree[r].rc);
     if(tree[tree[r].rc].h==tree[tree[r].lc].h+)
     {
         if(x>tree[tree[r].rc].v) r=zag(r);//情况4
         else if(x<tree[tree[r].rc].v)r=zigzag(r);//情况3
     }
  }
   tree[r].h=max(tree[tree[r].lc].h,tree[tree[r].rc].h)+;
  return r;
}

AVL树的删除操作

删除操作类似于普通二叉查找数的删除，不同的是删除过后要调整。

情况1：如果当前节点是叶子节点，直接删除

情况2: 如果当前节点只有一个儿子，则将儿子与父亲连接起来，类似于链表中删除一个节点。

情况3：如果当前节点有左右儿子，则从左儿子中取出最大的节点x，用它的值来替换掉要删除的节点，然后删除节点x。

从删除的节点开始（情况3从x开始，往上调整，直到根节点）。

删除代码

int dele(int &r,int x)//在r的子树中删除x，注意，如果没有x，则将小于x的最大的那个删除
{int tx;
    if(x==tree[r].v||(x<tree[r].v&&tree[r].lc==)||(x>tree[r].v&&tree[r].rc==))
    {if(tree[r].lc==||tree[r].rc==)
       {
           tx=tree[r].v;
           r=tree[r].lc+tree[r].rc;
           return tx;
       }
       else
           tree[r].v=dele(tree[r].lc,x); }
    else
    {
       if(x<tree[r].v)
            tx=dele(tree[r].lc,x);
        else tx=dele(tree[r].rc,x);
    }
 maintain(r);
return tx;
}

调整

void maintain(int &r) //对r为根的子树进行调整
{
   if(tree[tree[r].lc].h==tree[tree[r].rc].h+)
    {
        int t=tree[r].lc;
        if(tree[tree[t].lc].h==tree[tree[r].rc].h+)
        {
           r=zig(r);
        }
        else if(tree[tree[t].rc].h==tree[tree[r].rc].h+)
        {
            tree[r].lc=zag(tree[r].lc);
            r=zig(r);
        }
    }
    else  if(tree[tree[r].lc].h+==tree[tree[r].rc].h)
    {
       int t=tree[r].rc;
        if(tree[tree[t].rc].h==tree[tree[r].lc].h+)
            r=zag(r);
        else if(tree[tree[t].lc].h==tree[tree[r].lc].h+)
        {
            tree[r].rc=zig(tree[r].rc);
            r=zag(r);
        }
    }
    tree[r].h=max(tree[tree[r].lc].h,tree[tree[r].rc].h)+;
}

在main函数中，调用dele(r,x),一定要保证x在子树中，所以可以用先find(r,x),返回真才调用dele(r,x)

int main()
{
   if(find(r,x))
    dele(r,x);
}

平均搜索长度（ASL）——衡量搜索算法效率的标准

指在数据表中搜索各数据元素所需进行的关键码的比较次数的期望值。

对于具有n个数据元素的数据表，搜索某数据元素成功时的平均搜索长度为：

Pi表示第i个数据元素被搜索的概率，Ci表示搜索第i个数据元素所需要进行关键码的比较次数。

Time ：2017-03-22