为 AVL Tree 实现 REMOVE 方法

Question

5。创建一个删除方法。如果找到该项目，请搜索树，然后将其杀死。然后，您必须以 AVL 方式平衡树，以正确填充您制作的洞。再次，使用维基百科描述（非常好）和模拟器，甚至可能是我的讲座，以使删除正常工作。我不会提供这方面的样本数据——此时您可以自己弄清楚。请记住，除了一般情况外，您还有两个需要双旋转的特殊情况（请参阅讲座或使用模拟器来了解您遇到 left/right 或 right/left 情况的情况。）

现在我需要实现这个功能

public void remove(K input)

帮助我。我已经做到了

public void remove(K input) {
    root = remove(root,input);
}

public AVLNode<K> remove(K x, AVLNode<K> t) {
    if (t==null)    { 
        System.out.println("Sorry but you're mistaken, " + t + " doesn't exist in this tree :)/>\n");
        return null;
    }
    System.out.println("Remove starts... " + t.data + " and " + x);
    if (x.compareTo(t.data) < 0 ) {
        t.left = remove(x,t.left);
        int l = t.left != null ? getHeight(t.left) : 0;

        if((t.right != null) && (getHeight(t.right) - l >= 2)) {
            int rightHeight = t.right.right != null ? getHeight(t.right.right) : 0;
            int leftHeight = t.right.left != null ? getHeight(t.right.left) : 0;

            if(rightHeight >= leftHeight)
                t = rotateLeft(t);              
            else
                t = rotateRight(t);//double
        }
    }
    else if (x.compareTo(t.data) > 0) {
        t.right = remove(x,t.right);
        int r = t.right != null ? getHeight(t.right) : 0;
        if((t.left != null) && getHeight(t.left) - r >= 2) {
            int leftHeight = t.left.left != null ? getHeight(t.left.left) : 0;
            int rightHeight = t.left.right != null ? getHeight(t.left.right) : 0;
            if(leftHeight >= rightHeight)
                t = rotateRight(t);             
            else
                t = rotateLeft(t);//and double
        }
    }
    return t;

} //End of remove...

Answer 1

nvm 找到了答案

private AVLNode<K> findMin( AVLNode<K> t )
{
    if( t == null )
        return t;

    while( t.left != null )
        t = t.left;
    return t;
}
public void remove( K x )
{
    root = remove( x, root );
}
private AVLNode<K> remove( K x, AVLNode<K> t )
{
    if( t == null )
        return t;   // Item not found; do nothing

    int compareResult = x.compareTo( t.data );

    if( compareResult < 0 )
        t.left = remove( x, t.left );
    else if( compareResult > 0 )
        t.right = remove( x, t.right );
    else if( t.left != null && t.right != null ) // Two children
    {
        t.data = findMin( t.right ).data;
        t.right = remove( t.data, t.right );
    }
    else
        t = ( t.left != null ) ? t.left : t.right;
    return t;
}

为 AVL Tree 实现 REMOVE 方法

Implement REMOVE method for AVL Tree

java

avl-tree