Что не так с моим методом удаления дерева AVL? - PullRequest
Новая
       39

Что не так с моим методом удаления дерева AVL?

0 голосов
/ 03 сентября 2018 
if(t == null) //If search is complete and no element is found
    {
        return null;
    }
    else
    {
        if(x < t.data)
            t.left = delete(t.left, x);
        else if(x > t.data)
            t.right = delete(t.right, x);
        else if(t.left != null && t.right != null)
        {
            TreeNode temp = findMax(t.left);
            t.data = temp.data;
            t.left = delete(t.left, temp.data);
        }
        else
        {
            TreeNode child = null;
            if(t.left == null)
                child = t.right;
            if(t.right == null)
                child = t.left;
            return child;
        }

        t.height = Math.max(height(t.left), height(t.right)) + 1; //Update the height of TreeNodes
        t = balanceTree(t);

        return t;
    }
private TreeNode balanceTree(TreeNode t)
{
    if(getBalance(t) > 1) 
    {
        if (getBalance(t.left) >= 0)
            return singleRotateLeftToRight(t);
        else
            return doubleRotateLeftToRight(t);
    }
    else 
    {
        if (getBalance(t) < -1)
        {
            if (getBalance(t.right) <= 0)
                return singleRotateRightToLeft(t);
            else
                return doubleRotateRightToLeft(t);
        }
    }

    return t;
}
public static void main(String[] args)
{
    AVLTree v = new AVLTree();
    v.insert(50);
    v.insert(40);
    v.insert(35);
    v.insert(37);
    v.insert(34);
    v.insert(55);
    v.insert(60);
    v.insert(54);
    v.insert(53);
    v.insert(52);
    v.insert(5);
    v.insert(4);
    v.insert(3);
    v.delete(40);
    v.delete(35);
    v.delete(37);
    v.delete(53);
    v.delete(60);
    v.insert(2);
    v.insert(6);
    v.delete(34);
    v.delete(6);
    v.delete(50);
    v.delete(4);
    v.delete(3);
    v.delete(2);






}
private TreeNode singleRotateLeftToRight(TreeNode k1) // (Utility Method) Performs single rotation of a TreeNode from left to right
{ 
    TreeNode k2 = k1.left;
    k1.left = k2.right;
    k2.right = k1;
    k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
    k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
    return k2;
}

private TreeNode singleRotateRightToLeft(TreeNode k1) //(Utility Method) Performs single rotation of a TreeNode from right to left
{ 
    TreeNode k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;
    k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
    k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
    return k2;
}

private TreeNode doubleRotateLeftToRight(TreeNode k1) //(Utility Method) Performs double rotation of a TreeNode from left to right
{ 
    k1.left = singleRotateRightToLeft(k1.left);
    return singleRotateLeftToRight(k1);
}

private TreeNode doubleRotateRightToLeft(TreeNode k1) //(Utility Method) Performs double rotation of a TreeNode from right to left
{ 
    k1.right = singleRotateLeftToRight(k1.right);
    return singleRotateRightToLeft(k1);
}

private int getBalance(TreeNode t) { //Returns the difference between the height of the left TreeNode and right TreeNode (utility method)
    if(t == null)
        return -1;
    return height(t.left) - height(t.right);
}

код вставки работает нормально, но когда дело доходит до удаления, возникают проблемы, как будто некоторые узлы дерева исчезают, и я уверен, что коды поворота в порядке, но что не так с моим кодом, когда я удаляю узел дерева с 2 узлами с 54 и 55 отсутствуют, и я почти уверен, что с удалением проблем нет, но должно быть с поворотами, или, может быть, я балансирую не на тех узлах, которых не знаю.

...