algorithm - AVL 树：向每个节点添加一个新字段：其树的“大小”，同时插入操作

Question

我正在尝试Insert在将新元素插入 AVL 树时更新操作。对操作的更新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，并且您只对您本来会遍历的顶点执行此操作。