AVL实现

Coco_young

浏览: 125310 次
性别:
来自: 湖南长沙

最近访客更多访客>>

yzmduncan

jacket233

进击的老人

aspnetwxw

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

avl 数据结构 bst

一. AVL概念：
    对于一颗BST，其中每个节点的左右子树高度差均不超过1的平衡二叉搜索树，就叫做AVL树。
二. 如何维护一颗AVL树。
    旋转操作：
    1. rotateWithLeft:(右旋转)
*       (N)                (L)
*      /   \              /   \
*    (L)    3    ==>     1    (N)
*   /   \                    /   \
* 1     2                  2     3
    2. rotateWithRight:(左旋转)
*    (N)                (R)
*   /   \              /   \
* 1    (R)    ==>   (N)    3
*      /   \        /   \
*     2     3      1     2

三.AVL的基本操作:

   Find(x,AVL);//在AVL树中查找值为X的元素
   Insert(x,&AVL);//在AVL树中插入值为X的元素
   Remove(x,&AVL);//在AVL树中删除值为X的元素
   FindMax(AVL);//查找AVL树中的最大值
   FindMin(AVL);//查找AVL树中的最小值
   rotateWithLeft(&node);//右旋
   rotateWithRight(&node)//左旋

四.AVL的静态实现:
1.用到的数据结构:int left[],right[],next[],height[],data[].
2.说明: left,right分别保存节点的左子结点和右子结点,0表示空，height保存某一结点的   高度，用来计算平衡因子,data保存结点的数据.
3.实现分析:
    （1）.FindMax,Find,FindMin,和BST的一样。
    （2）.Insert,将元素插入AVL树后，沿插入路径逆向，从插入位置开始，遇到第一个不平衡的结点就将该子树旋转至平衡，如此操作，整棵AVL都达到平衡。
    （3）.Remove,先仿造BST的删除方式进行删除,从删除位置沿删除路径返回根节点，只要遇到不平衡的结点就旋转.
    （4）.旋转操作，不平衡的点一定有孙子，祖父与孙子共线: 单旋转；祖父与孙子不共线: 双旋转。(图来自刘汝佳的书《高级数据结构》)
     单旋转：

双旋转：

五.实现代码:

   #include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define SIZE 100
#define MAX(a,b) a>b?a:b
/**
** author: yfr
** date: 2012-1-9
** project: AVL tree
** reference: LRJ's BOOK
** 用数组模拟链式结构（姑且用静态这个说法）,实现AVL的插入操作 
** 这里不直接用平衡因子，而是保持树各结点的高度，然后去计算平衡因子 
** 空树的高度是-1 
**/
int Left[SIZE],Right[SIZE],next[SIZE],data[SIZE],height[SIZE];
/*辅助容器*/
vector<int> look[SIZE];
int depth[SIZE];
/**/
/**
所有操作申明 
**/
void Init();
int makenode(int x);
void delnode(int);
int find(int x,int p);
int findmin(int);
int findmax(int);
void insert(int x,int &p);
void remove(int x,int &p);

//初始化各数组
void Init()
{
   memset(Left,0,sizeof(Left));
   memset(Right,0,sizeof(Right));
   memset(height,-1,sizeof(height));//空树高度为-1 
   for(int i=0;i<SIZE;i++)
   next[i] = i+1;
}
//模拟内存分配函数  
int makenode(int x)
{
    int p = next[0];
    next[0] = next[p];
    data[p] = x;
    return p;
}
void delnode(int p)
{
    Left[p] = Right[p] = 0;
    height[p] = -1;
    next[p] = next[0];
    next[0] = p;
}
//AVL的操作函数
/*旋转
         a                           b
          \                         / \
           b    ------------>      a   c
          / \                     /
         d   c                   d 
*/
void rotateWithRight(int &p)
{
     int q = Right[p];
     Right[p] = Left[q];
     Left[q] = p;
     height[p] = MAX(height[Left[p]],height[Right[p]])+1;
     height[q] = MAX(height[Right[q]],height[p])+1;
     p = q;//
} 
/*旋转
         a                           b
        /                           / \
       b      ------------->       c   a
      / \                             /
     c   d                           d  
*/
void rotateWithLeft(int &p)
{
    int q = Left[p];
    Left[p] = Right[q];
    Right[q] = p;
    height[p] = MAX(height[Left[p]],height[Right[p]])+1;
    height[q] = MAX(height[Left[q]],height[p])+1;
    p = q;
}
void insert(int x,int &p)
{
    if(!p)
    {
       p = makenode(x);
       height[p] = MAX(height[Left[p]],height[Right[p]])+1;
       return;
    }
    if(x < data[p])
    {
       insert(x,Left[p]);
       height[p] = MAX(height[Left[p]],height[Right[p]])+1;
       if(height[Left[p]]-height[Right[p]]==2)//不平衡 
       {
           if(height[Left[Left[p]]]-height[Right[Left[p]]]==1)//LL
           {
               rotateWithLeft(p);
           }
           else if(height[Left[Left[p]]]-height[Right[Left[p]]]==-1)//LR
           {
               rotateWithRight(Left[p]);
               rotateWithLeft(p);
           }
       }
    }
    else 
    {
       insert(x,Right[p]);
       height[p] = MAX(height[Left[p]],height[Right[p]])+1;
       if(height[Left[p]]-height[Right[p]]==-2)//不平衡
       {
           if(height[Left[Right[p]]]-height[Right[Right[p]]]==1)//RL
           {
               rotateWithLeft(Right[p]);
               rotateWithRight(p);
           }
           else if(height[Left[Right[p]]]-height[Right[Right[p]]]==-1)//RR
           {
               rotateWithRight(p);
           }
       } 
    }
}
//从AVL树中删除节点 
//先删除，再调整树形 
void remove(int x,int &p)
{
     if(!p) return;//如果是空树，返回
     if(x < data[p]){
          remove(x,Left[p]);
     }
     else if(x > data[p]){
          remove(x,Right[p]);
     }
     else//如果已经找到该结点 
     {
         if(Left[p]&&Right[p])//如果左右结点非空
         {
             int q = findmin(Right[p]);
             data[p] = data[q];
             remove(data[p],Right[p]);
         }
         else
         {
             int q = p;
             p = Left[p]?Right[p]:Left[p]; 
             delnode(q);//释放该结点 
             return;//删除处的高度不需要调整 
         } 
     } 
     if(p){//如果不是空树的话 
       height[p] = MAX(height[Left[p]],height[Right[p]])+1;//记录高度
       //不平衡则旋转 
       if(height[Left[p]]-height[Right[p]]==2)//L
       {
          if(height[Left[Left[p]]]-height[Right[Left[p]]]>=0)//L
          {
             rotateWithLeft(p);//LL旋转 
          }
          else//R 
          {
          //LR旋转 
             rotateWithRight(Left[p]);
             rotateWithLeft(p);
          }
       }
       else if(height[Left[p]]-height[Right[p]]==-2)//R
       {
          if(height[Left[Right[p]]]-height[Right[Right[p]]]<=0)//RR
          {
             rotateWithRight(p);
          }
          else
          {
             //RL
             rotateWithLeft(Right[p]);
             rotateWithRight(p);    
          }
       } 
     }
}
int find(int x,int p)
{
    if(!p)return 0;
    if(x == data[p]) return p;
    if(x < data[p]) return find(x,Left[p]);
    if(x > data[p]) return find(x,Right[p]);
}
int findmin(int p)
{
    if(!p)return 0;//空树
    if(!Left[p]) return p;
    else return findmin(Left[p]); 
}
int findmax(int p)
{
    if(p)
    while(Right[p]) p = Right[p];
    return p;
}
/*********************
辅助函数 
**********************/
//标记好各结点的层数，查看树形时要用到 
void dfs(int p,int deep)
{
   if(!p)return;
   depth[p] = deep;
   dfs(Left[p],deep+1);
   dfs(Right[p],deep+1);
}
void order(int p)
{
   if(!p)return;
   order(Left[p]);
   cout<<data[p]<<endl;
   order(Right[p]);
}
//查看树形 
void bfs(int p)
{
   dfs(p,0);
   queue<int> q;
   q.push(p);
   while(!q.empty())
   {
      int v = q.front();
      q.pop();
      if(Left[v])q.push(Left[v]);
      if(Right[v])q.push(Right[v]);
      cout<<data[v]<<endl;
      look[depth[v]].push_back(data[v]);
   }
}
void print_tree(int deep)
{
     for(int i=0;i<=deep;i++)
     {
        for(int j=0;j<look[i].size();j++)
        {
           cout<<look[i][j];
           for(int k=0;k<=deep-i;k++)
           cout<<" ";
        }
        cout<<endl;
     }
}
int main()
{
    freopen("dataout.txt","w",stdout);
    Init();
    int ROOT = 0;
    insert(10,ROOT);//build AVLtree
    insert(11,ROOT);
    insert(12,ROOT);
    insert(13,ROOT);
    insert(14,ROOT);
    remove(10,ROOT);
    bfs(ROOT);
    print_tree(height[ROOT]);
    return 0;
}