平衡二叉树AVL

1 结点定义

//平衡二叉树AVL 
struct node{int v,height;node *lchild,*rchild;
};

2 创建新结点

//创建新结点 
node* newNode(int v){node* Node=new node;Node->v=v;Node->height=1;	//结点高度初始化为1 Node->lchild=Node->rchild=NULL;return Node;
}

3 获取结点root所在子树的当前高度

//获取结点root所在子树的当前高度 
int getHeight(node* root){if(root==NULL) return 0;	//空结点高度为0 return root->height;
}

4 计算结点root的平衡因子

//计算结点root的平衡因子 
int getBalanceFactor(node* root){//左子树高度减右子树高度 return getHeight(root->lchild)-getHeight(root->rchild);
}

5 更新结点root的height

//更新结点root的height
void updateHeight(node* root){root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}

6 查找AVL树中数据域为x的结点

//查找AVL树中数据域为x的结点
void search(node* root,int x){if(root==NULL){printf("search failed\n");return;}if(x==root->v)printf("%d\n",root->v);else if(x<root->v)search(root->lchild,x);elsesearch(root->rchild,x);
}

7 左旋

//左旋
void L(node* &root){node* temp=root->rchild;root->rchild=temp->lchild;temp->lchild=root;updateHeight(root);updateHeight(temp);root=temp;
} 

8 右旋

//右旋
void R(node* &root){node* temp=root->lchild;root->lchild=temp->rchild;temp->rchild=root;updateHeight(root);updateHeight(temp);root=temp;
}

9 插入权值为v的结点

//插入权值为v的结点
void insert(node* &root,int v){if(root==NULL){	//到达空结点就新增一个权值为v的结点root=newNode(v);return;}if(v<root->v){insert(root->lchild,v);	//往左子树插入 updateHeight(root);	//更新树高 if(getBalanceFactor(root)==2){if(getBalanceFactor(root->lchild)==1){	//LL型 R(root); }else if(getBalanceFactor(root->lchild)==-1){//LR型 L(root->lchild);R(root);}}}else{insert(root->rchild,v);updateHeight(root);if(getBalanceFactor(root)==-2){if(getBalanceFactor(root->rchild)==1){	//RL型 R(root->rchild);L(root);}else if(getBalanceFactor(root->rchild)==-1){//RR型 L(root);}}}
}

10 AVL树的建立

//AVL树的建立
node* Create(int data[],int n){node* root=NULL;for(int i=0;i<n;i++){insert(root,data[i]);}return root;
}