Рубрики

Приложения древовидной структуры данных


Почему дерево?
В отличие от Array и Linked List, которые являются линейными структурами данных, дерево является иерархической (или нелинейной) структурой данных.

  1. Одной из причин использования деревьев может быть то, что вы хотите хранить информацию, которая естественно образует иерархию. Например, файловая система на компьютере:

    файловая система
    —-

         /   <-- root
      /      \
    ...        home
          /          \
       ugrad        course
        /          /    |    \
      ...        cs101 cs112 cs113
    
  2. Если мы организуем ключи в виде дерева (с некоторым порядком, например, BST), мы можем искать данный ключ за умеренное время (быстрее, чем Linked List, и медленнее, чем массивы). Самобалансируемые поисковые деревья, такие как AVL и красно-черные деревья, гарантируют верхнюю границу O (Logn) для поиска.
  3. Мы можем вставлять / удалять ключи за умеренное время (быстрее, чем массивы, и медленнее, чем неупорядоченные связанные списки). Самобалансируемые поисковые деревья, такие как AVL и красно-черные деревья, гарантируют верхнюю границу O (Logn) для вставки / удаления.
  4. Как и в случае связанных списков и в отличие от массивов, реализация указателей деревьев не имеет верхнего предела числа узлов, поскольку узлы связаны с помощью указателей.

Другие применения:

  1. Храните иерархические данные, такие как структура папок, организационная структура, данные XML / HTML.
  2. Двоичное дерево поиска — это дерево, которое позволяет осуществлять быстрый поиск, вставку, удаление отсортированных данных. Это также позволяет найти ближайший пункт
  3. Куча — это древовидная структура данных, которая реализована с использованием массивов и используется для реализации приоритетных очередей.
  4. B-Tree и B + Tree : они используются для реализации индексации в базах данных.
  5. Синтаксическое дерево : используется в компиляторах.
  6. KD Tree: Дерево разбиения пространства, используемое для организации точек в K-мерном пространстве.
  7. Три : Используется для реализации словарей с поиском префиксов.
  8. Суффикс-дерево : для быстрого поиска по шаблону в фиксированном тексте.
  9. Деревья связующего и кратчайшего пути используются соответственно в маршрутизаторах и мостах в компьютерных сетях.
  10. В качестве рабочего процесса для создания цифровых изображений для визуальных эффектов.

Ссылки:
http://www.cs.bu.edu/teaching/c/tree/binary/
http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Common_uses

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Приложения древовидной структуры данных

0.00 (0%) 0 votes