Может ли кто-нибудь дать мне пример реальной жизни (в программировании, C#) необходимости использования двоичного дерева или даже обычного дерева?Использование двоичного дерева
Я понимаю принцип двоичного дерева и то, как они работают, но я пытаюсь найти пример реальной жизни их использования?
Tony
В C#, Java, Python, C++ (с использованием STL) и других языков высокого уровня, большую часть времени вы будете использовать один из встроенных в/библиотечно- включенные типы для хранения ваших данных, по крайней мере данные, на которых вы работаете в данный момент, поэтому большую часть времени вы не будете использовать двоичное дерево или другой вид дерева явно.
Это, как говорится, некоторые из этих встроенных типов реализованы как деревья того или иного вида «за кулисами», и в некоторых ситуациях вам придется реализовать их самостоятельно.
Кроме того, связанная вещь, которую вы должны знать, - это двоичный поиск. В основном это делается в бинарных деревьях (деревья двоичного поиска: P), но идея может быть экстраполирована на множество проблем, даже без задействованных деревьев, поэтому попробуйте понять это хорошо.
Edit: Реальная жизнь классический пример:
Представьте себе, что вы хотите найти номер телефона конкретного человека в телефонном руководстве большого города. При прочих равных условиях вы откроете его примерно посередине, найдите парней на этой странице и посмотрите, есть ли ваша «цель» до или после нее, тем самым сокращая данные наполовину. Затем вы повторяете операцию в половине, где вы знаете свою «цель», и снова и снова, пока не найдете свою «цель». Поскольку каждый раз, когда вы просматриваете половину данных, которые у вас были до этого, вам требуется всего log (base 2) n операций для достижения вашей «цели», где n - это общий размер данных.
Итак, в 1 миллионной телефонной книге вы найдете свою цель в базе данных (база 2) 1 миллион = 20 сравнений, вместо сравнения один за другим, как в линейном поиске (это 1 миллион сравнений в худшем случае).
Обратите внимание, что это работает только в уже отсортированных данных.
Простой пример - поиск. Например, если вы сохраняете данные списка в дереве, вы получаете время поиска O (log (n)). Стандартная реализация массива списка приведет к достижению O (n) времени поиска.
В Java, дерева используются для реализации определенных отсортированных структур данных, таких как TreeSet:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeSet.html
Они используются для структур данных, где вы хотите, чтобы основываться на какой-то собственности элементов, а не на порядок вставки.
Документы XML, HTML (и SGML) являются деревьями.
Но они не бинарные деревья? Поскольку у них может быть более двух детей, принадлежащих одному узлу, поэтому он не соответствует правилам двоичного дерева. – Tarik
Это n-арные деревья, причем любой узел может иметь произвольное количество дочерних узлов. Он используется для гибкости (поэтому ваш HTML-документ может иметь любую структуру), где бинарное дерево и его кузены (красный/черный и т. Д.) Создаются для хранения больших объемов данных и вставки или извлечения любого элемента данных очень быстро по сравнению с числом вещей, хранящихся в дереве. –
Хммм. Теперь я не могу вспомнить, является ли n-арное дерево правильным термином. Однако остальное мое описание в порядке. –
Balanced binary trees, хранение данных поддерживается в отсортированном порядке, используются для достижения O (журнал (п)) поиска, удаления и вставки раз. «Сбалансированный» означает, что существует ограниченный предел между глубиной самых мелких и самых глубоких листьев, считая пустые левые/правые узлы листьями. (оптимально глубина левого и правого поддеревьев отличается не более чем одним, некоторые реализации ослабляют это, чтобы упростить алгоритмы)
Вы можете использовать массив, а не дерево, в отсортированном порядке с бинарным поиском для достижения O (log (n)), но тогда время вставки/удаления равно O (n).
Некоторые деревья (в частности, B-trees для баз данных) используют более двух ветвей на узел, чтобы расширить дерево и уменьшить максимальную глубину (которая определяет время поиска).
Я не могу придумать причину использования двоичных деревьев, которые не поддерживаются в отсортированном порядке (точка, о которой не упоминалось в большинстве ответов здесь), но, возможно, для этого есть приложение.
Помимо сортированного двоичного сбалансированного дерева, все, что связано с иерархией (как упоминают другие ответчики, XML или структуры каталогов), является хорошим приложением для деревьев, будь то двоичное или нет.
Редактировать: re: несортированные бинарные деревья: Я только что вспомнил, что LISP и Scheme очень сильно используют несбалансированные бинарные деревья. Функция cons принимает два аргумента (например, (define c (cons a b))) и возвращает узел дерева, ветви которого являются двумя аргументами. Функция car принимает такой узел дерева и возвращает первый аргумент, заданный cons. Функция cdr аналогична, но возвращает второй аргумент cons. Наконец nil представляет собой нулевой объект. Это примитивы, используемые для создания всех структур данных в LISP и Scheme. Списки выполняются с использованием крайне несбалансированного двоичного дерева. Список, содержащий буквенные элементы 'Alabama, 'Alaska, 'Arizona и 'Arkansas можно построить в явном виде
(cons 'Alabama (cons 'Alaska (cons 'Arizona (cons 'Arkansas nil))))
и может перемещаться с помощью car и cdr (где car используется, чтобы получить голову списка и cdr используется для получить подсписку, исключая заголовок списка).Вот как работает Scheme, я думаю, что LISP такой же или очень похожий. Более сложные структуры данных, такие как бинарные деревья (для которых требуется 3 члена на узел: два для хранения левого и правого узлов и третий для хранения значения узла) или деревья, содержащие более двух ветвей на узел, могут быть построены с использованием списка для реализовать каждый узел.
Как насчет структуры каталогов в Unix. Например, команда du, то есть команда использования диска выполняет обход после ордера (порядок обхода :: левый дочерний -> правый дочерний -> корневой узел) дерева, представляющего структуру каталогов, чтобы извлекать дисковое пространство, используемое этим каталогом.
Следующие слайды должны помочь.
http://www.cse.unt.edu/~rada/CSCE3110/Lectures/Trees.ppt
веселит
отличный пример - хотя структуры каталогов не являются бинарными деревьями –
да, они не бинарные деревья. Я только что опубликовал это, когда Тони упомянул обычное дерево в своем вопросе. – Arnkrishn
Вот некоторые примеры:
в оперативной памяти представление о анализируемой программы или выражение является деревом. В случае выражений (исключая тройные операторы) дерево будет двоичным.
Компоненты GUI организованы как дерево.
Любая иерархия «сдерживания» может быть представлена как дерево. (HTML, XML и SGML являются примерами.
И, конечно же, бинарные (и п-ичных) деревья могут быть использованы для представления индексов, карты, наборы и другие «общие» структуры данных.
Значит, вы можете хранить все, что вы храните в массиве в дереве? Но в дереве время поиска меньше ... Наверное, это только вступает в игру с структурами данных, содержащими множество данных. –
@ Тони: Не обязательно. Все, что имеет явную иерархию, хорошо подходит для деревьев (возможно, не для двоичных деревьев, а, конечно, для деревьев вообще), даже если это не так много предметов. (Подумайте о своем генеалогическом древе: даже если вы не знаете, что многие из ваших родственников это все еще дерево!) –
Двоичное дерево поиска требует ** O ** (log2 * n *). Для линейного списка требуется ** O ** (* n */2). В 8 элементах вы обнаружите, что дерево требует (самое большее) 3 сравнения, но для линейного поиска требуется (в среднем) 4. –