Реальные примеры древовидных структур

https://stackoverflow.com/questions/577659

05-09-2019
|

Вопрос

Я ищу несколько примеров древовидных структур, которые используются в проектах коммерческого / свободного программного обеспечения, современных или старых.Я могу видеть примеры в Википедии, но я ищу более конкретные примеры и то, как они используются.Например, первичные ключи в базах данных (из того, что я прочитал) хранятся в структуре BST или вариации BST (не стесняйтесь поправлять меня по этому поводу)

Мой вопрос не ограничивается бинарными деревьями поиска (BSTS), он может включать любые варианты, такие как красно-черный, AVL и так далее.

Решение

Нормально ли, если примеры немного обобщены, т. е.относятся к графам и не обязательно к деревьям?Если это так, читайте дальше.

Излишне говорить, что большинство анализаторов XML / разметки используют деревья.Смотрите, например, Apache Xerces.Или анализатор Xalan XSLT.Спасибо мэтьюсдаве26 за то, что напомнил мне!
PDF - это древовидный формат.В нем есть root узел, за которым следует catalog узел (часто это одно и то же), за которым следует pages узел, который имеет несколько дочерних page узлы.Производители / потребители часто используют реализацию сбалансированного дерева для хранения документа в памяти.
Компьютерные шахматные игры создают огромное дерево (обучение), которое они обрезают во время выполнения, используя эвристику для достижения оптимального хода.
Вспышка это библиотека визуализации, написанная на AS.Возможно, вы захотите проверить, как отображаются объекты данных.В частности, flare.analytics пакет в значительной степени использует графическую структуру, связующие деревья и т.д.
Социальные сети - это модное слово в исследованиях CS.Само собой разумеется, что связи / relations очень естественно моделируются с помощью графиков.Часто деревья используются для представления/ идентификации более интересных явлений.Как вы отвечаете на такие вопросы, как "Есть ли у Гарри и Салли какие-либо общие друзья?"
Некоторые очень успешные физические / игровые движки строят деревья, чтобы точно имитировать движение человека.Дерево в этом случае обычно будет соответствовать набору действий;Контекст будет определять, какой путь будет выбран для отображения конкретного ответа.
Обучение на основе дерева решений на самом деле является важной областью исследований в области интеллектуального анализа данных.Существует множество известных методов, таких как упаковка в мешки, бустинг и их модификации, которые работают на деревьях.Такая работа часто используется для создания прогностической модели.
Распространенной проблемой в биоинформатике является поиск в огромных базах данных для поиска совпадений по заданной строке запроса.Попытки там - обычное явление.
Довольно много успешных (биржевых) трейдеров используют деревья решений в своей повседневной торговле - для выбора сделки и выхода из нее.Часто они не кодифицированы в компьютерной программе, а записаны где-нибудь на обратной стороне их записной книжки.

Обманщик.Видишь это и это.

Другие советы

B в индексе базы данных B* trees означает Сбалансированный, а не двоичный.Дерево укладывается на одинаковую глубину, чтобы обеспечить равномерное время доступа.

Ваша файловая система представляет собой древовидную структуру.Так что проверьте исходный код любой свободной файловой системы.
Ваш компилятор генерирует АСТ из вашего исходного кода, в качестве промежуточного этапа.Так что ознакомьтесь с исходным кодом любого бесплатного компилятора.

Индексы базы данных обычно хранятся в виде вариантов B *-деревьев, которые, несмотря на свое название, не являются бинарными деревьями.

Бинарные деревья использовались для разделения пространства и удаления скрытых поверхностей в старых 3D-играх, я полагаю, что одно из них использовалось в игре Doom.

Напишите простой анализатор рекурсивного спуска и попросите его сгенерировать дерево синтаксического анализа.
Структура спецификации материалов, используемая в производстве (например, автомобиль состоит из узлов, рекурсивно, вплоть до гаек и болтов).
Таблица символов (как используется в компиляторе).
План счетов, используемый в управлении проектами.Общий проект имеет подпроекты, к которым может быть применена плата.
Организационная структура компании:подразделения, департаменты и т.д.
Оглавление документа.
Потомки человека, предки человека.
Любое s-выражение Lisp, включая любую программу Lisp.

Функции автозаполнения в программном обеспечении (например."предложения" поисковой системы, заполнение типа IDE / символа, названия электронной почты и адресной книги и т.д.) Часто реализуются в виде попыток, которые представляют собой древовидные структуры.

Взглянув на любой из продуктов Datawarehousing, вы увидите продуманные способы хранения и сверления в виде дерева.Вы получаете древовидную структуру для местоположения (страна, регион, штат, m округ, город и т.д.) и времени (год, месяц, День, час).Эти два измерения являются общими для многих областей, но многие другие данные реального мира также могут быть использованы в дереве.

Например, в розничной торговле продуктами питания у истоков могут лежать бакалейные товары, которые можно разделить на молочные продукты, фрукты и овощи и т.д.Следуя одному потоку, который у вас мог бы быть.Банки с фасолью, на верхнем уровне вы будете говорить о грузовиках, затем перейдете к поддонам, коробкам, размерам жестянок.Все различные артикулы (единицы учета запасов) важны для кого-то в магазине или компании.Затем разные виды бобов, разные поставщики, производители - все примеры деревьев для одного и того же размера.

Все различные продукты образуют массивное дерево с различными способами нарезки и нарезки кубиками.

C ++ включает в себя ряд коллекций (set, multi_set, map, multi_map), которые обычно реализуются в виде красно-черных деревьев, своего рода сбалансированного дерева.

(Стандарт C ++ явно не требует такой реализации, но это самый простой дизайн, который отвечает требованиям сложности.)

В маршрутизаторе / коммутаторе, где я раньше работал, мы использовали кучу древовидных структур, для таблицы программных маршрутов мы использовали исходное дерево (довольно распространенный выбор для таблицы маршрутизации IP).

Наша реализация OSPF использовала красно-черные деревья, наша реализация BGP использовала списки пропусков.

Технически скиплисты не являются древовидными структурами, но на практике они очень похожи, и они действительно классные.

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

DNS-запросы..все, что использует map, использует AVL

Система.Коллекции.Общий.Сортированный список<T> использует двоичное дерево поиска в качестве базовой реализации.То же самое верно и для Система.Коллекции.Дженериксортированный справочник<T>.Любой код, использующий SortedList<T> или SortedDictionary<T> использует двоичное дерево поиска.

В моем проекте, системе редактирования и вменения данных опросов / переписей, мы используем двоичное дерево решений, чтобы решить, какие переменные записи вменять или не вменять.Бинарное дерево решений позволяет нам эффективно принимать решения о путях в дереве, которые мы должны и не должны выбирать.

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

Мы используем древовидную структуру для моделирования системы классификации деталей.Части классифицируются на "классы", у которых есть родительские классы и так далее.Классы верхнего уровня управляют текстом для вкладок в нашем пользовательском интерфейсе каталога.Классы также используются для применения правил ценообразования, определения "горячих точек" на транспортном средстве, где детали отображаются в "конфигураторе", и т.д.Мы моделируем дерево в SQL, используя вложенные наборы Джо Селко, и загружаем их по требованию в память для повышения производительности.Наиболее распространенные вопросы, которые мы задаем, - это "кто мои потомки" и "является ли этот класс моим предком?"

Очень удобно

Классификация объектов в целом очень часто это делается с использованием деревьев.И очень часто график был бы гораздо более подходящим, чем дерево, однако дерево имеет два больших преимущества перед графиком:

Он может быть представлен в виде (вложенного) списка.Например, гораздо проще показать большое дерево на бумаге (с заголовками, субтитрами, абзацами и вложенными списками) или на экране компьютера, чем график.
Вы можете указать на элемент в дереве, используя простую строку пути (или стек), например "http/StackOverflow.com/Users/Dimitri C", что гораздо сложнее сделать на графике.

Существует treap, реализованный в ActionScript.Источники:

treap является частью Фреймворк коллекций AS3Commons.Модифицированный treap используется для резервного копирования включенных коллекций SortedSet и SortedMap.

Представьте себя корнем дерева, а теперь сделайте своих родителей детьми дерева, а родителей родителей - их детьми дерева, и это может стать полноценным вариантом использования tree.

Итак, реализуя что-то там, где требуется полная иерархия семейства, вы можете использовать tree для реализации этого.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow