В дереве Splay (сверху вниз), как мне поддерживать инварианты узлов?

Question

Я пытаюсь реализовать дерево Splay с воспроизведением сверху вниз, как описано здесь (http://www.nocow.cn/index.php/Code:Splay_Tree/C) (первый). Я уже реализовал восходящую версию, которая также поддерживает размер поддерева на каждом узле, где поддерево является корнем в этом узле (т. Е. Size = 1 + left-> size + right-> size).

Как и в каждой операции разворота, я перемещал узел вверх до корня, нет необходимости обновлять всех предков с каждым вращением. Но теперь в нисходящей версии я не понимаю, как поддерживать это значение размера поддерева на каждом узле (и других видах инвариантов) без рекурсивного обновления предков с каждым вращением.

Короче говоря, как я могу поддерживать размер поддерева на каждом узле, когда выполняю операцию сверху вниз? (Было бы неплохо иметь модифицированную версию операции воспроизведения, описанную на упомянутой выше странице)

Answer 1

Возможно, вы ищете эту реализацию?

http://www.link.cs.cmu.edu/link/ftp-site/splaying/top-down-size-splay.c