Добрый день!
Скорее всего Вы когда-либо слышали про 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
Из поста можно было сделать вывод, что функция
add_slowво всём лучше функцииadd(высота не увеличилась, значит, скорость работы такая же, при этом кода гораздо меньше!)На самом деле у
вращений на каждый запрос.
add_slowесть один минус:addделает не более одного вращения (маленького или большого), аadd_slowв худшем случае будет делатьА переведи пост на английский язык, может, кто-нибудь из англоязычных участников что-нибудь подскажет. Например, говорят, пользователь Darooha кое-что смыслит во вращениях бинарных деревьев.
Дело предлагаешь. Вообще, вопрос интересный. На главную отправим — может правда кто-то напишет что-то умное.
Готово.
P.S. Как-то тяжело перевод пошёл... Кстати, в англоязычной литературе я не нашёл понятия "большое вращение", "малое вращение". UPD: Мне таки объяснили, что есть "double rotation" и "rotation".