java - 低效二叉搜索树平衡算法

Question

我正在开发一个使用二叉搜索树的项目。该项目要求我创建一个名为 isBalanced 的方法，用于检查二叉搜索树是否在容差范围内平衡。我能够弄清楚如何做到这一点，但速度非常慢。我想知道是否有人有任何技巧可以提高效率。顺便说一句，如果子项为 null，.getLeftChild() 和 .getRightChild() 必须返回 IllegalStateExceptions。我个人更希望他们返回 null。

这是我的代码片段:

@Override
public <T> int getDepth(BinaryTreeNode<T> root) {
    return recDepth(root,0);
}

public <T> int recDepth(BinaryTreeNode<T> root,int depth) {
    int leftTree,rightTree;
    if(!root.hasLeftChild()&&!root.hasRightChild()) return depth;

    if(!root.hasLeftChild()) leftTree = 0;
    else                     leftTree = recDepth(root.getLeftChild(),depth+1);

    if(!root.hasRightChild()) rightTree = 0;
    else                      rightTree = recDepth(root.getRightChild(),depth+1);

    if(rightTree>leftTree) return rightTree; 
    else                   return leftTree;
}

@Override
public <T> boolean isBalanced(BinaryTreeNode<T> root, int tolerance) {
    if(tolerance<0) throw new IllegalArgumentException("Can't have negative tolerance");
    if(root==null) throw new NullPointerException();
    return recBalanced(root,tolerance);
}

public <T> boolean recBalanced(BinaryTreeNode<T> root, int tolerance){
    try{
    if(Math.abs(getDepth(root.getLeftChild())-getDepth(root.getLeftChild()))<=tolerance){
        return recBalanced(root.getLeftChild(),tolerance)&&recBalanced(root.getRightChild(),tolerance);
    }else return false;
    } catch (IllegalStateException e){
        if(root.hasLeftChild()&&getDepth(root.getLeftChild())>tolerance-1) return false;
        else if(root.hasRightChild()&&getDepth(root.getRightChild())>tolerance-1) return false;
        else return true;
    }
}

预先感谢您的帮助。

Answer 1

您的效率问题来自于这样的事实:您多次遍历相同的元素来计算子树的深度，然后计算其右子树和左子树的深度。

当你遇到这样的重叠问题，并且可以通过更小的问题来推断时，你的脑海中一定会响起一个铃声:动态规划。您可以计算 BinaryTreeNode<Integer> ，它将包含每个对应节点的深度(该树将具有与原始树相同的形状)。然后，您只需遍历该树一次即可执行计算，总时间复杂度为 O(n) (但是使用了 O(n) 的内存)。

public BinaryTreeNode<Integer> computeDepthTree(BinaryTreeNode<T> bt) {
    return computeDepth(bt,0);
}

public BinaryTreeNode<Integer> computeDepthTree(BinaryTreeNode<T> bt, int depth) {
    BinaryTreeNode<Integer> result = new BinaryTreeNode<>(depth);
    if (bt.getLeftNode() != null)
        result.setLeftNode(computeDepthTree(bt.getLeftNode(),depth + 1));

    if (bt.getRightNode() != null)
        result.setRightNode(computeDepthTree(bt.getRightNode(),depth + 1));

    return result;
}

计算出这棵树后，当遍历给定节点时，您将可以访问其 O(1) 中的深度。因此，同一父节点的子节点之间的深度比较将很便宜!