При вставке дерево AVL не вращается.

[RonakJain]

Я пытался сначала добавить 0, затем 1, затем 2, но всегда терпит неудачу, когда я добавляю 2. Когда я добавляю 2, вместо поворота влево и 1 становится новым корнем, корень остается 0. Я не думаю, что это проблема с моими процедурами вращения, потому что я тестировал их и еще не провалил тест.

public void updateHeight(BSTNode<T> node) {
    if (node != null) {
        int leftHeight = height(node.getLeft());
        int rightHeight = height(node.getRight());
        int realHeight = Math.max(leftHeight, rightHeight) + 1;
        node.setHeight(realHeight);
    }
}

public int balanceFactor(BSTNode<T> node) {
    if (node == null)
        return 0;
    return height(node.getRight()) - height(node.getLeft());
}

public BSTNode<T> rotateLeft(BSTNode<T> node) {
    BSTNode<T> rightNode = node.getRight();
    BSTNode<T> rightLeftNode = rightNode.getLeft();

    node.setRight(rightLeftNode);

    if (rightLeftNode != null)
        rightNode.getLeft().setParent(node);
    rightNode.setLeft(node);

    rightNode.setParent(node.getParent());
    node.setParent(rightNode);

    if (rightNode.getParent() != null && node.getData().compareTo(rightNode.getParent().getData()) > 0)
        rightNode.getParent().setLeft(rightNode);
    else if (rightNode.getParent() != null)
        rightNode.getParent().setRight(rightNode);

    updateHeight(node.getRight());
    updateHeight(node.getLeft());
    updateHeight(node);
    updateHeight(node.getParent());

    return rightNode;
}

public BSTNode<T> rotateRight(BSTNode<T> node) {
    BSTNode<T> leftNode = node.getLeft();
    BSTNode<T> leftRightNode = leftNode.getRight();

    if (leftRightNode != null)
        leftNode.getRight().setParent(node);

    node.setLeft(leftRightNode);
    leftNode.setRight(node);

    leftNode.setParent(node.getParent());
    node.setParent(leftNode);

    if (leftNode.getParent() != null && node.getData().compareTo(leftNode.getParent().getData()) > 0)
        leftNode.getParent().setLeft(leftNode);
    else if (leftNode.getParent() != null)
        leftNode.getParent().setRight(leftNode);

    node = leftNode;
    updateHeight(node.getRight());
    updateHeight(node.getLeft());
    updateHeight(node);
    updateHeight(node.getParent());

    return node;
}

public void add(T t) {
    BSTNode<T> newNode = new BSTNode<T>(t, null, null);
    if (root == null)
        root = newNode;
    else
        addHelper(root, newNode);
}

private void addHelper(BSTNode<T> currNode, BSTNode<T> newNode) {
    if (currNode == null)
        return;
    if (newNode.getData().compareTo(currNode.getData()) < 0) {
        if (currNode.getLeft() == null) {
            currNode.setLeft(newNode);
            newNode.setParent(currNode);
        } else
            addHelper(currNode.getLeft(), newNode);
    } else {
        if (currNode.getRight() == null) {
            currNode.setRight(newNode);
            newNode.setParent(currNode);
        } else
            addHelper(currNode.getRight(), newNode);
    }

    int balance = balanceFactor(currNode);
    System.out.println(newNode.getData() + " " + currNode.getData() + " " + balance);

    if (balance < -1) {
        if (balanceFactor(currNode.getLeft()) > 0) {
            rotateLeft(currNode.getLeft());
        }
        rotateRight(currNode);
    } else if (balance > 1) {
        if (balanceFactor(currNode.getRight()) < 0) {
            rotateRight(currNode.getRight());
        }
        rotateLeft(currNode);
    }

    updateHeight(currNode);
}

Я не уверен, что происходит не так. Я прочитал эту статью от scaler, чтобы узнать об этом больше. Мне также непонятно, почему оператор печати выводит дважды при добавлении 2 по какой-то причине.

[danil11]

Useful Information Are Providing In Thise Post