插入函数Insert

先放一下代码。因为是照着黑皮书《数据结构与算法分析》学的,所以代码大致和书上的一样,我并没有做太多修改。只是在理解原理的时候有些比较棘手的地方,所以在这里记笔记,方便以后查看。

int max(int n1,int n2)
{
	if (n1 >= n2)
		return n1;
	else
		return n2;
}
//取最大值
 
static int Height(position P)
{
	if (P = NULL)
		return -1;
	else
		return P->height;
}
//获取高度//只是通过结构内定义的高度去取值,没有测算
 
static position SingleRotateWithLeft(position K2)
{
	position K1;
	K1 = K2->left;
	K2->left = K1->right;
	K1->right = K2;
	K1->height = max(Height(K1->left), Height(K1->right)) + 1;
	K2->height = max(Height(K2->left), Height(K2->right)) + 1;
	return K1;
}
//单旋转(左树旋转)
 
static position DoubleRotateWithLeft(position K3)
{
	K3->left = SingleRotateWithRight(K3->left);
	return SingleRotateWithLeft(K3);
}
//双旋转(左树旋转)
 
static position SingleRotateWithRight(position K1)
{
	position K2;
	K2 = K1->right;
	K1->right = K2->left;
	K2->left = K1;
	K1->height = max(Height(K1->left), Height(K1->right)) + 1;
	K2->height = max(Height(K2->left), Height(K2->right)) + 1;
	return K2;
}
//单旋转(右树旋转)
 
static position DoubleRotateWithRight(position K3)
{
	K3->right = SingleRotateWithLeft(K3->right);
	return SingleRotateWithRight(K3);
}
//双旋转(右树旋转)
 
avltree insert(int X,avltree T)
{	
	if (T == NULL)
	{
		//T为空节点
		T = new avlnode;//假定空间永远是足够的
		T->height = 0;
		T->left = T->right = NULL;
		T->info = X;
	}
	if (X < T->info)
	{
		T->left = insert(X, T->left);
		if (Height(T->left) - Height(T->right) >= 2)//事实上等于2才是最合适的
		{
			if (X < (T->left->info))
				T = SingleRotateWithLeft(T);
			else
				T = DoubleRotateWithLeft(T);
		}
	}
	else if (X > T->info)
	{
		T->right = insert(X, T->right);
		if (Height(T->right) - Height(T->left) >= 2)//事实上等于2才是最合适的
		{
			if (X > (T->right->info))
				T = SingleRotateWithRight(T);
			else
				T = DoubleRotateWithRight(T);
		}
	}
	T->height = max(Height(T->left), Height(T->right)) + 1;
	return T;
}

如果你也有这本书,并且已经看过这一部分关于avl的描述了,那么关于“什么是avl树”以及这些代码的作用至少是明白的,这里我主要是对书中所写的insert函数做些笔记。

因为在树这一节中,很多地方都是通过递归来实现的,不得不承认这是一种非常巧妙的方法,但对于我这种小白来说,阅读和分析递归代码往往会转不过弯(其实更多时候是我懒得动笔,只在脑子里转了几十个循环,最后把自己绕懵了......)

写在前面,书中的element我用int类型的info代替了,我觉得这样会更容易理解(虽然这样做其实也没什么意义就是了)。

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

Insert过程分析:

首先,这段函数的第一部分用来判断T节点是否存在。但我最开始还在奇怪,因为我们通常都是创建好了一颗空树,然后再进行插入节点的工作,而这里却要判断T节点是否为空。

但可能是书上对这里的解释并不是那么清楚,这里我说一些自己的看法,如果有问题,欢迎指出。

函数中的X代表的就是info,而T则应该输入我们要进行操作的树的根节点地址,毕竟我们也不清楚这个X应该放到树的什么地方。

但值得注意的是,我们是在使用递归来实现这个功能,也就是说,在每一次递归循环中,T节点是不断改变的,它最终会找到我们要插入数据的实际位置,并在这个地方开辟出新的节点,这才是这段函数的作用。

那么关键其实就在于寻址了。找到X应该放置的位置其实并不难,ADT树中也已经说过这种方法,但找到之后,却要按照AVL树的性质来存放数据。

假设,我们通过函数递归,T参数已经来到了NULL的位置,于是这一次的递归中第一次开辟出了新节点。于是我们将新节点的地址返回到了上一次递归中(显然X=T->info,所以其他判断都不起作用了)。

不妨假设我们上一次是向左树去找,大概就是下面这样(没用鼠标垫,所以漂移的有点厉害......):

所以这一次,T节点实际上是指K1。

T->left = insert(X, T->left);

而我们刚执行完这条函数,接下来判断K1节点是否打破了平衡状态。

if (Height(T->left) - Height(T->right) >= 2)//事实上等于2才是最合适的

(之所以会有这道注释,其实只是我的喜好罢了。因为如果在创建和修改二叉树的时候都有这样的操作,那么左树和右树的高度差值根本不可能超过2,因为一旦达到2就会被重新平衡,但我还是想这样写.....)

假设我们这一次没有打破这个平衡,那么最终我们将会返回K1的地址。

注:这里有个巧妙的地方,

T->height = max(Height(T->left), Height(T->right)) + 1;

这段函数能够保证每一次插入节点的时候,都能为它获取高度。假设现在有一颗空树,我插入的第一个节点T1就获得了高度‘0’,而再次插入新节点T2的时候,T2的高度是‘0’,而这条代码获取了T2的高度又+1,变成了自己的高度,从而到达了高度‘1’。如果每个节点都通过这个函数来插入,那么深度自然就被设定好了。

假设我们从上一次递归出来,回到了下图这个位置。本次递归中T代表了K3的地址。 

现在,我们通过判断,发现K3打破了平衡状态,于是做了一个奇怪的判断:

if (X < (T->left->info))

函数在判断X是不是小于K1的关键值。

如果判断为真,其实就说明K2会成为K1的左节点,那么就要进行左树单旋转操作。

如果判断为假,说明K2是K1的右节点,那么就要进行左树的双旋转操作。

(判断左树还是右树,其实是根据K1的位置判断。很简单,所以不再赘述)

旋转结束之后,返回了K1的地址(这个地址怎么来的,写在左树单旋转函数里了,该函数返回新根)。

假设这一次是平衡的,那么大概会长上图这样了。

最后就是把剩下的还没走完的递归流程走完就行了,这个过程中通常不会再有什么操作了,因为如果你每一次放入节点都用这个函数来操作,基本上都能保证当前的树是一颗正常的树,放入的新节点最多只能影响到它的‘祖父母辈’的平衡状态,只要把‘祖父母辈’的平衡修正回来,通常整棵树都会平衡。

(这个结论是我自己猜测的,如果有错误欢迎指出)

删除函数Delete

 先放一下代码:(请注意注释。关于旋转函数,分析insert时贴出过,仅供参考。如果在某个地方没有理解,请先继续往下看一会,或许能找到答案。如果发现代码和解释有问题,请务必指出。

avltree deletenode(int X, avltree T)
{
	//X为删除目标的关键字值
	//info为关键字值
	position tmp;
	if (T == NULL)
		return NULL;
	else if (X < T->info)
	{
		T->left=deletenode(X, T->left);
		if (Height(T->right)-Height(T->left) >= 2)//height函数用于返回节点所处的高度
		{
			tmp = T->right;
			if(Height(tmp->right)>Height(tmp->left))
				T = SingleRotateWithRight(T);//右树单旋转
			else
				T = DoubleRotateWithRight(T);//右树双旋转
 
		}
	}
	else if (X > T->info)
	{
		T->right=deletenode(X, T->right);
		if (Height(T->left) - Height(T->right) >= 2)
		{
			tmp = T->left;
			if (Height(tmp->left) > Height(tmp->right))
				T = SingleRotateWithLeft(T);//左树单旋转
			else
				T = DoubleRotateWithLeft(T);//左树双旋转
		}
	}
	else
	{
		if (T->left == NULL && T->right == NULL)//若目标节点没有为叶子
		{
			delete T;
			return NULL;
		}
		else if (T->right == NULL)//若目标节点只有左子树
		{
			tmp = T->left;
			delete T;
			return tmp;
		}
		else if (T->left==NULL)//若目标节点只有右子树
		{
			tmp = T->right;
			delete T;
			return tmp;
		}
		else//若目标节点左右都有子树
		{
			if (Height(T->left) > Height(T->right))
			{
				tmp = findmax(T->left);//找出参数节点中最大的节点,返回地址
				T->info = tmp->info;
				T->left = deletenode(tmp->info,T->left);
			}
			else
			{
				tmp = findmin(T->right);//找出参数节点中最小的节点,返回地址
				T->info = tmp->info;
				T->right = deletenode(tmp->info, T->right);
			}
		}
	}
	T->height = max(Height(T->left), Height(T->right)) + 1;
	return T;
}

前提条件:假设现在面对的是一颗完整正确的AVL树,而我们需要对其进行删除节点的操作。

主要思路是运用递归的方法来进行查找,向函数中输入目标节点的关键字以及根节点地址,进行查找。

首先进入递归,函数通过这两条代码以及上面的 if条件语句 进行匹配关键字:

T->left=deletenode(X, T->left);	
T->right=deletenode(X, T->right);

当我们成功找到了这个关键字所在的节点,进入本次递归,此时T节点代表了目标节点。(方便区分起见,我将每个目标节点T称之为T1节点)

于是进入了再往下的环节:判断该节点是否有子树。

情景一:(无子树)

假设该节点是叶,那么它既没有左子树也没有右子树,直接删除该节点,返回NULL值,回到了进入本次递归的函数位子,假设是这一段:

T->right=deletenode(X, T->right);

那么,T1节点的父节点成功的将本该指向T1的指针指向了NULL,实现了最基础的 ‘叶删除’ 操作。

情景二/情景三:(一个子树)

要么只有左子树,要么只有右子树,这是两个相近的情景,所以何在一起解释。

在每一次的递归中,函数都会创建一个tmp指针用来储存可能必要的信息(你也可以对这个函数进行优化,毕竟不是每一轮递归都需要它,这或许能省下一部分空间)

假设现在我们要删除的目标节点只有一个左子树:

那么我们将tmp指向它左子树的第一个节点,并将这个地址返回,然后T1节点被删除。和情景一相同,它的父节点成功指向了返回值,也就是T1的左子树。

然而需要注意的是,这是在AVL树中的实现。按照AVL树的性质,倘若一个节点没有右子树,那么它的左子树最多也只能有一个节点。所以每个节点对应的高度就有可能发生变化。

T->height = max(Height(T->left), Height(T->right)) + 1;

因为叶子仍然是叶子,高度仍然为 0 (假设叶子的高度均为0,当然,这只是假设罢了),于是通过返回的递归右重新测算了改变高度的节点的高度。

至此,删除节点被实现了。

情景四:(两个子树)

最麻烦也最难理解的部分(只是相对而言罢了)。

if (Height(T->left) > Height(T->right))

他判断了一下目标节点左树和右树哪个比较高,这里不妨先假设一下左树比较高的情景吧。

函数令tmp指向了左树中最大的那个节点,并将该节点的关键字赋予T1节点(实际上是将tmp复制给T1)。

然后进入下一轮递归

T->left = deletenode(tmp->info,T->left);

注意:这一次,查找的目标关键字变成了左树中最大的那个。

于是我们到达了第二个目标节点T2,并对它进行了删除(这是一个非常简单的删除方法,因为AVL性质规定了数值的大小,只要不停的向右走,走到没有右子树的时候,就能遇见这个最大值,所以这个T2节点一定没有右子树,情景和上面的一样)。

而之所以要找左树中最大的值,是因为进行复制之后,并不会破坏AVL树在数值上的结构:节点左树中的所有值低于节点,右树中所有值高于节点。

最后测算高度,完成了删除节点的工作。

旋转判定:

以上工作只是完成了 ‘ 删除节点 ’ 这一项,但事实上,删除节点之后,还必须面临打破平衡条件的可能性。

回到每一轮递归的入口:(本轮T节点将被称为T3)

T->left=deletenode(X, T->left);	
if (Height(T->right)-Height(T->left) >= 2)//height函数用于返回节点所处的高度		{
	tmp = T->right;
	if(Height(tmp->right)>Height(tmp->left))
			T = SingleRotateWithRight(T);//右树单旋转			
	else
		T = DoubleRotateWithRight(T);//右树双旋转
}

当我们离开递归之后,必须进行判断是否打破了平衡条件(递归实现了高度的重新测算,这也是非常棒的地方) 。

注:判断条件写了“右树-左树>2”,而并没有包括“左树-右树”的情况。原因是因为:这个路口是指向左树的,也就是说,我们将在左树中删除某个节点。二叉树本身应该保持平衡,倘若现在左树被删除节点,那么左树就不可能比右树要高,所以只需要判断这一种情况即可。在向右查找的过程中也是如此。

假设现在平衡被打破了。也就是说,右树比左树高了 2(其实高度差不可能超过 2 ,但我习惯写成 “>=” 罢了)。

那么该轮tmp将指向T3的右子树第一个节点,然后判断究竟是那一边打破了平衡(必然是比较高的那一边打破平衡)。

假设是tmp的左树更高,那么就需要进行双旋转,如图:(最开始想要删除的节点已经被删除了,造成了如下的情况出现)

注:

T = DoubleRotateWithRight(T);//右树双旋转

这些旋转函数都将返回旋转之后的新根。

其他情况也是相同,判断是否旋转,并判断应该选择哪一种旋转。

且在每一轮的递归里,都重新计算了高度。

至此,整个函数完成了删除节点的全部流程。


"The unexamined life is not worth living."