1

为我的数据结构课程编写一个 AVL 树来保存泛型；在我的 add() 方法中，在实际插入一个元素之后，我会通过它的祖先检查他们的分数。对于最初的几个添加，它可以工作，但是（大概是在确实需要进行平衡的地方），备份路径的循环无法终止。我已经尝试了我能想到的一切来确保树的父节点的根没有被设置为另一个节点或类似的东西。我将平衡分数计算为右减左，所以正数表示树右重，负数表示左重。这是我的添加（）：

public void add(T e){
    if (e == null)
        return;
    if (root == null) {
        root = new TNode<T>(null, e);
        return;
    }
    boolean added = false;
    TNode<T> current = root;
    while (current != null && added != true) {  //insertion loop
        if (current.compareTo(e) == 0)
            return;
        else if (current.compareTo(e) < 0) {
            if (current.getRight() == null) {
                current.setRight(new TNode<T>(current, e));
                added = true;
            }
            else                
                current = current.getRight();
        }   
        else if (current.compareTo(e) > 0) {
            if (current.getLeft() == null) {
                current.setLeft(new TNode<T>(current, e));
                added = true;
            }
            else
                current = current.getLeft();
        }
    }
    if (useAVL == false)
        return;

    //balancing, checking up from added node to find where tree is unbalanced; currently loop does not terminate
    //current is now parent of inserted node
    while (current.hasParent()) {       
        if (current.getAvl() > 1) {
            if (current.getRight().getAvl() > 0)
                current = rotateLeft(current);
            else if (current.getRight().getAvl() < 0) {
                current.setRight(rotateRight(current.getRight()));
                current = rotateLeft(current);
            }
        }
        if (current.getAvl() < -1) {
            if (current.getLeft().getAvl() < 0)
                current = rotateRight(current);
            else if (current.getLeft().getAvl() > 0) {
                current.setLeft(rotateLeft(current.getLeft()));
                current = rotateRight(current);
            }
        }
        current = current.getParent();
    }
    root = current;
    root.setParent(null);
}

这是正确的旋转方法：

private TNode<T> rotateRight(TNode<T> old) {
    TNode<T> oldRoot = old;
    TNode<T> newRoot = old.getLeft();
    TNode<T> rightChildNewRoot = newRoot.getRight();    //was right child of what will become root, becomes left child of old root
    newRoot.setRight(oldRoot);
    oldRoot.setParent(newRoot);
    oldRoot.setLeft(rightChildNewRoot);
    if (rightChildNewRoot != null)
        rightChildNewRoot.setParent(oldRoot);
    newRoot.setParent(oldRoot.getParent());
    return newRoot;
}
4

0 回答 0