Это потому, что я рассказывал сразу про все дерево. Если есть база — реализованное двоичное дерево поиска (поиск, два вида вставки, удаление, как у Седжвика сделано), то надо объяснить только рандомизацию, на это как раз и уходит пол-страницы. :) Кстати, по поводу списков с пропусками — в видео-лекции (кажется вот в этой) Erik Demaine говорил, что эти списки самая простая реализация сбалансированных деревьев. Как-то мне в это не верится! По сравнению с красно-черными деревьями это может и так, но те же декартовы деревья нмв на много проще реализуются!
Меня вы можете не уговаривать :) к тому же декартовы деревья обладают различными полезными плюшками, да и работают, я подозреваю, чуть быстрее. Скажем так, на мой взгляд рандомизированные деревья проще в концепции, потому что оперируют двумя очевидными понятиями — ключ и размер. А вот в декартовых деревьях вместо размера используется «какой-то непонятный» приоритет…
Если это вот этот алгоритм, то «Its average case complexity is considered to be O(nlogn), whereas in the worst case it takes O(n2) (quadratic)»… Может он самый быстрый в том же смысле, что и быстрая сортировка? Ссылкой не поделитесь? Нашел оригинальную статью.
Мощно! Справедливости ради, не сомневаюсь, что приведенный выше питоновский код можно существенно подсократить, просто цель моего поста — объяснение алгоритма, а не демонстрация возможностей языка программирования :) В любом случае спасибо за ссылку, записал ее в избранное…
Я, пока пост готовил, тоже успел придумать суперэффективный алгоритм, при ближайшем рассмотрении оказалось, что это просто-напросто усложненная версия алгоритма Джарвиса :)
Ага, неравенство треугольника я и имел в виду, когда писал про «очевидность» выпуклости. Думаю, что при строгом доказательстве для произвольных кривых возникнут некоторые трудности, нет? Для ломаных линий (т.е. для многоугольников, в контексте рассматриваемой темы) это не проблема, согласен…
Ссылкой не поделитесь?Нашел оригинальную статью.Либо ключ (вернее, функцию сравнения) слегка изменить:
Работают оба варианта. А функция cmp_to_key, как написано по вашей ссылке, должна входить в модуль functools.