Дерево 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, и вы делаете это только для вершин, которые вы бы в любом случае прошли.