AVL Деревья и РЕАЛЬНЫЙ мир

14

в школе нас учат, как мы можем сбалансировать дерево AVL при вставке или удалении.

Как этот тип знаний будет полезен в реальном мире? Может ли кто-нибудь привести пример того, когда этот тип знаний будет полезен?

Из того, что я видел, на рабочем месте такие детали вряд ли когда-либо всплывают ...

Я вижу, насколько важны подробные знания об алгоритмах и некоторых структурах данных, но не такие подробности, как ротация дерева AVL (и подобные подробные концепции).

Благодарность!

rrazd
источник
7
Это полезно в интервью, если это считается реальным миром.
Кевин
Это тот же самый аргумент, который некоторые люди высказывают об изучении тригонометрии в школе «Sheesh! Когда я когда-нибудь собираюсь использовать это в реальной жизни?», И ответ звучит так: «Вы думали, как анализировать и решать целый класс проблем» , Это и однажды вы хотите срубить дерево, и ваш партнер спрашивает: «Вы уверены, что это не ударит по дому?» Триг на помощь!
двоичный беспорядок

Ответы:

13

Изучение деревьев AVL может быть полезным по следующим причинам:

  • Это отличная практика для рассуждений об абстрактных данных. Вам не нужно думать об одном конкретном дереве, вы должны рассмотреть каждую возможность. Практика с такими рассуждениями может помочь и в более простых случаях.

  • Это отличная практика для понимания предикатов и контрактов. Обеспечение того, чтобы дерево было сбалансированным, и инструменты, которые вы используете для проверки баланса каждой операции, можно, например, применять к соображениям безопасности и к параллельному коду.

  • Это дает вам возможность писать свои собственные варианты или даже создавать совершенно новые типы структур данных.

  • Возможно, вам просто придется реализовать дерево AVL для новой библиотеки или платформы.

Вы можете обсудить конкретные преимущества изучения каждого вида алгоритма сортировки или каждого вида сбалансированного дерева. Неважно, какие из них вы в конечном итоге изучаете, но вы должны быть уверены, что получите полное освещение наиболее важных тем.

Если вы хотите узнать, насколько важны алгоритмы знания в реальном мире, прочитайте статью « Как убить великую идею! », Статью в Inc о гибели Friendster и о том, как малейшее применение фундаментальных принципов для повышения эффективности могло бы помочь им.

Макнейл
источник
Интересная статья, но я не вижу, как деревья AVL помогли бы друзьям.
Эратосфен
Я хотел бы видеть пример, как B + -Tree используются для индексации базы данных.
Лука Фюльбьер
5

В дополнение к очкам Macneils ...

Красно-черные деревья, возможно, более полезны, потому что есть полезные эффективные операции, которые широко не поддерживаются в стандартных реализациях библиотек, таких как C ++ std::map(по крайней мере, AFAIK). Красно-черные деревья могут поддерживать «расщепление» (разрезание дерева на два, одно, содержащее ключи меньше указанного ключа, и одно, содержащее ключи больше) и «объединение» (наоборот, объединение дерева больших ключей с деревом маленьких ключи) могут быть выполнены за время O (log n), но если они поддерживаются в стандартных библиотеках контейнеров, это, кажется, хорошо скрыто.

Однако «расширение» структур данных является распространенным явлением. Простой пример - добавление информации о размере поддерева к узлам практически любой древовидной структуры данных для поддержки подписки O (log n). Более сложные примеры включают интервальные деревья.

Как только у вас появится идея дополнения структур данных, появится множество вариантов, которые могут быть полезны для конкретных приложений, и очень немногие из них доступны в виде библиотеки. Существующие структуры данных стандартной библиотеки (например, такие как std::map) не могут быть дополнены за исключением копирования исходного кода и его прямого изменения - вы не можете дополнить их, используя параметры шаблона.

Конечно, чтобы разработать расширенную структуру данных, вам необходимо понять основную структуру без дополнительных данных.

Деревья AVL могут быть быстрее, чем красно-черные деревья, если вы выполняете намного больше операций поиска, чем вставки / удаления (и при условии, что вам не нужны эти операции разделения / объединения), поэтому в зависимости от приложения они могут быть очень хорошей основой для приумножения.

Steve314
источник
1
+1 за расширение структуры данных, хотя это довольно редкая вещь. Большинству программистов не нужно стремиться к производительности (иначе мы все будем использовать C ++ / C / Fortran / Assembly).
Матье М.
@Matthieu - я считаю, что это распространено, но только в определенных типах сред разработки. Это не противоречие, честно, потому что ... ну, хорошо ...
Steve314
Я полностью согласен! : D
Матье М.
5

нет

Это действительно бесполезно в реальном мире ...

За исключением того, чтобы заставить вас думать .

В реальном мире существуют гораздо более сложные проблемы , многие из которых еще не имеют известных решений.

Стивен А. Лоу
источник