1

我正在尝试实现 AVL 树，但重新平衡方法似乎无法正常工作。如果错误出在轮换方法或重新平衡本身，则 IDK。这是代码。

包 adt.avltree；

导入 adt.bst.BSTImpl；导入 adt.bst.BSTNode；

公共类 AVLTreeImpl> 扩展 BSTImpl 实现 AVLTree {

//TODO Do not forget: you must override the methods insert and remove conveniently.

@Override
public void insert(T element) {
    insertRecursive(root, element);
}

private void insertRecursive(BSTNode<T> node, T element) {
    if (node.isEmpty()) {
        node.setData(element);
        node.setLeft(new BSTNode<T>());
        node.setRight(new BSTNode<T>());

    } else {
        if (element.compareTo(node.getData()) < 0) {
            insertRecursive((BSTNode<T>) node.getLeft(), element);
            node.getLeft().setParent(node);
        } else if (element.compareTo(node.getData()) > 0) {
            insertRecursive((BSTNode<T>) node.getRight(), element);
            node.getRight().setParent(node);
        }
        rebalance(node);
    }

}

//AUXILIARY
protected int calculateBalance(BSTNode<T> node){
    if (!node.isEmpty())
        return height((BSTNode<T>) node.getLeft()) - height((BSTNode<T>) node.getRight());
    return 0;
}

//AUXILIARY
protected void rebalance(BSTNode<T> node){
    int balance = calculateBalance(node);
    if (Math.abs(balance) > 1) {
        if (balance == 2) {
            if (calculateBalance((BSTNode<T>) node.getLeft()) == -1)
                leftRotation((BSTNode<T>) node.getLeft());
            rightRotation(node);
        } else if (balance == -2) {
            if (calculateBalance((BSTNode<T>) node.getRight()) == 1)
                rightRotation((BSTNode<T>) node.getRight());
            leftRotation(node);
        }
    }
}

//AUXILIARY
protected void rebalanceUp(BSTNode<T> node){
        // TODO Auto-generated method stub
}

//AUXILIARY
protected void leftRotation(BSTNode<T> node){
    BSTNode<T> pivot = (BSTNode<T>) node.getRight();
    node.setRight(pivot.getLeft());
    node.getRight().setParent(node);
    pivot.setLeft(node);
    pivot.setParent(node.getParent());
    node.setParent(pivot);
    if (node.equals(root))
        root = pivot;
    node = pivot;
}

//AUXILIARY
protected void rightRotation(BSTNode<T> node){
    BSTNode<T> pivot = (BSTNode<T>) node.getLeft();
    node.setLeft(pivot.getRight());
    node.getLeft().setParent(node);
    pivot.setRight(node);
    pivot.setParent(node.getParent());
    node.setParent(pivot);
    if (node.equals(root))
        root = pivot;
    node = pivot;
}


public static void main(String[] args) {
    AVLTreeImpl<Integer> teste = new AVLTreeImpl<Integer>();
    teste.insert(2);
    teste.insert(5);
    teste.insert(3);
    System.out.println(teste.getRoot().getData());
    System.out.println(teste.getRoot().getLeft().getData());
    System.out.println(teste.getRoot().getRight().getData());

}

}

它应该打印 3 2 5 但它打印 5 2 null

4

0 回答 0