平衡二叉树实现

avl树代码实现

0x00 insert代码

​ 注意使用该函数时，要将返回值赋值给传入的p，因为根节点会在旋转时改变。

node avl_insert(node p,int x){
	node ret=p;
	if(!p){
		ret=createnode(x);
	}else{
		if(x>p->data){
			//通过递归，插入节点，在插入节点后，要检查平衡因子 
			//因为是插在右边，所以只检查hr-hl>1 
			//如果大于1，就 判断是rr  rl中的哪一种 
			//方法是 如果插入的x比p->right->data大，那就说明在右边的右边是rr，否则rl； 
			p->right=avl_insert(p->right,x); 
			if(getheight(p->right)-getheight(p->left)>1){
				if(x>p->right->data){
					node temp=p->right;
					p->right=temp->left;
					temp->left=p; 
					ret=temp;
				}else if(x<p->right->data){
					node temp=p->right;
					node temp1=temp->left;
					p->right=temp1->left;
					temp->left=temp1->right;
					temp1->left=p;
					temp1->right=temp;	
					ret=temp1;
				}
			} 
			
		}else if(x<p->data){
			p->left=avl_insert(p->left,x);
			if(getheight(p->right)-getheight(p->left)>1){
				if(x<p->left->data){
					node temp=p->left;
					p->left=temp->right;
					temp->right=p; 
					ret=temp;
				}else if(x>p->left->data){
					node temp=p->left;
					node temp1=temp->right;
					temp->right=temp1->left;
					p->left=temp1->right;
					temp1->left=temp1;
					temp1->right=p;
					ret=temp1;
				}
			} 
		}else{
			printf("节点已有！");
			ret=p;
		}
	}
	return ret;
}

0x01 delete代码

引用其他博主的思路，今天太累了，先不写

虽然AVL树的删除操作比较麻烦。 但是明白了插入过程，删除过程也就不难理解。 递归删除的实现，也是沿着树递归向下寻找，直到找到该元素。 如果只有一个儿子或没有儿子那么直接删除他，返回(只有一个儿子时由于原来是平衡的，再删除一个仍然时平衡的) 他的儿子(或空节点)，和插入操作一样，因为是带返回的插入，在回溯的过程会将他们连接起来。所以我们只要返回 其儿子(或空)就行了。 如果是两个儿子，那么就有点麻烦了。因为正真要删除的是其右子树中的最小关键字。 对有两个儿子的删除操作，还要对其右子树使用一个递归历程。递归的寻找左儿子，当左儿子的儿子为空是，即找到 右子树中的最小关键字。于是删除他返回其儿子节点(空节点)。 无论是如何删除的，删除后的回溯过程都需要修复可能的高度规则破坏。即判断左右子树高度差是不是小于1 不如不是，那么就要进行修复操作。通过比较左右子树的高度差，根据比较结果再在比较 左子树/右子树 的左右子树高度 差，从而判断对应那种旋转修复操作。