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