Все о древовидной структуре данных в JavaScript.

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

Видеоверсия этой статьи

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

Посмотреть видео

Что такое дерево?

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

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

  • Узел: член дерева, который может быть самим деревом.
  • Корневой узел: самый верхний узел в дереве. Единственный узел в дереве без родителя.
  • Узел ответвления: (также известный как внутренний узел). Узел с дочерним узлом.
  • Конечный узел: (также известный как внешний или внешний узел). Узел без детей.
  • Дочерний узел: узел под другим узлом является потомком этого узла.
  • Родительский узел: узел с дочерним узлом.
  • Узлы-предки: все родительские узлы и их родительские узлы.
  • Дочерние узлы: все дочерние узлы и их дочерние узлы.
  • Родственные узлы: узлы с одним и тем же родителем.
  • Поддерево: узел и все его дочерние узлы.
  • Глубина узла: это путь узла к корневому узлу. Довольно много уровней родителей вверх.
  • Высота узла: это самый длинный путь до его нижнего листового узла. Довольно много уровней детей вниз.
  • Обход дерева. Также известен как «обход дерева» - это переход между узлами дерева. Вы перебираете список и перемещаетесь по дереву.
  • Рекурсия: когда функция вызывает сама себя. Рекурсия - очень распространенный способ обхода дерева.
  • Упорядоченное дерево: дерево, в котором порядок указан для каждого узла, например, в двоичном дереве левый узел имеет меньшее значение, чем родительский, а правый дочерний узел имеет большее значение, чем родительский.

Типы деревьев

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

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

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

Двоичное дерево

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

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

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

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

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

Дерево AVL

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

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

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

Красно-черное дерево

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

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

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

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

Дерево кучи (Treap)

Дерево кучи или treap - это очень особенное двоичное дерево. Если вы работали с javascript, вы, вероятно, слышали о куче памяти или сортировке кучи, которая представляет собой алгоритм сортировки с использованием дерева кучи. В некотором смысле куча - это более эффективная реализация очереди с приоритетами, и достаточно часто люди называют очереди с приоритетом кучей.

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

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

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

Trie

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

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

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

Когда использовать дерево?

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

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

Заключение

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

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

Канал YouTube: До точки с запятой
Веб-сайт: beforesemicolon.com