Комментарии 10
Вижу, за счет чего дерево получается проще в реализации. Но за это упрощение мы чем-то расплачиваемся. Чем конкретно? Почему-то же все поголовно не заменили RBT на AAT...
Доброго времени суток) Это отличный вопрос, но к сожалению на данный момент "подводных камней" я не увидел, возможно нужно придумать какую-нибудь практическую задачу для АА-дерева и после этого что-нибудь всплывает; Если узнаю - обязательно дополню статью)
Я бы ожидал, что множитель у AA деревьев чуть хуже в асимптотиках. Т.е. все операции O(log) как и в RBT, но множитель на случайных операциях, видимо, чуть похуже - приходится чаще подниматься по дереву выше, чем в RBT.
Более опытные коллеги подсказали, что из минусов выделить можно то, что в АА-дереве в отличие от КДЧ нам необходимо в каждой ноде хранить ее высоту, тратим дополнительную память; Почему-то сам об этом не вспомнил)
Простите за нубские вопросы, но:
Почему "полезная информация в ноде" названа key? Если бы было info, shit, blabla, или на худой конец data - вопрос бы не возник :) Где так принято?
Зачем color: Literal ? Я не питонист, мож просто не знаю, там препроцессор интерпретатора сам решает, что для двух возможных вариантов надо сделать 1 байт со значениями 0..1
В статье хорошо написано "как", но не описано зачем, почему и для чего всё это. А неплохо бы раскрыть такие вопросы, иначе не "разобраться с деревьями".
Доброго времени суток)
Пойду по порядку)
Статья не несет цели заставить вас делать так и только так, она скорее разъясняет принципы работы тк лично мне показалось что материалов по теме маловато
1. Ну во всех материалах я видел что информацию в ноде называют key, но думаю это несущественно, можно назвать как угодно; Как я полагаю key пошло от того что информация ноды используется для поиска в дереве, как будто бы это некоторый "ключ" ноды, как ключ в БД :) Не уверен что это так, но моя интерпретация такова)
2. Да, тут вы правы, с точки зрения хранения информации выгоднее использовать boolean, само собой, но повторюсь что я хотел сделать упор на разъяснении принципов, а не на оптимальном решении; Лично мне показалось что код "node.color == 'red'" воспринимается лучше чем "node.is_red", поэтому я и реализовал эту вещь так, думаю это просто вкусовщина)
3. По поводу того зачем это - это отличный вопрос и хороший повод написать новую статью; Я преподаю курс по алгоритмам и мне нужно было раскрыть тему балансировок; Материалы касаемо того как деревья работают я нашел, а на придумать пример в реальной жизни к сожалению времени не хватило; Думаю в следующий раз когда буду затрагивать эту тему, попробую что-нибудь придумать и может даже собрать в статью)
Могу ответить про key. В свое время реализовывал С++ -шную map(те же словари) на КЧД в рамках учебного проекта - суть в том что по дереву производится очень быстрый поиск. Т.е. из мапы быстрее всего ищется и достается нужное значение. Поиск по ключу. )
Простите, но зачем? Если вам хочется свойств красно-черного дерева но не нравится сложность их реализации - возьмите 2-3 дерево, тем более что благодаря динамической типизации в Питоне они не должны сильно проигрывать красно-черным по производительности. Я вообще не понимаю почему везде красно-черные деревья рассказывают сразу, без того чтобы сначала изложить 2-3 деревья, ведь тогда все кажущиеся высосанными из пальца правила вставки-удаления в красно-черные деревья становятся тривиальными.
Доброго времени суток)
Кажется, эта статья не постулирует что AA-деревья это серебрянная пуля и не сравнивает разные варианты решения проблемы балансировки;
Моей задачей было скорее рассказать о том, как работает конкретно это дерево и поделиться этим материалом с остальными, возможно кому-то это сэкономит время)
Что касается 2-3 деревьев - да, было бы очень неплохо сначала рассказать о них, а после уже про КЧД, учту если буду готовить в будущем материалы на эту тему)
Добрый день!
Спасибо за познавательную статью. Однако, как было сказано выше - она не отвечает на вопрос "почему?".
Возможно, вы могли бы посоветовать хороший материал (желательно видео урок), в котором концепция использования деревьев, как структур данных, достаточно хорошо популяризирована.
Техническая сторона вопроса закрыта, но общего понимания целесообразности применения концепции построения деревьев - нет :(
Это как с определением предела в высшей математике: "для любого эпсилон больше нуля, существует такой номер N..." - пока не изобразишь графически эту эпсилон-полосу, до тебя не дойдет смысл такого определения.
Также и с деревьями у меня - пока что не встречал материала, который бы популярно объяснял смысл и выгоду применения подхода дерева решений (или случайного леса)...
Может бы вы могли бы подсказать?)
Разбираемся в АА-деревьях (Python)