AVL树

维基百科，自由的百科全书

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。

节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

目录 1 操作 1.1 插入 1.2 删除 1.3 查找 2 参考实现 3 参见 4 引用 5 外部链接

[编辑] 操作

AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运做的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL 旋转"。

假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a(即a是离插入点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行进行的规律可归纳为下列四种情况：

1. 单向右旋平衡处理RR：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；
2. 单向左旋平衡处理LL：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；
3. 双向旋转（先左后右）平衡处理LR：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
4. 双向旋转（先右后左）平衡处理RL：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

[编辑] 插入

向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次 AVL 旋转都耗费恒定的时间，插入处理在整体上耗费 O(log n) 时间。

在平衡的的二叉排序树Balanced BST上插入一个新的数据元素e的递归算法可描述如下：

1. 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1；
2. 若e的关键字和BBST的根结点的关键字相等，则不进行；
3. 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加(+1)时，分别就下列不同情况处理之：
   1. BBST的根结点的平衡因子为-1(右子树的浓度大于左子树的深度，则将根结点的平衡因子更改为0，BBST的深度不变；
   2. BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1；
   3. BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；
4. 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加(+1)时，分别就不同情况处理之。

[编辑] 删除

从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转，而每次 AVL 旋转耗费恒定的时间，删除处理在整体上耗费 O(log n) 时间。

[编辑] 查找

在AVL树中查找同在一般BST完全一样的进行，所以耗费 O(log n) 时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查询而改变。(这是与伸展樹查找相对立的，它会因为查找而变更树结构。)

[编辑] 参考实现

给出一个操作AVLTREE的完整程序 大部分由Peter Brass编写

 #include <iostream.h>
 #include <math.h>
 #include <stdlib.h>
 
 //建立一个整数类型
 typedef struct obj_n_t
 {
  int obj_key;
 } obj_node_t;
 
 
 //建立树结点的基本机构
 typedef struct tree_n_t 
 {
  int key;
  struct tree_n_t *left,*right;
  int height;
 } tree_node_t;
 
 
 //建立堆栈
 #define MAXSIZE 512
 tree_node_t *stack[MAXSIZE]; //warning!the tree can contain 256 leaves at most!
 
 int i=0; //堆栈计数器
 
 //堆栈清空
 void stack_clear()
 {
  while(i!=0)
  {
   stack[i-1]=NULL;
   i--;
  }
 
 }
 //堆栈为空
 int stack_empty()
 {
  return(i==0);
 }
 
 //入栈函数
 int push(tree_node_t *node)
 {
  if(i<MAXSIZE)
  {
   stack[i++]=node;
   return(0);
  }
  else
   return(-1);
 }
 
 //出栈函数
 tree_node_t *pop()
 {
  if(i>0)
   return(stack[--i]);
  else
   return(0);
 }
 
 //建立get_node函数，用于动态分配内存空间
 
 tree_node_t *get_node()
 {
  tree_node_t *tmp;
  tmp=(tree_node_t *)malloc(sizeof(tree_node_t));
  return(tmp);
 }
 
 //建立return_node函数，用于释放内存
 void return_node(tree_node_t *free_node)
 {
  free(free_node);
 }
 
 //建立左旋转函数
 void left_rotation(tree_node_t *node)
 {
  tree_node_t *tmp;
  int tmp_key;
  tmp=node->left;
  tmp_key=node->key;
  node->left=node->right;
  node->key=node->right->key;
  node->right=node->left->right;
  node->left->right=node->left->left;
  node->left->left=tmp;
  node->left->key=tmp_key;
 }
 
 //建立右旋转函数
 void right_rotation(tree_node_t *node)
 {
  tree_node_t *tmp;
  int tmp_key;
  tmp=node->right;
  tmp_key=node->key;
  node->right=node->left;
  node->key=node->left->key;
  node->left=node->right->left;
  node->right->left=node->right->right;
  node->right->right=tmp;
  node->right->key=tmp_key;
 }
 
 int rebalance(tree_node_t *node)
 {
  int finished=0;
  while(!stack_empty()&&!finished)
  {
   int tmp_height,old_height;
   node=pop();                     //back to the root along the search path
   old_height=node->height;
   if(node->left->height-node->right->height==2)
   {
    if(node->left->left->height-node->right->height==1)
    {
     right_rotation(node);
     node->right->height=node->right->left->height+1;
     node->height=node->right->height+1;
    }
    else
    {
     left_rotation(node->left);
     right_rotation(node);
     tmp_height=node->left->left->height;
     node->left->height=tmp_height+1;
     node->right->height=tmp_height+1;
     node->height=tmp_height+2;
    }
   }
   else if(node->left->height-node->right->height==-2)
   {
    if(node->right->right->height-node->left->height==1)
    {
     left_rotation(node);
     node->left->height=node->left->right->height+1;
     node->height=node->left->height+1;
    }
    else
    {
     right_rotation(node->right);
     left_rotation(node);
     tmp_height=node->right->right->height;
     node->left->height=tmp_height+1;
     node->right->height=tmp_height+1;
     node->height=tmp_height+2;
    }
   }
   else
   {
    if(node->left->height>node->right->height)
     node->height=node->left->height+1;
    else
     node->height=node->right->height+1;
   }
   if(node->height==old_height)
    finished=1;
  }
 
  stack_clear();
  return(0);
 }
 
 
 //建立creat_tree函数，用于建立一颗空树
 tree_node_t *creat_tree()
 {
  tree_node_t *root;
  root=get_node();
  root->left=root->right=NULL;
  root->height=0;
  return(root);         //build up an empty tree.the first insert bases on the empty tree.
 }

 //建立find函数，用于查找一个对象
 obj_node_t *find(tree_node_t *tree,int query_key)
 {
  tree_node_t *tmp;
  if(tree->left==NULL)
   return(NULL);
  else
  {
   tmp=tree;
    while(tmp->right!=NULL)
    {
     if(query_key<tmp->key)
      tmp=tmp->left;
     else
      tmp=tmp->right;
    }
    if(tmp->key==query_key)
     return((obj_node_t*)tmp->left);
    else
     return(NULL);
  }
 }
 
 //建立插入函数
 int insert(tree_node_t *tree,obj_node_t *new_obj)
 {
  tree_node_t *tmp;
  int query_key,new_key;
  query_key=new_key=new_obj->obj_key;
 
  if(tree->left==NULL)
  {
   tree->left=(tree_node_t *)new_obj;
   tree->key=new_key;
   tree->height=0;
   tree->right=NULL;
  }
  else
  {
   stack_clear();
   tmp=tree;
   while(tmp->right!=NULL)
   {
 //use stack to remember the path from root to the position at which the new object should be inserted.
 //then after inserting,we can rebalance from the parrent node of the leaf which pointing to new object to the root node.
    push(tmp);  
    if(query_key<tmp->key)
     tmp=tmp->left;
    else
     tmp=tmp->right;
   }
   if(tmp->key==query_key)
    return(-1);
   else
   {
    tree_node_t *old_leaf,*new_leaf;
 //It must allocate 2 node space in memory.
 //One for the new one,another for the old one.
 //the previous node becomes the parrent of the new node.
 //when we delete a leaf,it will free two node memory spaces as well.
    old_leaf=get_node();
    old_leaf->left=tmp->left;
    old_leaf->key=tmp->key;
    old_leaf->right=NULL;
    old_leaf->height=0;
 
    new_leaf=get_node();
    new_leaf->left=(tree_node_t *)new_obj;
    new_leaf->key=new_key;
    new_leaf->right=NULL;
    new_leaf->height=0;
 
    if(tmp->key<new_key)
    {
     tmp->left=old_leaf;
     tmp->right=new_leaf;
     tmp->key=new_key;
    }
    else
    {
     tmp->left=new_leaf;
     tmp->right=old_leaf;
    }
    tmp->height=1;
   }
  
  
  }
  rebalance(tmp);
  return(0);
 
 }
 
 
 //建立删除函数
 int del(tree_node_t *tree,int key)
 {
  tree_node_t *tmp,*upper,*other;
  if(tree->left==NULL)
   return(-1);
  else if(tree->right==NULL)
  {
   if(tree->key==key)
   {
    tree->left=NULL;
    return(0);
   }
   else
    return(-1);
  }
  else
  {
   tmp=tree;
   stack_clear();
   while(tmp->right!=NULL)
   {
    upper=tmp;
    push(upper);
    if(key<tmp->key)
    {
     tmp=upper->left;
     other=upper->right;
    }
    else
    {
     tmp=upper->right;
     other=upper->left;
    }
   }
   if(tmp->key!=key)
    return(-1);
   else
   {
    upper->key=other->key;
    upper->left=other->left;
    upper->right=other->right;
    upper->height=upper->height-1;
    return_node(tmp);
    return_node(other);
    rebalance(pop());
    //here must pop,then rebalance can run from the parrent of upper,because upper has become a leaf.
    return(0);
   }
  }
 }
 
 
 //建立测试遍历函数
   int travel(tree_node_t *tree)
 {
  stack_clear();
  if(tree->left==NULL)
   push(tree);   
  else if(tree->left!=NULL)
  {
   int m=0;
   push(tree);
   while(i!=m)
   {
    if(stack[m]->left!=NULL && stack[m]->right!=NULL)
    {
     push(stack[m]->left);
     push(stack[m]->right);
     
    }
    m++;
   }
  }
  return(0);
 }
 
 //建立测试函数
 int test_structure(tree_node_t *tree)
 {
  travel(tree);
  int state=-1;
  while(!stack_empty())
  {
   --i;
   if(stack[i]->right==NULL && stack[i]->height==0)  //this statement is leaf,but also contains an empty tree
   state=0;
   else if(stack[i]->left!=NULL && stack[i]->right!=NULL)
   {
    if(abs(stack[i]->height-stack[i]->height)<=1)
     state=0;
    else
    {
     state=-1;
     stack_clear();
    }
   }
  }
  stack_clear();
  return(state);
 }
 
 //建立remove_tree函数
 int remove_tree(tree_node_t *tree)
 {
  travel(tree);
  if(stack_empty())
   return(-1);
  else
  {
   while(!stack_empty())
   {
    return_node(pop());
   }
   return(0);
  }
 }
 
 void main()
 {
  tree_node_t *atree=NULL;
  obj_node_t obj[256],*f; //MAXSIZE=n(number of leaf)+(n-1) number of node
  int n,j=0;
  cout<<"Now Let's start this program! There is no tree in memory.\n";
  int item;
  while(item!=0)
  {
   cout<<"\nRoot address = "<<atree<<"\n";
   cout<<"\n1.Create a tree\n";
   cout<<"\n2.Insert a int type object\n";
   cout<<"\n3.Test the structure of the tree\n";
   cout<<"\n4.Find a object\n";
   cout<<"\n5.Travel\n";
   cout<<"\n6.Delete a object\n";
   cout<<"\n7.Remove the Tree\n";
   cout<<"\n0.Exit\n";
   cout<<"\nPlease select:";
   cin>>item;
   cout<<"\n\n\n";
   switch(item)
   {
   case 1:
    {
     atree=creat_tree();
     cout<<"\nA new empty tree has been built up!\n";
     break;
    }
   case 2:
    {
     if(atree!=NULL)
     while(n!=3458)
     {
      cout<<"Please insert a new object.\nOnly one object every time(3458 is an end code) : ";
      cin>>n;
      if(n!=3458)
      {
      obj[j].obj_key=n;
      if(insert(atree,&obj[j])==0)
      {
      j++;
      cout<<"Integer "<<n<<" has been input!\n\n";
      }
      else
       cout<<"\n\nInsert failed!\n\n";
     
      }
     }
     else
      cout<<"\n\nNo tree in memory,insert Fail!\n\n";
     break;
    }
   case 3:
    {
     if(atree!=NULL)
     {
      n=test_structure(atree);
      if(n==-1)
       cout<<"\n\nIt's not a correct AVL tree.\n\n";
      if(n==0)
       cout<<"\n\nIt's a AVL tree\n\n";
     }
     else
      cout<<"\n\nNo tree in memory,Test Fail!\n\n";
     break;
    }
   case 4:
    {
     if(atree!=NULL)
     {
      cout<<"\n\nWhat do you want to find? : ";
      cin>>n;
      f=find(atree,n);
      if(f==NULL)
      {
       cout<<"\n\nSorry,"<<n<<" can't be found!\n\n";
      }
      else
      {
       cout<<"\n\nObject "<<f->obj_key<<" has been found!\n\n";
      }
     }
     else
      cout<<"\n\nNo tree in memory,Find Fail!\n\n";
     break;
    }
   case 5:
    {
     if(atree!=NULL)
     {
      travel(atree);
      for(int count=0;count<i;count++)
      {
 
       cout<<" "<<stack[count]->key<<",";
      }
     }
     else
      cout<<"\n\nNo tree in memory,Travel Fail!\n\n";
     break;
    }
   case 6:
    {
     if(atree!=NULL)
     {
      cout<<"\n\nWhich object do you want to delete?\n\n";
      cin>>n;
      if(del(atree,n)==0)
      {
       cout<<"\n\n"<<n<<" has been deleted!\n\n";
      }
      else
       cout<<"\n\nNo this object\n\n";
     }
     else
      cout<<"\n\nNo tree in memory,Delete Fail!\n\n";
     break;
    }
   case 7:
   {
    if(atree!=NULL)
    {
     remove_tree(atree);
     cout<<"\n\nThe Tree has been removed!\n\n";
     atree=NULL;
    }
    else
     cout<<"\n\nNo tree in memory,Removing Fail!\n\n";
   }
   default:
    cout<<"\n\nNo this operation!\n\n";
   }
   n=0;
  }
 }

[编辑] 参见

• Tree rotation
• 伸展樹
• 紅黑樹
• B樹

[编辑] 引用

• G. Adelson-Velskii and E.M. Landis, "An algorithm for the organization of information." Doklady Akademii Nauk SSSR, 146:263–266, 1962 (Russian). English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.

[编辑] 外部链接

• Description from the Dictionary of Algorithms and Data Structures
• AVL Tree Traversal
• Linked AVL tree
• C++ AVL Tree Template and C AVL TREE "Generic Package" by Walt Karas
• A Visual Basic AVL Tree Container Class by Jim Harris
• AVL Trees: Tutorial and C++ Implementation by Brad Appleton
• Ulm's Oberon Library: AVLTrees
• The AVL TREE Data Type
• CNAVLTree Class Reference
• GNU libavl
• AVL-trees - balanced binary trees by Alex Konshin
• Simulation of AVL Trees
• AVL tree applet
• Simulation of AVL Trees (DYNAMIC)
• AVL, Splay and Red/Black Applet
• AVL树注释实现
• 高度平衡树注释实现