1

所以我用Java编写了一个BST的实现。我的目标是使其平衡，更准确地说是 AVL 树。我遇到了一些问题，我不知道如何实现 trinodeRestructering 方法（即平衡树的方法）我尝试了各种方法，但这些指针有时很难处理，我不知道该怎么做递归地。下面是我添加新元素的代码以及检查我们是否在树中超过 2 步差异的方法。

添加和平衡方法：

private TreeNode insert(TreeNode currN, TreeNode newN) {
    if (currN == null) {
        return newN;
    }

    if (currN.getData() == newN.getData()) {
        throw new IllegalArgumentException("Value already exists.");
    }

    if (newN.getData() < currN.getData()) {
        if (currN.getLeft() == null) {
            currN.setLeft(newN);

        } else {
            insert(currN.getLeft(), newN);
        }
    } else {
        if (currN.getRight() == null) {
            currN.setRight(newN);

        } else {
            insert(currN.getRight(), newN);
        }
    }

      if (needBalancing()) {
          trinodeRestructering(currN);
      }           

    return currN;
}

private TreeNode trinodeRestructering(TreeNode currN) {
//Not sure what to do here.
    return currN;
}

高度检查方法。

    public boolean needBalancing(){
    if(height(root) == -1){ // true if we need to balance
        return true;
    }else{
        return false;
    }
}

private int height(TreeNode node){
    if (node == null)
        return 0;
    int left = height(node.getLeft());
    int right = height(node.getRight());

    if (left == -1 || right == -1)
        return -1;

    if (Math.abs(left - right) > 1) {
        return -1;
    }

    return Math.max(left, right) + 1;
}

我可能会补充说我有一个工作 inOrder 方法，也许我可以用它来平衡我的树？

4

0 回答 0