Блог пользователя Burunduk1

Автор Burunduk1, 10 лет назад, По-русски

Добрый день!

Скорее всего Вы когда-либо слышали про AVL дерево. Помните, там есть большие вращения и маленькие? Большое, конечно, можно делать как два маленьких, просто оно называется большим.

Вопрос: а есть ли тест, на котором дерево, построенное без использования больших вращений, имеет высоту хотя бы на 3 большую, чем правильное AVL дерево? А если нет теста, может, можно доказать корректность такого недо-AVL? =)

Вот код на C++, в котором
функция void add( node* &t, int x ); делает правильное добавление в AVL-дерево, а
функция void add_slow( node* &t, int x ); при нарушении инварианта всегда делает малое вращение.

P.S. Ни программно, ни на бумажке у меня не получилось создать разницу высот больше двух, отсюда и вопрос.

UPD: У кого-то были проблемы скачать/прочитать код, поэтому not pastebin, short version

  • Проголосовать: нравится
  • +188
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Из поста можно было сделать вывод, что функция add_slow во всём лучше функции add (высота не увеличилась, значит, скорость работы такая же, при этом кода гораздо меньше!)

На самом деле у add_slow есть один минус: add делает не более одного вращения (маленького или большого), а add_slow в худшем случае будет делать вращений на каждый запрос.

»
10 лет назад, # |
  Проголосовать: нравится +89 Проголосовать: не нравится

А переведи пост на английский язык, может, кто-нибудь из англоязычных участников что-нибудь подскажет. Например, говорят, пользователь Darooha кое-что смыслит во вращениях бинарных деревьев.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    Дело предлагаешь. Вообще, вопрос интересный. На главную отправим — может правда кто-то напишет что-то умное.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    Готово.

    P.S. Как-то тяжело перевод пошёл... Кстати, в англоязычной литературе я не нашёл понятия "большое вращение", "малое вращение". UPD: Мне таки объяснили, что есть "double rotation" и "rotation".