При вставке элемента в дерево сопряжения повороты выполняются парами на основе зигзагообразного или зигзагообразного рисунка. Когда нужно выполнить нечетное количество поворотов, можно либо сделать дополнительное вращение, начиная с листа, либо сохранить дополнительное вращение и сделать это в корне. Это имеет значение?
Например, в прикрепленном изображении я вставляю 4 в BST и «вставляю» его в корень. В верхней части рисунка я сначала нахожу зигзагообразную пару в листовом узле и выполняю зигзагообразную растяжку снизу, оставляя последний поворот вправо в корне. В нижней части рисунка я сначала делаю странное вращение, начиная с листа, а затем делаю зигзагообразное растяжение до корня.
Что правильно? Или оба приведут к обычной производительности Splay-Tree?
источник