AVLTree.zip_平衡树

我的实现思路： 采用递归实现删除算法，将待删除的元素值与当前结点的元素值进行比较，分几种情况： 1.当前结点为空，则删除失败，返回 2.待删除的元素值比当前结点的元素值小，则采用递归删除当前结点的左子树上的点，且要返回一个表示它的左子树在执行删除操作之后是否变短的变量shorter。如果变短了，则要讨论当前结点在不同的平衡因子（删除前的平衡因子）下平衡因子的变化，若bF为0，则置为-1；若为1，则置为0；若为-1，则要进行左旋操作。 3.待删除的元素值比当前结点的元素值大，则删除当前结点的右子树上的点，与情况2类似。 4.待删除的元素值就是当前结点的元素值，这又要分几种情况讨论： ①当前结点的左右子树均为空，即为叶子结点，则只要把该点删除即可，shorter置为true ②当前结点的左右子树均不为空，即有两个孩子，此时要寻找该节点在中序遍历下的后继结点，即它的右子树中第一个被访问的结点。找到该结点后，将该结点的元素值与待删除的元素值交换，然后继续采用递归从当前结点的右孩子开始删除该元素，返回后仍然要分情况讨论平衡情况。这就转变成了删除只有一个孩子的结点或者叶子结点的简单情况。 ③当前结点的左子树或右子树为空，则只需要把其左子树或右子树提上来，将shorter置为true。 在删除操作的过程中，因为采用了递归，所以可以记录下路径上结点的bF和shorter，有效得调整了树的平衡。 删除的左旋操作：（删除一个结点的左子树上的一个结点，使得左子树矮，向左旋转） 在shorter为true的情况下： 若结点的平衡因子值为0，则在做相应旋转后将其置为-1，但树并没有变矮 若结点的平衡因子为1，则做旋转后将其置为0，树变矮，shorter=false 若结点的平衡因子为-1，则要坐双向旋转，shorter=true 删除的右旋操作：（与左旋类似） 具体细节见源程序