本文共 2158 字，大约阅读时间需要 7 分钟。

1、定义

任意结点的左、右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树。左子树与右子树的高度差为该节点的平衡因子，平衡因子值只能是-1，1，0

2、插入

A、二叉排序树保证平衡的基本思想：每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。B、在新节点插入后，若造成查找路径上某个结点不在平衡，则需做出相应调整。分4中情况： 1. LL平衡旋转（右单旋转） 2. RR平衡旋转（左单旋转） 3. LR平衡旋转（先左后又双旋转） 4. RL平衡旋转（先右后左双旋转）

template
   
    BinNodePosi(T) AVL(T)::insert(const T & e){
   	BinNodePosi(T) &x=search(e);	if(x) BinNodePosi(T) return x;//若目标尚不存在 	x=new BinNode
    
     (e,_hot);-size++;	BinNodePosi(T) xx=x;//则创建x	//以下，从x的父亲出发逐层向上，依次检查各代祖先g 	for(BinNodePosi(T) g=x->parent;g;g=g->parent);	if(!AVLBalanced(*g)){
   //一旦发现g失衡，则通过调整恢复平衡 		FromParentTo(*g)=rotateAt(tallerChild(tallerChild(g)));		break;//否则只需简单地 	}else//更新其高度（平衡性虽不变，高度确可能改变） 		updateHeight(g);	return xx;//返回新节点，至多1次调整 }
    
   

3、查找

template 
   
    BinNodePosi(T)  & BST
    
     :: search(const T &e){
   	return searchIn(_root,e,_hot=NULL);	}//从根节点启动查找 static BinNodePosi(T) & searchIn(//尾递归 	BinNodePosi(T) & v,//当前（子）树根 	const T & e,//目标关键码 	BinNodePosi(T) & hot//记忆热点 ){
   	if(!v||(e==v->data)) return V;	hot=v;//先记下当前（非空）节点，然后再。。。 	return serchIn(((e
     
      data)?v->lChild:v->rChild),e,hot); }//运行时间正比于v的深度，不超过树高O（h）
     
    
   

平衡二叉树进行查找的过程与二叉排序树的相同。二叉树平均查找长度O（log2 n)

4、删除 5、（3+4）重构

template
   
     BinNodePosi(T) BST
    
      :: connect34{
   	BinNodePosi(T) a,BinNodePosi(T) b,BinNodePosi(T) c;	BinNodePosi(T) T0,BinNodePosi(T) T1,BinNodePosi(T) T2,BinNodePosi(T) T3;	{
   		a->lchild=T0;if(T0) T0->parent=a;		a->rchild=T1;if(T1) T1->parent=a;updateHeight(a);	}}template
     
       BinNodePosi(T) BST
      
        rotateAt(BinNodePosi(T) v){
   	BinNodePosi(T) p=v->parent,g=p->parent;	if(IsLChild)(*p)		if(IsLChild(*v)){
   			p->parent=g->parent;			return connect34(v,p,g,v->lChild,v->rChild,p->rChild,g->rChild);		}		else{
   			v->parent=g->parent;			return connect34(p,v,g,p->lChild,v->lChild,v->rChild,g->rchild);		}		else{
   					}}
      
     
    
   

6、性能分析

优点：无论查找、插入或删除，最坏情况下的复杂度均为O（log2 n），O（n）的存储空间。 缺点： 1）借助高度或平衡因子，为此需改造元素结构，或额外封装。 2）实测复杂度与理论复杂度尚有差距 插入/删除后的旋转，成本不菲 删除操作后，最多需要旋转 若需频繁进行插入/删除操作，未免得不尝失 3）单次动态调整后，全树拓扑结构的变化量可能高达

转载地址：http://wzgwi.baihongyu.com/