data-structures - 如何在 O(1) 时间内返回 AVL 树的最左边节点？

Question

我的想法是：

    AVLNode minOfTree(AVLNode node) {
        while (node.left != null) node = node.left;
    return node;
    }

但是，while 循环不能是 O(1) 时间，对吧？

标签： data-structuresavl-tree

Answer 1

你是对的。从根走到最左边的节点需要 O(log N) 时间。

所以，只需在最左边的节点周围保留一个指针。每当您删除它或插入一个较小的节点时，只需再次找到最左边的节点即可。插入和删除都需要 O(log N) 时间，因此您可以花费额外的 O(log N) 时间而不会改变它们的复杂性。