Обновлено: 05.07.2024

Думаю, я никогда не увижу
График прекраснее дерева.
Дерево, важнейшим свойством которого
является связность без петель.
Дерево, которое должно охватывать
Чтобы пакеты могли достигать любой локальной сети.
Во-первых, необходимо выбрать корень.
По ID, он избран.
Отслеживаются пути с наименьшей стоимостью от корня.
В дереве эти пути размещены.
Сетка создается такими людьми, как я,
Затем мосты находят остовное дерево.

– Радия Перлман (разработчик Spanning Tree)

Двоичное дерево состоит из узлов, каждый из которых содержит левый указатель, правый указатель и элемент данных.

Указатель корня указывает на самый верхний узел в дереве. Левый и правый указатели рекурсивно указывают на меньшие поддеревья с обеих сторон. Нулевой указатель представляет собой двоичное дерево без элементов — пустое дерево.

Формальное рекурсивное определение: бинарное дерево либо пусто (представлено нулевым указателем), либо состоит из одного узла, где каждый левый и правый указатели (рекурсивное определение впереди) указывают на бинарное дерево.< /p>

Двоичное дерево поиска (BST) или упорядоченное двоичное дерево — это тип двоичного дерева, в котором узлы расположены по порядку: для каждого узла все элементы в его левом поддереве меньше или равны узлу ( ).

В основном бинарные деревья поиска работают быстро при вставке и поиске. В среднем алгоритм бинарного дерева поиска может найти узел в дереве узлов из $n$ в порядке $\log n$ времени (логарифмическая база 2). Таким образом, бинарные деревья поиска хороши для задач со словарями, когда код вставляет и ищет информацию, проиндексированную некоторым ключом. Поведение $ \log n$ является обычным случаем: конкретное дерево может работать намного медленнее в зависимости от его формы.

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

Листовой (внешний) узел — это узел, у которого нет дочерних элементов, тогда как нелистовой узел также называется внутренним узлом. Количество потомков узла $x$ в дереве $T$ равно степени узла $x$. Длина простого пути от корня $r$ до вершины $x$ равна глубине $x$ в $T$. Уровень дерева состоит из всех узлов на одной глубине. Высота узла в дереве — это количество ребер (скачков) на самом длинном нисходящем пути от узла к листу, а высота дерева — это высота его корня. Таким образом, высота дерева равна наибольшей глубине любого узла в дереве.

1. $O(1)$
2. $O(log_2 n)$
3. $O(высота)$
4. $O(n)$

В этот пример кода двоичного дерева поиска включены следующие элементы.
Он основан на дереве на картинке выше.

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

Определения:

1. Дерево – это набор узлов с одним корнем и ветвями, которые являются деревьями.
2. Дерево — это конечное множество узлов, такое что: (1) существует специально назначенный узел, называемый корнем; (2) остальные узлы разбиты на n ≥ 0 непересекающихся множеств T1, T2, . Tn, где каждый из этих наборов представляет собой дерево, известное как поддерево .

Концепция/терминология:

• Нелинейная организация элементов. Компоненты не образуют простую последовательность из первого элемента, второго элемента и т. д.
• Имена взяты из ботаники и генеалогии: узел, ветвь, глубина (высота), корень, лист, нелист (внутренний узел), путь, лес; родитель, ребенок, родной брат, двоюродный брат, предок, потомок и поддерево.
• Дополнительные термины приведены на страницах 445–447.

Классификация:

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

Особые деревья:

• Пустое (нулевое) дерево: дерево без узла
• Корневое дерево: дерево только с одним узлом
• Двоичное дерево: дерево, в котором каждый узел имеет не более двух дочерних элементов (родительский, левый и правый).
• Два дерева: бинарное дерево, которое либо пусто, либо каждое нелистовое дерево имеет двух дочерних элементов.
• Куча: дерево, в котором родительский узел имеет большее (меньшее) значение, чем дочерний.
• И многие другие: бинарное дерево поиска (BST), дерево 2-3, дерево AVL, B-дерево, дерево Хаффмана, красно-черное дерево, игровое дерево, связующее дерево и т. д.

Почему древовидная структура?

• O(журнал n)

• Двоичное дерево – это конечное множество узлов.
• Набор может быть пустым.
• Если набор не пуст, он следует следующим правилам:
  1. Существует один специальный узел, называемый корневым.
  2. Каждый узел может быть связан максимум с двумя другими узлами, называемыми его левым дочерним элементом и его правым дочерним элементом. Если узел c является дочерним по отношению к другому узлу p, то мы говорим, что "p является узлом c's. родительский".
  3. Каждый узел, кроме корня, имеет только одного родителя; у корня нет родителя.
  4. Если вы начнете с узла и перейдете к родительскому элементу узла (если он есть), а затем снова перейдете к родительскому элементу этого узла и продолжите движение вверх к родительскому элементу каждого узла, вы в конечном итоге достигнете корня.

Является ли следующее бинарным деревом?

Другие определения:

• Поддерево: любой узел дерева и его потомки.
• Глубина узла: количество шагов для перехода от текущего узла к корневому узлу дерева.
• Глубина дерева: максимальная глубина любого из его листьев.
• Высота узла: длина самого длинного нисходящего пути к листу от этого узла.
• Полное бинарное дерево: каждый лист имеет одинаковую глубину, а каждый нелист имеет двух дочерних элементов.
• Полное бинарное дерево: каждый уровень, кроме самого глубокого, должен содержать как можно больше узлов; а на самом глубоком уровне все узлы находятся максимально слева.
• Обход: организованный способ посетить каждого члена в структуре.

Для полного бинарного дерева используйте следующие формулы представления массива:

1. Данные из корня всегда отображаются в компоненте [0] массива.
2. Предположим, что данные для некорневого узла появляются в компоненте [i] массива. Тогда данные для его родителя всегда находятся в месте [(i - 1)/2].
3. Предположим, что данные для узла появляются в компоненте [i] массива. Тогда его дочерние элементы (если они существуют) всегда имеют свои данные в этих местах:
   1. Левый дочерний элемент в компоненте [2i + 1]
   2. Правый дочерний элемент в компоненте [2i + 2]

   Давайте рассмотрим пример с доски.

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

   • Сам массив
   • Вторая переменная экземпляра отслеживает, какая часть массива используется.

   Фактические связи между узлами не сохраняются, а определяются по формуле.

   Можем ли мы также реализовать неполное двоичное дерево с помощью массива?

   Представление узлов бинарных деревьев:

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

   Например, реализация универсального типа:

   
   

   класс BTNode
   частные данные E;
   приватная BTNode оставлена;
   приватный BTNode справа;
   .
   >
   

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

   // Получение и настройка ссылок на данные
   public E getData()
   public BTNode getLeft()
   public BTNode getRight()

   public void setData(E newData)
   public void setLeft(BTNode newLeft)
   public void setRight(BTNode newRight)

   // Проверяем, является ли узел листом
   public boolean isLeaf() // реализуем его

   // Получение данных из крайнего левого или крайнего правого узла; подсказки: используя рекурсию
   public E getLeftmostData() // реализуем
   public E getRightmostData()

   // Удаление самого левого или самого правого узла
   // Удаляем самый левый узел дерева с этим узлом в качестве корня.
   // Постусловие: удален крайний левый узел. Возвращаемое значение является ссылкой на корень нового дерева. Возвращаемое значение может быть нулевым.
   public BTNode removeLeftmost()
   // узел, который активирует removeLeftmost, не имеет левого дочернего элемента, поэтому сам является самым левым узлом поддерева
   if (left == null) return right;
   > else // рекурсивный вызов удаляет самый левый узел из моего левого поддерева
   left = left.removeLeftmost();
   вернуть это;
   >
   >

   // Ваша очередь реализовать removeRightmost()
   public BTNode removeRightmost()
   

   // Копирование дерева
   public static BTNode treeCopy(BTNode source)
   BTNode leftCopy, rightCopy;

   if (source == null)
   вернуть null;
   else leftCopy = treeCopy(source.getLeft());
   rightCopy = treeCopy(source.getRight());
   вернуть новый BTNode (source.getData(), leftCopy, rightCopy);
   >
   >

   // Высота узла
   public static int height(BTNode node)
   if (node ​​== null)
   return -1; // это пустое дерево
   else
   return 1 + Math.max(height(node.getLeft()), height(node.getRight()));
   >

   // Подсчитаем количество узлов в бинарном дереве с заданным корнем
   public static int treeSize(BTNode root)
   // ваша очередь реализовывать

   // Подсчитаем количество листьев в бинарнике с заданным корнем
   public static int countLeaves(BTNode root)
   // ваша очередь реализовать

   Примечание. Реализация дерева или связанные алгоритмы действительно используют много "рекурсий". Также обратите внимание, что глубина среднего бинарного дерева значительно меньше, чем n, хотя в худшем случае глубина может достигать n-1.

   • Обход предварительного заказа
   • Обход по порядку
   • Обход после заказа
   1. Обработать корень.
   2. Обработать узлы в левом поддереве с помощью рекурсивного вызова.
   3. Обработка узлов в правом поддереве с помощью рекурсивного вызова.
   1. Обработать узлы в левом поддереве с помощью рекурсивного вызова.
   2. Обработать корень.
   3. Обработка узлов в правом поддереве с помощью рекурсивного вызова.
   1. Обработать узлы в левом поддереве с помощью рекурсивного вызова.
   2. Обработка узлов в правом поддереве с помощью рекурсивного вызова.
   3. Обработать корень.

   Завершите код для обхода по порядку и после заказа.

   В бинарном дереве поиска элементы узлов можно сравнивать с семантикой общего порядка. Следующие два правила соблюдаются для каждого узла n:

   1. Каждый элемент в левом поддереве n меньше или равен элементу в узле n.
   2. Каждый элемент в правом поддереве n больше, чем элемент в узле n.

   Пример: создайте двоичное дерево поиска со следующими значениями: 51, 29, 68, 90, 36, 40, 22, 59, 44, 99, 77, 60, 29, 83, 15, 75, 3. Затем вставьте 33, 88, 1, 36 в БСТ. Теперь удалите 44, 90, 68, 70 из BST.

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

   
   

   19 ответов 19

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

   Применения бинарных деревьев

   - Используется во многих поисковых приложениях, где данные постоянно вводятся и выводятся, например карта и набор объектов в библиотеках многих языков. - Используется почти в каждой 3D-видеоигре, чтобы определить, какие объекты необходимо визуализировать. - Используется почти в каждом маршрутизаторе с высокой пропускной способностью для хранения таблиц маршрутизатора. - Используется в торрентах и ​​специализированных изображениях-подписях, в которых нужно проверить хеш, но файл целиком недоступен. Также используется в блокчейнах, например. Биткойн. - Используется для реализации эффективных очередей с приоритетом, которые, в свою очередь, используются для планирования процессов во многих операционных системах, качества обслуживания в маршрутизаторах и A* (алгоритм поиска пути, используемый в приложениях ИИ, включая робототехнику и видео игры). Также используется в куче сортировки. (Chip Uni) — используется в алгоритмах сжатия, таких как используемые форматами файлов .jpg и .mp3. - Используется в криптографических приложениях для генерации дерева псевдослучайных чисел. - Создан компиляторами и (неявно) калькуляторами для разбора выражений. - Рандомизированная структура данных, используемая в беспроводных сетях и распределении памяти. - Хотя большинство баз данных используют некоторую форму B-дерева для хранения данных на диске, базы данных, которые хранят все (большую часть) своих данных в памяти, часто используют для этого T-деревья.

   Причина, по которой бинарные деревья используются для поиска чаще, чем n-мерные, заключается в том, что n-мерные деревья более сложны, но обычно не дают реального преимущества в скорости.

   В (сбалансированном) двоичном дереве с m узлами для перехода с одного уровня на другой требуется одно сравнение, и существует log_2(m) уровней, всего log_2(m) сравнений.

   Напротив, n-арное дерево потребует log_2(n) сравнений (с использованием бинарного поиска) для перехода на следующий уровень. Поскольку существует общее количество уровней log_n(m), для поиска потребуется общее количество сравнений log_2(n)*log_n(m) = log_2(m). Таким образом, хотя n-арные деревья более сложны, они не дают никаких преимуществ с точки зрения необходимого общего количества сравнений.

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

   > Treap — Рандомизированная структура данных, используемая в беспроводных сетях и распределении памяти. Как именно они используются при распределении памяти и беспроводных сетях?

   Существует множество полезных структур данных и алгоритмов, в которых используется слово "бинарные", и "бинарное дерево ПОИСКА" на самом деле является одним из них, но вопрос был задан не об этом. Какая польза от старого доброго «бинарного дерева», не отсортированного, не сбалансированного, не полного. Простое старое случайное дерево?

   Я считаю, что хеш-деревья обычно называют деревьями Меркла, по крайней мере, в сообществах биткойнов и эфириумов, IPFS и т. д.

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

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

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

   чтобы при обратном чтении получилось следующее дерево:

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

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

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

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

   С трехсторонним деревом вы получите:

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

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

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

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

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

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

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

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

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

   
   

   Когда я начал изучать Ruby в прошлом году, я решил реализовать бинарное дерево поиска и некоторые из его основных операций (вставка, удаление, обход и поиск), просто чтобы освоить язык. Двоичные деревья поиска — хорошее упражнение, потому что вам нужно использовать несколько функций языка, таких как условные операторы, циклы и классы, и в то же время решать интересную задачу. Алгоритм бинарных деревьев поиска хорошо описан в большинстве вводных книг по алгоритмам и в Интернете.

   Чтобы немного усложнить задачу, я также реализовал программу для рисования бинарного дерева поиска, чтобы люди могли видеть, как выглядит бинарное дерево поиска, когда в нем больше нескольких узлов. В этом конкретном случае я написал небольшое веб-приложение на Ruby, которое рисует двоичное дерево поиска, используя новый элемент холста, поддерживаемый в HTML 5. Вы можете загрузить весь исходный код для двоичного дерева и демонстрационный веб-сайт из этого репозитория GitHub и играть с ним в вашей локальной среде.

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

   Двоичное дерево или бинарное дерево поиска

   Корректно говоря, код в этом сообщении блога реализует двоичное дерево поиска (BST), которое является более конкретной версией двоичного дерева. Кормен и др. дать хорошее объяснение этого в своей книге «Введение в алгоритмы». Двоичные деревья — это деревья, в которых каждый узел имеет не более двух дочерних элементов, один из которых называется «левым поддеревом», а другой — «правым поддеревом», но сам по себе порядок не применяется (стр. 1178). Двоичные деревья поиска, с другой стороны, всегда хранятся таким образом, чтобы удовлетворять свойству двоичного дерева поиска (стр. 287):

   Пусть x будет узлом в двоичном дереве поиска.
   Если y является узлом в левом поддереве x, то y.key ? х.ключ.
   Если y является узлом в правом поддереве x, то y.key ? х.ключ.
   

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

   Реализация бинарного дерева поиска

   Класс, который я реализовал, можно использовать следующим образом (суть):

   Из коробки мы можем использовать этот класс BinaryTree с числами, строками или любым другим родным типом Ruby. Мы также можем использовать его с другими типами, если они реализуют сопоставимые операции (например, def ).

   Добавление узлов в двоичное дерево поиска

   Ниже показан код для добавления узлов в двоичное дерево поиска. Этот код сначала оценивает, есть ли у нас уже корневой узел, если нет, то мы создаем корневой узел с новым значением, и все готово. Если у нас уже есть корневой узел, то сканируйте узлы дерева (используя вышеупомянутое свойство двоичного дерева поиска, меньшие значения идут влево, равные или большие, чем значения, идут вправо), пока мы не достигнем конечного узла. Как только мы достигли конечного узла, мы обновляем его, чтобы он указывал на новый узел. (суть)

   Прогулка по дереву

   Одним из преимуществ бинарного дерева поиска является то, что очень легко извлекать по порядку хранящиеся в нем значения. Этот процесс называется «обход дерева по порядку». Например, если у нас есть дерево со следующими значениями: 100, 50, 200 и 150, обход дерева по порядку даст нам: 50, 100, 150 и 200. Обход дерева можно легко реализовать с помощью рекурсивной функции. . Однако рекурсивный метод, хотя и элегантный, не очень эффективен, когда ожидается, что дерево будет иметь большое количество узлов. Код, который я реализовал для обхода дерева, не использует рекурсию, а вместо этого использует массив в качестве стека для отслеживания узлов, которые он посещает.Эта версия не так элегантна, как рекурсивная версия, которую можно найти в большинстве вводных книг, но она хорошо работает, даже когда дерево содержит тысячи узлов.

   Ниже приведен код, который я реализовал для обхода дерева по порядку (суть).

   При реализации этого метода я на собственном опыте убедился в красоте и простоте одной из самых разрекламированных функций Ruby: блоков. Вы можете увидеть использование блоков в узле строки yield предыдущего кода. Когда алгоритм находит следующий узел для обработки, он просто выдает его вызывающей программе. Это позволяет коду обхода дерева быть полностью независимым от действия, которое мы хотим выполнить на каждом узле. Например, мы можем вывести каждый узел в консоль с помощью следующего кода:

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

   Как нарисовать бинарное дерево поиска

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

   Основы этого алгоритма следующие:

   • Нарисуйте корневой узел в указанных координатах.
   • Нарисуйте левое поддерево слева от корневого узла.
   • Нарисуйте правое поддерево справа от корневого узла.

   Чтобы вычислить координату, в которой должно быть нарисовано левое поддерево, мы подсчитываем, сколько потомков имеет правая сторона левого поддерева. Мы используем это число для вычисления координаты x как отрицательного смещения от корня. Координата Y — это просто положительное смещение от корня. Затем мы повторяем этот процесс для левого и правого поддеревьев. В следующем фрагменте кода показан этот код (суть).

   Процедура вычисления координаты, где должно быть нарисовано правое поддерево, прямо противоположна: мы подсчитываем, сколько дочерних элементов левая сторона правого поддерева есть. Мы используем это число для вычисления координаты x как положительного смещения от корня. Координата Y — это просто положительное смещение от корня. Затем мы повторяем этот процесс для левого и правого поддеревьев. В следующем фрагменте кода показан этот код (суть).

   Как и в методе обхода, представленные здесь три метода отрисовки только вычисляют, где должен быть отрисован узел, но фактически не отрисовывают узел. Вместо этого они вызывают блок с соответствующими параметрами для выполнения фактической операции. Вы можете увидеть это в строке block.call(node.value, x, y, parent_x, parent_y) в этих трех подпрограммах.

   В следующем коде показан пример вызова метода рисования для простого дерева и отображения на консоли координат, где должен быть нарисован каждый из узлов (суть):

   Существует множество исследований о том, как лучше всего рисовать бинарные деревья поиска с большим количеством данных. Книга «Рисование графиков: алгоритмы визуализации графиков» Толлиса и др. похоже, это ссылка, на которую ссылается большинство исследовательских работ и презентаций. На страницах 43–45 представлена ​​более сложная версия алгоритма, который я использовал, а также несколько расширенных алгоритмов для различных сценариев.

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

   Реальный пример рисования бинарного дерева поиска на веб-странице

   Когда у нас есть координаты, где можно нарисовать каждый узел, мы можем использовать любую графическую программу для фактического рисования. Так как я написал эту программу в качестве учебного упражнения, я решил написать небольшое веб-приложение на Ruby для фактического рисования. В этом веб-приложении я использую новый элемент холста HTML 5 в качестве поверхности для рисования и серию вызовов JavaScript для рисования линий и окружностей в соответствующих координатах.

   В следующем коде показана упрощенная версия того, как я генерирую вызовы JavaScript для рисования узлов (кругов и меток) и линий, соединяющих узлы (суть):

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

   Исходный код

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

   На своем ноутбуке я нарисовал деревья, содержащие до 10 000 узлов. Один из недостатков алгоритма рисования, который я реализовал, заключается в том, что это неэффективный по площади алгоритм, который приводит к очень широким рисункам. Вы можете увидеть этот эффект в этом дереве с 500 узлами.

   Похожая запись

   Блог опубликован: 2011-04-11 03:59:00 +0000 UTC

   
   

   Эта работа находится под лицензией Creative Commons Attribution 4.0 International License. | Кредиты.

   Модуль 10: Дополнительный материал

   
   

   Упражнение 1. Нарисуйте дерево выражений для выражения 10/4 + 2*(5+1). Вычислите значения в каждом неконечном узле.

   Как построить дерево по заданному выражению.

   Вычислительная процедура для извлечения частей (чисел и операторов) выражения типа (35-3*(3+2))/4 называется анализом.

   • Каждое число будет заключено в круглые скобки.
   • Каждый оператор со своим операндом будет заключен в круглые скобки.
   • Конечно, синтаксический анализ можно сделать и с этими ограничениями
     ⇒ Но код сложнее
   • Таким образом, выражение (35-3*(3+2))/4 становится (((35)-((3)*((3)+(2) )))/(4))

   Упражнение 2. Преобразуйте выражение 10/4 + 2*(5+1) в приведенную выше форму с полными скобками.

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

   Упражнение 3. Покажите, как работает рекурсия для выражения (((35)-((3)*((3)+(2))))/(4)). То есть нарисуйте последовательность «снимков стека», показывающую рекурсивные вызовы метода parse().

   Это тоже написано рекурсивно:

   Упражнение 6. Преобразуйте выражение 10/4 + 2*(5+1) в постфиксную форму и запишите push/арифметические «инструкции», соответствующие этому выражению.

   Существуют компьютерные архитектуры с похожими наборами команд
   ⇒ Они используют вычислитель на основе стека как часть ЦП.

   Преобразование в постфиксное простое: просто пройдитесь по дереву в постфиксном порядке!

   Перечисление элементов структуры данных

   Напомним: карта хранит пары "ключ-значение".

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

   Упражнение 7. Загрузите BinaryTreeMap3.java и BinaryTreeMapExample3.java, скомпилируйте и выполните. Вы заметите, что вывод отсортирован, а ввод (порядок добавления строк) — нет. Как/где происходила сортировка?

   Иногда удобнее использовать классы итераторов.

   Упражнение 8. Зачем требуется приведение выше?

   Как мы встраиваем эту функцию в наши собственные структуры данных?
   ⇒ Это довольно сложная тема.
   ⇒ См. Модули 6–7 продвинутого материала по Java

   Приложение: количество слов

   Например, рассмотрим этот текст: В этом примере мы хотим, чтобы вывод выглядел примерно так:

   • добавить()
   • содержит()
   • getAllKeyValuePairs() (чтобы получить все пары "ключ-значение" в виде массива)

   Упражнение 9. Загрузите BinaryTreeMap3.java, OurLinkedListMap.java, WordCount.java и тестовый файл. Скомпилируйте и запустите WordCount, чтобы убедиться, что он работает. Затем выполните подсчет слов для этой классической книги и для этой. Вы можете закомментировать версию со связанным списком (поскольку она делает то же самое, но делает это медленнее). Найдите другую бесплатную книгу в Интернете и примените к ней WordCount.

   Упражнение 10. Сравните производительность дерева, хеш-таблицы и связанного списка для двух больших текстов выше. Вам нужно будет добавить код, чтобы использовать хеш-таблицу для подсчета. Используйте OurHashMap.java в качестве хеш-таблицы.

   • Сначала рассмотрим использование:
     • Таким образом, мы начинаем с несортированного массива объектов ( uniqueWords )
     • В этом случае каждый объект представляет собой KeyValuePair .
     • Мы вызываем метод sort() в классе Arrays в библиотеке.
     • Мы передаем экземпляр KeyValueComparator алгоритму сортировки.
     • Мы не можем. Вместо этого мы передаем класс с помощью нашего метода.
     • В нашем примере это класс KeyValueComparator , который мы напишем.
     Сигнатура метода сортировки Java (тот, который мы хотим использовать): (Примечание: мы немного упростили его, чтобы удалить ссылки на универсальные типы).

     • Обратите внимание, что наш класс KeyValueComparator реализует интерфейс Comparator
     • Здесь мы предоставили реализацию compare() (и equals() , которая требуется интерфейсом, но не используется алгоритмом сортировки).< /li>
     • Мы пишем любой код внутри compare().
     • Конечно, мы действительно хотим правильно сравнить два объекта KeyValuePair.
       ⇒ Именно поэтому мы извлекаем целые числа из объектов и сравниваем их.

     Упражнение 11. Добавьте счетчик в KeyValueComparator выше, чтобы подсчитывать, как часто вызывается метод compare(). Какова связь между этим количеством и размером сортируемого массива?

     Упражнение 12. Изучите логику в compare() . Что произойдет, если мы заменим первые два оператора return на: Попробуйте и посмотрите, что получится. Затем объясните, что произошло.

     Читайте также:

       
     • Как проверить диодный мост в блоке питания компьютера
       
     • Замена жесткого диска SATA
       
     • Папка может содержать файлы папки ярлыки копии ярлыков копии дисков информация о пользователе
       
     • Несуществующее устройство указало жесткий диск Windows 10
       
     • Как снизить нагрузку на процессор в gta 5