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

Question

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

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

Answer 1

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

• Нет нужды говорить, что большинство синтаксических анализаторов XML / Markup используют деревья. Смотрите Apache Xerces для примера. Или Xalan XSLT-парсер. Спасибо mathewsdave26 за напоминание!

• PDF - это древовидный формат. У него есть узел root, за которым следует узел catalog (они часто совпадают), за которым следует узел pages, который имеет несколько дочерних узлов page. Производители / потребители часто используют реализацию сбалансированного дерева для хранения документа в памяти.

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

• Flare - библиотека визуализации, написанная на AS. Вы можете проверить, как отображаются объекты данных. В частности, пакет flare.analytics интенсивно использует графовую структуру, связующие деревья и т. Д.

• Социальные сети - настоящее модное слово в исследованиях CS. Само собой разумеется, что связи / отношения очень естественно моделируются с помощью графиков. Часто деревья используются для представления / идентификации более интересных явлений. Как вы отвечаете на вопросы типа «Есть ли у Гарри и Салли какие-нибудь общие друзья?»

• Некоторые очень успешные физические / игровые движки создают деревья для точного моделирования движения человека. Дерево в этом случае обычно будет соответствовать набору действий; Контекст определит, какой путь используется для визуализации конкретного ответа.

• Обучение, основанное на дереве решений, фактически представляет собой огромную область исследований в области интеллектуального анализа данных. Существуют многочисленные известные методы, такие как пакетирование, повышение и их модификации, которые работают на деревьях. Такая работа часто используется для создания прогностической модели.

• Распространенной проблемой в биоинформатике является поиск в огромных базах данных для поиска соответствий для заданной строки запроса. Попытки - обычное явление.

• Довольно много успешных (фондовых) трейдеров используют деревья решений в своей повседневной торговле - чтобы выбрать сделку, чтобы выйти из нее. Часто они не кодифицированы в компьютерной программе, а записаны где-то на обороте их ноутбука.

Dupe. См. это и это .

Answer 2

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

Answer 3

• Ваша файловая система имеет древовидную структуру. Так что проверьте исходный код любой свободной файловой системы.

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

Answer 4

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

Answer 5

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

Answer 6

• Напишите простой синтаксический анализатор с рекурсивным спуском и сделайте так, чтобы он генерировал дерево разбора.

• Структура ведомости материалов, используемая в производстве (например, автомобиль состоит из сборочных узлов, рекурсивно, вплоть до гаек и болтов).

• Таблица символов (как используется в компиляторе).

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

• Организационная структура предприятия: подразделения, отделы и др.

• Содержание документа.

• Потомки человека, предки человека.

• Любое s-выражение на Лиспе, включая любую программу на Лиспе.

Answer 7

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

Answer 8

System.Collections.Generic.SortedList использует двоичное дерево поиска в качестве базовой реализации. То же самое верно для System.Collections.GenericSortedDictionary . Любой код, использующий SortedList или SortedDictionary , использует двоичное дерево поиска.

Answer 9

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

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

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

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

Answer 10

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

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