0

对于我的 AVL 树实现，我有一个节点，它有一个左、右和父指针，以及一个平衡变量。每次我插入一个新节点并执行所需的旋转时，我都会通过从左子树中减去右子树来更新余额。这种有问题的方法递归地调用自身来计算高度。

有问题的方法：

private int getHeight(Node nd){
    if (nd != null){
        if (nd.getLeft() == null && nd.getRight() == null)
            return 0;
        else if (nd.getLeft() == null)
            return getHeight(nd.getRight()) + 1;
        else if (nd.getRight() == null)
            return getHeight(nd.getLeft()) + 1;
        else
            return Math.max(getHeight(nd.getLeft()), getHeight(nd.getRight())) + 1;
    }
    else return -1;
}

我的问题是，由于 AVL 树插入时间复杂度是O(log n)，我认为这种方法会影响这个时间复杂度。可以做些什么来修改它？

4

3 回答 3

1

提示：您不需要高度来计算新天平。节点及其左右子节点的旧余额值就足够了。

于 2013-01-14T08:04:37.460 回答
1

你不需要高度。知道旧的平衡，您可以保持平衡。也就是说，如果您还没有编写轮换，您可能需要调整轮换，以便在每次“移动”时保持平衡更新。

于 2013-01-14T08:07:29.727 回答
1

您不需要计算每个插入中所有节点的平衡因子。

您只需要计算插入节点的父节点，以及它们的父节点，同时您到达平衡为 2 或 -2 的节点，然后旋转它们。

如果您不知道如何以这种方式旋转主题（哪种旋转适合）请告诉我

于 2013-01-14T19:12:03.637 回答