AVL 平衡二叉树

时间:2021-05-29 17:31:15


#include "stdio.h"
#include "stdlib.h"

typedef struct _Node{
	int data;
	int h;
	struct _Node* lf;
	struct _Node* rt;
}Node, *pNode;

int ht(pNode a){
	return a?a->h:0;
}

int mh(pNode a, pNode b){
	return ht(a)>ht(b)?ht(a):ht(b);
}

void LL(pNode* root){
	pNode t, w = *root;
	t = w->lf;
	w->lf = t->rt;
	t->rt = w;
	*root = t;
	w->h = mh(w->lf, w->rt) +1;   //移到了右边,更新高度
}

void RR(pNode* root){
	pNode t, w = *root;
	t = w->rt;
	w->rt = t->lf;
	t->lf = w;
	*root = t;
	w->h = mh(w->lf, w->rt) +1;  //移到了左边,更新高度

}

void LR(pNode* root){
	RR(&((*root)->lf));   //这句后面是否需要加一句更新高度?不需要
	LL(root);
}

void RL(pNode* root){
	LL(&((*root)->rt));
	RR(root);
}

void rotate(pNode* root){   //旋转平衡
	pNode w = *root;
	if(ht(w->lf) - ht(w->rt) == 2){
		if(ht(w->lf->lf) > ht(w->lf->rt))
			LL(root);
		else
			LR(root);
	}
	if(ht(w->rt) - ht(w->lf) == 2){
		if(ht(w->rt->rt) > ht(w->rt->lf))
			RR(root);
		else
			RL(root);
	}
	w = *root;   //为什么要这样?因为在前面旋转时,*root已经改变,w和*root已经不是指向同一个地方
	w->h = mh(w->lf, w->rt) +1;  //更新高度
}

void insert(pNode* root, int val){
	pNode w = *root;
	if(!w){
		w = (pNode)malloc(sizeof(Node));
		w->data = val;
		w->h = 1;
		w->lf = w->rt = 0;
		*root = w;
		return;
	}
	
	if(val > w->data)
		insert(&(w->rt), val);
	else
		insert(&(w->lf), val);
	rotate(root);
}

void remove(pNode* root, int val){
	pNode t, w = *root;
	if(!w) return;
	if(val == w->data){
		if(w->rt == 0){   //如果节点只有左子树,直接删掉,并将其左子树接上
			*root = w->lf;
			free(w);
			return;
		}
		t = w->rt;  //否则,用该节点右子树的最左子节点来代替,这是个递归的过程
		while(t->lf) t = t->lf;
		w->data = t->data;
		remove(&(w->rt), t->data);  //用右子树的最左节点来代替后,那还得用右子树的最左节点的右子树的最左节点来代替……递归
	}else if(val > w->data)
		remove(&(w->rt), val);
	else 
		remove(&(w->lf), val);
	rotate(root);
}

void show(pNode root){
	if(!root) return;
	printf("%d ", root->data);
	show(root->lf);
	show(root->rt);
}

void main(){
	int i;
	pNode root = 0;
	for(i=20; i>=0; i--)
		insert(&root, i);
	show(root);
	printf("\n");
	remove(&root, 7);
	remove(&root, 13);
	remove(&root, 19);
	remove(&root, 16);
	show(root);
	printf("\n");
}


关于高度更新:

AVL 平衡二叉树

经过LL旋转,A的高度更新了,但B的高度没更新,是否需要再写一句代码更新呢?不需要。因为插入B1后,B1高度变成h,然后回退到B节点,更新高度为h+1,此时以B为根的树还是平衡的,不需要旋转,但继续回退到A时,发现不平衡,才开始执行LL,也就是说,在执行LL操作前,B的高度已经更新为h+1,LL操作后,不需要再更新B的高度。

即:LL操作中,只更新降为右子树的节点(例如上图的A点)即可。不需要再写一句来更新根(B点)的高度。

AVL 平衡二叉树

RR操作与LL操作相同,只需更新降为左子树的节点(如上图的A)即可

AVL 平衡二叉树

LR操作是先RR操作再LL操作。通过上面可知,RR操作时,上图中B的高度更新了,再进行LL操作时,A的高度也更新了,最后C成了树根,高度没更新,那是否也和上面一样不需要再写一句更新呢?答案是需要。

C在其子树插入节点后,树高更新为h,等LR操作结束后,C成了树根,其高度应该为h+1,所以需要再写一句更新高度。


AVL 平衡二叉树

RL操作与LR操作同理,过程中会先更新B的高度,再更新A的高度,最后需要再写一句来更新C的高度

更多参考:

http://www.asiteof.me/2010/06/avl/

http://www.asiteof.me/2010/06/avl/


- - - - - - - - - - - - - - - - -- - -  - - - - -- - - - - - - - - - - - - --  --  - -- - - - - - - - - - - 

进一步浓缩:

#include "stdio.h"
#include "stdlib.h"

typedef struct _Node{
	int val;
	int h;
	struct _Node* ch[2];
}Node, *pNode;

int ht(pNode r){
	return r?r->h:0;
}

void update(pNode r){
	r->h = (ht(r->ch[0])>ht(r->ch[1])?ht(r->ch[0]):ht(r->ch[1])) + 1;
}

void xxx(pNode* r, int op){ //0, LL; 1, RR;
	pNode t, w = *r;
	t = w->ch[op];
	w->ch[op] = t->ch[!op];
	t->ch[!op] = w;
	*r = t;
	update(w);
}

void zzz(pNode* r, int op){ //0, LR; 1, RL;
	xxx(&((*r)->ch[op]), !op);
	xxx(r, op);
}

void rotate(pNode* r){
	int op;
	pNode w = *r;
	for(op=0; op<2; op++){
		if(ht(w->ch[op])-ht(w->ch[!op]) == 2){
			if(ht(w->ch[op]->ch[op]) > ht(w->ch[op]->ch[!op]))
				xxx(r, op);
			else
				zzz(r, op);
		}
	}
	update(*r);
}

void insert(pNode* r, int val){
	pNode w = *r;
	if(!w){
		w = (pNode)malloc(sizeof(Node));
		w->val = val;
		w->h = 1;
		w->ch[0] = w->ch[1] = 0;
		*r = w;
		return;
	}
	if(val > w->val)
		insert(&(w->ch[1]), val);
	else
		insert(&(w->ch[0]), val);
	rotate(r);
}

void del(pNode* r, int val){
	pNode t, w = *r;
	if(!w) return;
	if(val == w->val){
		if(!(w->ch[1])){
			*r = w->ch[0];
			return;
		}
		t = w->ch[1];
		while(t->ch[0]) t = t->ch[0];
		w->val = t->val;
		del(&(w->ch[1]), t->val);
	}else if(val > w->val)
		del(&(w->ch[1]), val);
	else
		del(&(w->ch[0]), val);
	update(w);
}

void show(pNode r){
	if(!r) return;
	printf("%d ", r->val);
	show(r->ch[0]);
	show(r->ch[1]);
}

void destroy(pNode r){
	if(!r) return;
	destroy(r->ch[0]);
	destroy(r->ch[1]);
	free(r);
}

void main(){
	int i;
	pNode root = 0;
	for(i=0; i<20; i++)
		insert(&root, i);
	show(root); printf("\n");
	del(&root, 3);
	del(&root, 7);
	del(&root, 10);
	show(root); printf("\n");
}