Splay дерево с нечетным числом поворотов

9

При вставке элемента в дерево сопряжения повороты выполняются парами на основе зигзагообразного или зигзагообразного рисунка. Когда нужно выполнить нечетное количество поворотов, можно либо сделать дополнительное вращение, начиная с листа, либо сохранить дополнительное вращение и сделать это в корне. Это имеет значение?

Например, в прикрепленном изображении я вставляю 4 в BST и «вставляю» его в корень. В верхней части рисунка я сначала нахожу зигзагообразную пару в листовом узле и выполняю зигзагообразную растяжку снизу, оставляя последний поворот вправо в корне. В нижней части рисунка я сначала делаю странное вращение, начиная с листа, а затем делаю зигзагообразное растяжение до корня.

Что правильно? Или оба приведут к обычной производительности Splay-Tree?

два способа раскраски для нечетного числа вращений

wcochran
источник

Ответы:

4

1+3(р(T)-р(Икс))Tр(U)знак равножурнал(вес Uподдерево)Φ(T)знак равноΣИкс узел Tр(T)

В доказательстве леммы о доступе рассматривается стоимость одной операции зиг / зиг-зиг / зиг-зиг и т. Д. Ты получаешь

  1. 1+3(р+(U)-р(U))р+U

  2. 3(р+(U)-р(U))

1+3(р(T)-р(Икс))

Если вы измените порядок поворотов, вы получите ту же сумму. Единственное отличие состоит в том, что теперь «+1» происходит от первого вращения, а не от последнего вращения. Вы могли бы даже сделать вращение зигзага в середине. Весь дальнейший (классический) анализ опирается на лемму доступа.

Однако причина, по которой вы выполняете одно вращение в последнюю очередь, заключается в том, что вы не знаете заранее, является ли глубина узла четной или нечетной.

A.Schulz
источник