avltree 算法设计思路.txt

数据结构课作业 AVLTree算法 附带算法讲解

设计：
	AVLTree模板类有两个参数类型，第一个是E 就是element，也就是元素的类型；第二个K就是KeyWord，也就是元素对象里面的一个属性、关键字的类型。
#########################################################################################
算法：
	删除部分的算法基本上和插入算法差不多，利用递归调用寻找被删除的结点，通过shorter判断是否需要继续验证、通过balance判断是否需要旋转。
*****************************************************************************************
	首先，如果被删除的结点有两个子树，那就找到这个结点的直接后继并把后继的element保存起来，从当前结点开始递归寻找并删除直接后继，然后把保存的直接后继的值赋给当前结点。也就是说，实际上被删除的结点绝对是“最多只有一个子树”的结点。
*****************************************************************************************
	如果当前结点是要被删除的结点，首先从树的根开始重新搜索一次以便找到它的父结点，把当前结点保存进指针q，父结点保存进指针p，然后把当前结点唯一的一个子结点保存到一个指针c里（如果没有子结点，c就为空）。如果q是根结点，那么就把c变成新的根结点；否则，用c替换父结点p里q的位置，然后删除q，（注意是删除q而不是删除“当前结点”tree——尽管多数情况下他们是一样的）并把q置空。(删除q而不是删除tree的原因是：由于Delete方法里，“当前结点”这个参数是引用传入的，所以如果删除的是tree而不是q，那当tree为根结点时就会出麻烦了。因为前面已经把根结点(root)变成了c，也就是说tree即root已经是c指向的结点、并不是q指向的结点了，删除tree不就把新的root（而不是我们要删除的那个原来的root）删除了)，然后置success和shorter都为true，返回。
*****************************************************************************************
	之后就是按照递归顺序向上通过shorter判断是否需要继续算法、根据本层当前结点的balance判断是否需要旋转。
	case 1 : 当前结点的balance为0。如果缩短了的是左子树，就把balance改为1；相应的，如果是右子树缩短了就改为-1，因为当前结点为根的树没有缩短，所以 shorter 置为false。
	case 2 : 结点的balance不为0，且较高的子树被缩短，则 p 的balance改为0，同时 shorter 置为True（其实本来就是true，不变就可以了）。返回到上层方法继续判断。
	case 3 : 结点的balance不为0，且较矮的子树又被缩短，则在结点发生不平衡。调用相应的平衡函数进行旋转、相应地修改balance和shorter。
	举左边作为例子来说吧，右边只不过是“镜象算法”，就不多说了。
	如果当前结点的左子树比较矮、而左子树又被缩短了，则调用DeleteLeftBalance进行判断
	令rightSub指向Tree->right (该子树本来就高，而且未被缩短),判断rightSub->balance
	case 0:rightSub->balance变为-1（只有这一种可能），执行一个左旋转。因为这种情况下树并没有变短了，所以把shorter置为false;
	case 1:Tree->balance = rightSub->balance = 0;执行一个左旋转。因为这种情况下的树变短了，所以不改变shorter(本来就是true);
	case -1:把rightSub->left保存进leftSub,根据leftSub->balance的值有三种旋转后balance的结果：
			switch(leftSub->balance){
				case 1:Tree->balance = -1;
					rightSub->balance = 0;
					break;
				case 0:
					Tree->balance = rightSub->balance = 0;
					break;
				case -1:
					Tree->balance = 0;
					rightSub->balance = 1;
					break;
			}
	无论那种情况，最后leftSub->balance肯定会变成0，所以置0;然后进行两次旋转：
			RotateRight(rightSub,Tree->right);
			RotateLeft(Tree,Tree);
	因为这样旋转之后本树肯定变短了，所以shorter不变，仍然是true,返回上层继续判断。
*****************************************************************************************
要点：Delete方法，传入当前结点的时候必须用引用传入，原因在于：
我们的左旋转(RotateLeft)和右旋转(RotateRight)方法有两个参数，第一个参数是一个“复制传入”的值（和实参并不是同一个，但是内容相同），第二个参数是一个“引用传入”的值（和实参就是同一个，只不过名字不同），左旋转和右旋转之后的新的树的根结点会被保存在第二个参数里，也就是作为第二个参数的实参会指向旋转之后的新树的根。
如果我们在Delete方法里的参数不是引用传入、而是复制传入的话，在Delete方法里调用了左旋转和右旋转之后，经过了旋转的树的根尽管通过Delete方法里的这个“复制实参指针”的值得到的形参指针可以找到，但是要注意这只是一个复制得到的形参，它和调用Delete方法时的实参并不是同一个指针，只不过这两个指针指向的地址相同而已。这样的后果就是，Delete方法结束之后，形参会被“销毁”，而实参根本没有指向新的树的根、仍然还是指向原来的地方，当然就会造成找不到树的情况。