Comments 18
UFO just landed and posted this here
Да, это так. Хотя код все же посложнее, чем везде в примерах интернете, когда исходят из условия «пусть все ключи разные». Но ничего, за часок сообразить можно, эти 2 фукнции получаются в 2 раза длиннее и того суммарно строк 15 каждая.
Меня вы можете не уговаривать :) к тому же декартовы деревья обладают различными полезными плюшками, да и работают, я подозреваю, чуть быстрее. Скажем так, на мой взгляд рандомизированные деревья проще в концепции, потому что оперируют двумя очевидными понятиями — ключ и размер. А вот в декартовых деревьях вместо размера используется «какой-то непонятный» приоритет…
Отличная статья :) Написало бы кто нибудь про сплей деревья. Вот они крутые :)
1984 на картинке случайное совпадение интересно?
offtopic:
Совпадение с чем? Вы родились в этот год? :)) Может это знак?
Там еще у чувака в руке табличка с номером 2513.
Персонаж на рисунке видимо из алисы в зазеркалье, куда он повернут однозначно не скажешь.
А если по теме, классно все расписано, очень не хватает таких статей.
Совпадение с чем? Вы родились в этот год? :)) Может это знак?
Там еще у чувака в руке табличка с номером 2513.
Персонаж на рисунке видимо из алисы в зазеркалье, куда он повернут однозначно не скажешь.
А если по теме, классно все расписано, очень не хватает таких статей.
Это был намек на 1984.
А существует аналогичная техника для недвоичных (сильно ветвящихся) деревьев, типа индексов в базе данных?
Имеются 2-3-4 деревья с максимум тремя ключами в узле, тоже кстати сбалансированные. Про общий случай не слышал…
В функции find, if ( k = p->key ) это хитрое присваивание или опечатка?
Однако описание вставки заняло у вас существенно больше, чем треть страницы :-)
За статью спасибо, интересно. Skip-list'ы сразу вспомнились…
За статью спасибо, интересно. Skip-list'ы сразу вспомнились…
Это потому, что я рассказывал сразу про все дерево. Если есть база — реализованное двоичное дерево поиска (поиск, два вида вставки, удаление, как у Седжвика сделано), то надо объяснить только рандомизацию, на это как раз и уходит пол-страницы. :) Кстати, по поводу списков с пропусками — в видео-лекции (кажется вот в этой) Erik Demaine говорил, что эти списки самая простая реализация сбалансированных деревьев. Как-то мне в это не верится! По сравнению с красно-черными деревьями это может и так, но те же декартовы деревья нмв на много проще реализуются!
UFO just landed and posted this here
интересно, а что получится, если получение случайного числа заменить на инвертирование глобальной булевой переменной? right = !right;
if( right) { p->right = join(p->right,q);…
if( right) { p->right = join(p->right,q);…
Sign up to leave a comment.
Рандомизированные деревья поиска