algorithm - 插入操作时 AVL 树 : adding a new field to each node : the "size" of its tree ,

Question

我试图在将新元素插入 AVL 树时更新 Insert 操作。insert 操作的更新将向每个节点添加其根树的大小。

现在，由于我是自下而上插入元素的，所以如果我只是为向上巡视时经过的每个节点添加一个 +1，那么在某些情况下这是行不通的，因为例如，当我需要在新树不平衡后平衡树时，因为我更改了指针，那么计算将不正确。

任何想法或提示我怎样才能正确地做到这一点？

Answer 1

一个简单的解决方案可能是用大小的定义简单地修改它。

给叶子 size = 1，并且对于每个节点，它是根之旅的一部分，或者是滚动(从底部向上)集合的一部分:

size(v) = size(v.left) + size(v.right) + 1
            ^                 ^          ^
        size of left     size of right   size of "root"
           subtree        subtree     

这是正确的，因为您在每个步骤中都修改了所有已更改的顶点，并且由于您是自下而上进行的，因此可以为您修改的每个节点正确计算大小。

请注意，它不会影响复杂性，因为对于每个这样的顶点 - 您正在执行恒定数量的 OP，并且您只对无论如何都会遍历的顶点执行此操作。