Каковы приложения двоичных деревьев?

Основным приложением является двоичные деревья поиска . Это структура данных, в которой поиск, вставка и удаление выполняются очень быстро (около log(n) операций)

Их можно использовать как быстрый способ сортировки данных. Вставьте данные в двоичное дерево поиска в O(log(n)). Затем следуйте по дереву, чтобы отсортировать их.

Реализации Java.util.Set

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

В C++ STL, и многих других стандартных библиотеках на других языках, таких как Java и C#. Деревья двоичного поиска используются для реализации set и map.

Из наиболее распространенного приложения - это эффективно хранить данные в отсортированной форме, чтобы быстро получить доступ и поискать хранимые элементы. Например, STD :: Map или STD :: SET в стандартной библиотеке C ++.

Двоичное дерево в качестве структуры данных полезно для различных реализаций показателей экспрессии и решателей экспрессии.

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

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

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

Я не думаю, что "чистые" двоичные деревья можно использовать. (за исключением образовательных целей) Сбалансированные бинарные деревья, такие как Красно-черные или AVL деревья , гораздо более полезны, так как они гарантируют работу с O(logn). Обычные двоичные деревья могут оказаться списками (или почти списками) и на самом деле не очень полезны в приложениях, использующих большое количество данных.

Сбалансированные деревья часто используются для реализации карт или наборов. Они также могут быть использованы для сортировки в O(nlogn), даже если существуют лучшие способы сделать это.

Также для поиска/вставки/удаления можно использовать Хэш-таблицы , которые обычно имеют лучшую производительность, чем двоичные деревья поиска (сбалансированные или нет).

Приложение, в котором (сбалансированные) деревья двоичного поиска были бы полезны, если бы потребовались поиск/вставка/удаление и сортировка. Сортировка может быть на месте (почти игнорируя пространство стека, необходимое для рекурсии), учитывая готовое построенное сбалансированное дерево. Это все равно было бы O(nlogn), но с меньшим постоянным фактором и без лишнего пространства (за исключением нового массива, предполагая, что данные должны быть помещены в массив). Хэш-таблицы, с другой стороны, не могут быть отсортированы (по крайней мере, не напрямую).

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

Другие деревья, такие как B+trees, широко используются в базах данных

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

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

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

Alice
Bob
Chloe
David
Edwina
Frank

, так что при чтении их обратно в итоге получилось следующее дерево:

  Alice
 /     \
=       Bob
       /   \
      =     Chloe
           /     \
          =       David
                 /     \
                =       Edwina
                       /      \
                      =        Frank
                              /     \
                             =       =

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

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

1.   Alice
    /     \
   =       =

2.   Alice
    /     \
   =       Bob
          /   \
         =     =

3.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       =

4.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       David
                    /     \
                   =       =

5.           Bob
        ____/   \____
   Alice             David
  /     \           /     \
 =       =     Chloe       Edwina
              /     \     /      \
             =       =   =        =

6.              Chloe
            ___/     \___
         Bob             Edwina
        /   \           /      \
   Alice     =      David        Frank
  /     \          /     \      /     \
 =       =        =       =    =       =

Фактически вы можете увидеть целые поддеревья, вращающиеся влево ( на шагах 3 и 6) по мере добавления записей, и это дает вам сбалансированное двоичное дерево, в котором поиск в наихудшем случае будет O (log N) , а не O (N ) что дает вырожденная форма. Ни при каких обстоятельствах самый высокий NULL ( = ) не отличается от самого низкого более чем на один уровень. И в последнем дереве выше вы можете найти Фрэнка, посмотрев только на три узла ( Хлоя , Эдвина и, наконец, Фрэнк ).

Конечно, они могут стать еще более полезными, если вы сделаете их сбалансированными многоходовыми деревьями, а не бинарными прядями. Это означает, что каждый узел содержит более одного элемента (технически они содержат N элементов и N + 1 указателей, двоичное дерево является частным случаем одностороннего многостороннего дерева с 1 элементом и 2 указателями).

В случае трехстороннего дерева вы получите:

  Alice Bob Chloe
 /     |   |     \
=      =   =      David Edwina Frank
                 /     |      |     \
                =      =      =      =

Обычно это используется для поддержки ключей для индекса элементов. Я написал программное обеспечение для баз данных, оптимизированное для оборудования, где размер узла равен размеру блока диска (скажем, 512 байт), и вы помещаете столько ключей, сколько можете в один узел. Указатели в этом случае на самом деле были номерами записей в файле прямого доступа фиксированной длины отдельно от индексного файла (так что номер записи X можно было найти, просто выполнив поиск X * длина_записи ).

Например, если указатели составляют 4 байта, а размер ключа равен 10, количество ключей в 512-байтовом узле равно 36. Это 36 ключей (360 байтов) и 37 указателей (148 байтов), всего 508 байт с потерей 4 байтов на узел.

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

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

Также имейте в виду, что преимущества O (log N) перед O (N) на самом деле не проявляются, когда ваши наборы данных малы. Если вы используете многостороннее дерево для хранения пятнадцати человек в своей адресной книге, это, вероятно, излишне. Преимущества появляются, когда вы храните что-то вроде каждого заказа от сотни тысяч клиентов за последние десять лет.

Вся суть обозначения большого О состоит в том, чтобы указать, что происходит, когда N приближается к бесконечности.Некоторые люди могут не согласиться, но использовать пузырьковую сортировку можно даже в том случае, если вы уверены, что наборы данных останутся ниже определенного размера, до тех пор, пока нет ничего доступного: -)

Что касается других применений двоичных деревьев, то здесь их очень много, например:

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

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

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

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

Например, выражение (1 + 3) * 2 может быть выражено как:

    *
   / \
  +   2
 / \
1   3

Чтобы оценить выражение, мы запрашиваем значение родителя. Этот узел, в свою очередь, получает свои значения от своих дочерних элементов, оператора плюса и узла, который просто содержит «2». Оператор «плюс», в свою очередь, получает свои значения от дочерних элементов со значениями «1» и «3» и складывает их, возвращая 4 в узел умножения, который возвращает 8.

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