数据结构:AVL树(平衡二叉树)

一,概述

对于普通的查找二叉树,由于删除操作的某些规定,导致最终删除的结果是根节点的左右子树严重不平衡,这对他的正常操作带来严重的影响。因此提出了avl树,在avl树中,任意两个节点的子树的高度的相差最多为1。当然这对他的删除和插入操作提出了新的要求。本文将详细介绍avl树的设计思想和基本操作。

二基本术语。

有4种以下的情况可能导致二叉树不平衡,分别为:

(1)LL:插入一个新节点到根节点的左儿子的左子树,导致跟节点失去平衡。

(2)RR:插入一个新节点到根节点的右儿子的右子树,导致跟节点失去平衡。

(3)LR:插入一个新节点到根节点的左儿子的右子树,导致跟节点失去平衡。

(4)RL:插入一个新节点到根节点的右儿子的左子树,导致跟节点失去平衡。

针对上面的出现的不平衡,可以通过旋转使之恢复平衡。

(1),(2)种情况,使用单旋转。

(3),(4)种情况,使用双旋转。

三,详细介绍上面的四种情况,以及解决方法。

情况1:对于比较简单的a情形:

《数据结构:AVL树(平衡二叉树)》

3为插入的值,相应的代码(单旋转)如下,不考虑高度的情况下

//设5这个节点为k2,即传入的参数为k2(因为这个节点失去平衡)
position singlerotatewithleft(position k2){
	position k1;
	k1=k2->left;
	k1->right =k2;
	return k1;
}

对于较复杂的情形b呢?如下图所示:

《数据结构:AVL树(平衡二叉树)》

4为插入的值,相应的代码(单旋转)如下,不考虑高度的情况下

//设8这个节点为k2,即传入的参数为k2(因为这个节点失去平衡)
position singlerotatewithleft(position k2){
	position k1;
	k1=k2->left;
	k2->left=k1->right;
	k1->right =k2;
	return k1;
}

发现没有,仅仅比上面多了一行代码,而这行代码在情形a中也适合。

那么对于更复杂的情形c呢,如下图所示,

《数据结构:AVL树(平衡二叉树)》

初看,5,7两个节点都是不平衡的节点,那么我们应该平衡5,再平衡7节点。但是事实上,只要解决了5节点,那么7节点就不需要解决了。(存不存在既要解决两个节点的情况呢,当然存在,当6有右孩子的时候,仍然要平衡7,所以要递归遍历),对于这段代码,同上面。

情况2与1相似,这里不做讨论,给出以下代码:

position singlerotatewithright(position k2){
	position k1;
	k1=k2->right;
	k2->right=k1->left;
	k1->left =k2;
	return k1;
}

情况3:解决方法是对失衡节点的左儿子进行右单旋转,然后再对它本身进行左单旋转。(情况4相反)

如下图:

《数据结构:AVL树(平衡二叉树)》

看了上图,是不是对定义 LR:插入一个新节点到根节点的左儿子的右子树,导致跟节点失去平衡,更清楚了呢?为什么是左儿子,为什么是右子树。

那么他的实现代码如下所示:

position doublerotatewithleft(position k2){
	k2->left = singlerotatewithright(k2->left);
	return singlerotatewithleft(k2);
}

四,关于删除操作。

暂时不考虑。。。。

总的实现代码如下所示:

#include<stdio.h>
#include<stdlib.h>

typedef struct treenode{
	struct treenode *left;
	struct treenode *right;
	int height; //高度:叶子节点高度为0
	int element;
}treenode;

typedef treenode* position;
position single_rotate_left(position );
int height(position);
position insert_node(position,int);
position double_rotate_leftright(position);
position double_rotate_rightleft(position);
int max_2(int x,int y){
	if(x>y){
		return x;
	}
	return y;
}
int height(position p1){
	if(p1==NULL){
		//为什么是-1呢?因为叶子节点是0,而基本的操作是节点的高度为
		//节点的左子树与右子树的最大值加1,所以必须是-1
		return -1;
	}
	return p1->height;
}

position single_rotate_left(position k2){
	position k1;
	
	k1 = k2->left;
	k2->left=k1->right;
	k1->right=k2;
	
	//因为除了k2和k1节点的高度变了,而其他的节点的高度都没有变
	//那么可以用最简单的方法求出他们的高度。。。
	
	k1->height=max_2(height(k1->left),height(k1->right))+1;
	k2->height=max_2(height(k2->left),height(k2->right))+1;
	return k1;
}

position single_rotate_right(position k2){
	position k1;
	
	k1=k2->right;
	k2->right=k1->left;
	k1->left =k2;

	k1->height=max_2(height(k1->left),height(k1->right))+1;
	k2->height=max_2(height(k2->left),height(k2->right))+1;
	
	return k1;
}
position double_rotate_leftright(position p){
	p->left = single_rotate_right(p->left);
	p=single_rotate_left(p);
	return p;
}
position double_rotate_rightleft(position p){
	p->right=single_rotate_left(p->right);
	p=single_rotate_right(p);
	return p;
}

//其实插入操作整个过程和查找二叉树的方法类似
position insert_node(position t,int x){
	if(t==NULL){
		
	//可以插入一个新的节点
		position p =(position)malloc(sizeof(treenode));
		p->height=0;
		p->element = x;
		p->left=NULL;
		p->right=NULL;
		t=p;
	}else{
		if(x<t->element){
			t->left=insert_node(t->left,x);
			//对于下面这个判断,应该非常清楚
			//左右子树相减为2,说明出现不平衡
			if(height(t->left)-height(t->right)==2){
				//这判断的依据来源于:
				//是插入左儿子的左子树中,还是插入到做儿子的右子树中
				//因此 只要比较左儿子的 值就可以了
				if(x<t->left->element){
					t=single_rotate_left(t);
				}else if(x>t->left->element){
					t=double_rotate_leftright(t);
				}
			}
		}
		else if(x>t->element){
			t->right=insert_node(t->right,x);

			if(height(t->right)-height(t->left)==2){
				if(x>t->right->element){
					t=single_rotate_right(t);
				}else if(x<t->right->element){
					t=double_rotate_rightleft(t);
				}
			}
			
		}
	}
	
	t->height=max_2(height(t->left),height(t->right)) + 1;
	
	return t;
}
position initial(){
	position p=(position)malloc(sizeof(treenode));
	p->height=0;
	p->left=NULL;
	p->right=NULL;
	return p;
}
void tree_print(position p){
	if(p==NULL)
	{
		return;
	}
	tree_print(p->left);
	printf(" %d ",p->element);
	tree_print(p->right);
}
void main(){
	position p=initial();
	p->element= 5;
	insert_node(p,2);
	insert_node(p,6);
	insert_node(p,1);
	insert_node(p,4);
	//为什么是p=insert_node(p,3);而前面不需要,因为根节点在这个时候产生变化
	p=insert_node(p,3);
	tree_print(p);
}
    原文作者:AVL树
    原文地址: https://blog.csdn.net/haizi8888/article/details/8631473
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞