Avl树实现的续

接着看删除部分，删除部分比插入要更难搞一些。对于删除，同样需要分情况讨论。
1.如果是在一个平衡节点下删除，只要把这个节点的高度信息修改就可以了
2.如果是在较长的子树下删除，就把这个节点的高度信息修改成平衡
以上两种情况都不需要进行旋转。
3.如果是在较短的子树下删除，除了更新高度信息外，还需要旋转节点。这时又分3种情况讨论。
3种情况的图如下，直接针对编程就可以了







与插入一样，删除时不必从树根开始更新，记录一个path_top即可。如果某个节点是平衡的，那么删除不会影响到它以上的节点，如果某个节点下的情况和图1相同，那么删除也不会影响到它以上的节点。这时可以把path_top设为该节点。另外，treep是指向删除节点右子树中最小的节点，如果用中序遍历，就是下个节点，将用它的值来代替删除节点。

int avl_delete(node *treep, value_t target)
{
	/* delete the target from the tree, returning 1 on success or 0 if
	 * it wasn't found
	 */
	node tree = *treep, targetn;
	node *path_top = treep;
	node *targetp = NULL;
	direction dir;
	
	while (tree) {
		dir = (target > tree->value);
		if (target == tree->value)
			targetp = treep;
		if (tree->next[dir] == NULL)
			break;
		if (Balanced(tree)
		    || (tree->longer == (1-dir) && Balanced(tree->next[1-dir]))
			) path_top = treep;
		treep = &tree->next[dir];
		tree = *treep;
	}
	if (!targetp)
		return 0;

	/* adjust balance, but don't lose 'targetp' */
	targetp = avl_rebalance_del(path_top, target, targetp);

	/* We have re-balanced everything, it remains only to 
	 * swap the end of the path (*treep == treep) with the deleted item
	 * (*targetp == targetn)
	 */
	avl_swap_del(targetp, treep, dir);

	return 1;
}

这一段代码负责重新平衡树，除了最后一个node更新之外(tree-next[dir] == NULL)，其余的都要更新高度信息，如有必要，还有旋转。

node *avl_rebalance_del(node *treep, value_t target, node *targetp)
{
	/* each node from treep down towards target, but
	 * excluding the last, will have a subtree grow
	 * and need rebalancing
	 */
	node targetn = *targetp;

	while (1) {
		node tree = *treep;
		direction dir = (target > tree->value);

		if (tree->next[dir]==NULL)
			break;

		if (Balanced(tree))
			tree->longer = 1-dir;
		else if (tree->longer == dir)
			tree->longer = NEITHER;
		else {
                        // 对比图可以看到，这个是第三幅图的场景
			if (tree->next[1-dir]->longer == dir)
				avl_rotate_3_shrink(treep, dir);
			else // 第一二幅图
				avl_rotate_2_shrink(treep, dir);
                        // 这一句的作用，用targetp本身也在旋转过程中时，需要把它更新，targetp作为旋转的顶，而且三幅图里，都是转到&(*treep)->next[dir]
			if (tree == targetn)
				targetp = &(*treep)->next[dir];
		}
                // 为什么这里是tree而不是treep?
                // 是treep也可以，但是旋转后treep是tree的，这样要多遍历一个节点
		treep = &tree->next[dir];
	}
	return targetp;
}

交换并删除的代码比较简单，如下

void avl_swap_del(node *targetp, node *treep, direction dir)
{
	node targetn = *targetp;
	node tree = *treep;

	*targetp = tree;
	*treep = tree->next[1-dir];
	tree->next[LEFT] = targetn->next[LEFT];
	tree->next[RIGHT]= targetn->next[RIGHT];
	tree->longer = targetn->longer;

	free(targetn);
}

最后是后种旋转的代码实现，都比较直观，如果对着图看。

void avl_rotate_2_shrink(node *path_top, direction dir)
{
	node D, B, C;

	D = *path_top;
	B = D->next[1-dir];
	C = B->next[dir];

	*path_top = B;
	B->next[dir] = D;
	D->next[1-dir] = C;

	if (Balanced(B)) {
		B->longer = dir;
		D->longer = 1-dir;
	} else {
		B->longer = NEITHER;
		D->longer = NEITHER;
	}
}

void avl_rotate_3_shrink(node *path_top, direction dir)
{
	node B, C, D, E, F;
	F = *path_top;
	B = F->next[1-dir];
	D = B->next[dir];
	C = D->next[1-dir];
	E = D->next[dir];

	*path_top = D;
	D->next[1-dir] = B;
	D->next[dir] = F;
	B->next[dir] = C;
	F->next[1-dir] = E;

	B->longer = NEITHER;
	F->longer = NEITHER;
	if (D->longer == dir)
		B->longer = 1-dir;
	if (D->longer == 1-dir)
		F->longer = dir;
	D->longer = NEITHER;
}