[科普中国]-AVL树

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

特点AVL树本质上还是一棵二叉搜索树，它的特点是：1

1.本身首先是一棵二叉搜索树。

2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

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

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

单向右旋平衡处理LL：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；

单向左旋平衡处理RR：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；

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

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

插入向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次 AVL 旋转都耗费恒定的时间，插入处理在整体上耗费 O(log n) 时间。 在平衡的的二叉排序树Balanced BST上插入一个新的数据元素e的递归算法可描述如下： 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1； 若e的关键字和BBST的根结点的关键字相等，则不进行； 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：BBST的根结点的平衡因子为-1（右子树的深度大于左子树的深度，则将根结点的平衡因子更改为0，BBST的深度不变； BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1； BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变； 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。

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

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

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

#include #include ； #include ； //建立一个整数类型 #define MAXSIZE 512 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； //建立堆栈 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(i0) 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;elsenode->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_keykey)tmp=tmp->left;elsetmp=tmp->right;}if(tmp->key==query_key)return((obj_node_t*)tmp->left);elsereturn(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_keykey)tmp=tmp->left;elsetmp=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->keyleft=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);}elsereturn(-1）；}else{tmp=tree;stack_clear();while(tmp->right!=NULL){upper=tmp;push(upper);if(keykey){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->right==NULL && stack->height==0) //this statement is leaf,but also contains an empty treestate=0;else if(stack->left!=NULL && stack->right!=NULL){if(abs(stack->height-stack->height)