2

Добрый день!

Я новичок и пытаюсь сейчас реализировать декартово дерево поиска на python. Нужно написать несколько реализаций: - RandomTreap: использование рандомных переменных в качестве приоритетов - DynamicTreap: когда при каждом обращении к элементу его приоритет повышается и дерево переструктурируется, таким образом элементы с наибольшей частотой обращения передвигаются наверх. При первом внедрении элемента его приоритет равен 1.

Идеи: У меня уже есть реализация бинарного дерева поиска на питоне, имею представление, как написать функции поворота дерева. Опираясь на реализацию бинарного дерева, можно ее видоизменить, добавив атрибут priority. И изменить функцию insert: если ключа еще нет в дереве, то он добавляется как, как в бинарном дереве, а потом дерево поворачивается. Если ключ есть, то в RandomTreap ничего не происходит, а в DynamicTreap приоритет увеличивается на 1 и дерево поворачивается.

Просьба: Мне пока сложно написать все это сразу, поэтому предварительно хотелось бы почитать хорошие описания/ частичную реализацию на питоне, чтобы во всем хорошенько разобраться. Увы, похоже, что из-за скорости декартовы деревья поиска обычно не пишут на пионе, и я не могу найти в интренете почти ничего хорошего. Может быть, кто-то может посоветовать хорошие ссылки?

Заранее огромное спасибо!!!

1
  • Поглядите сайты algolist.ru, e-maxx.ru, infomatics.mccme.ru 21 сен 2017 в 8:46

1 ответ 1

1

Ознакомиться с созданием различных куч и деревьев можно по книге Problem Solving with Algorithms and Data Structures, рабочая ссылка на перевод: http://aliev.me/runestone/index.html

Про декартовы деревья хорошая статья, где описана реализация методов: http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_cartesian.pdf.

Надеюсь я вам хоть немного помог.

1
  • Деннис, огромное спасибо! :)
    – TatjanaCh
    7 июн 2017 в 15:17

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.