Древовидные структуры данных и DOM

Как «самая важная нелинейная [структура]… в компьютерных алгоритмах»¹ помогает организовывать сайты, которые мы создаем.

Понимание интерфейса Document Object Model (DOM) является неотъемлемой частью обучения разработке на JavaScript и может помочь новичкам расшифровать блоки туманного HTML. DOM упорядочивает элементы, из которых состоит файл HTML, и представляет их в виде данных в древовидной структуре данных, обеспечиваяболее четкую навигацию и более простой выбор отдельных ресурсов. Возможность уверенно взаимодействовать с DOM позволяет разработчику косвенно манипулировать стилем, содержимым и поведением HTML из внешних файлов JavaScript.

Использование DOM для рендеринга HTML (или XML) — это стандарт, который веб-разработчики приняли, но новые и опытные разработчики могут перестать спрашивать: «Что такое древовидная структура данных?» Мы пройдемся по определениям и приложениям этой модели в надежде укрепить наше понимание модели DOM, которую мы так часто используем.

Древовидная структура данных

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

        -> [node]
      /
[root]             -> [node] -> [node]
      \          /
        -> [node]
                 \
                   -> [node]

На диаграмме, которую мы видим ниже, узел A действует как корень, который, в свою очередь, имеет двух потомков, B и C. родственные узлыD и E имеют один и тот же >родительскийузел, C. Узлы без дочерних узлов (B, D и E) называются конечными узлами.

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

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

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

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

Применение деревьев

Одним из наиболее известных применений древовидной структуры данных могут быть файловые системы наших компьютеров. Если бы вы сейчас открыли проводник, вы могли бы увидеть папку «Рабочий стол», папку «Документы» или папку «Загрузки» (все узлы), которые, в свою очередь, содержат свои собственные папки (узлы со своими дочерними узлами) или файлы (конечные точки). или листья дерева). Пользователи Unix также могут быть знакомы с тем, что самый верхний файловый каталог называется root.

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

Использование древовидных структур также обеспечивает впечатляющие достижения в других областях науки, таких как деление пространства на квадранты в моделировании Барнса-Хата, что позволяет проводить динамическое моделирование частиц для задач с n телами (см. Реализация этой симуляции пользователем GitHub Elucidation в браузере « здесь").

Наконец, мы часто сталкиваемся с древовидной структурой данных в рамках HTML-сайтов: объектная модель документа.

DOM как дерево

Давайте взглянем на простой HTML-файл в качестве примера древовидной структуры DOM:

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Example Page</title>
  </head>
  <body>
    <header>
      <p>Home</p>
    </header>
    <main>
      <h1>Welcome to my example website!</h1>
      <div class="example-div">
        <p>This is an example paragraph.</p>
        <div class="another-div">
          <p>For some reason this paragraph is placed inside a div.</p>
        </div>
      </div>
    </main>
    <footer>
      <p>About us</p>
    </footer>
  </body>
</html>

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

Для этого DOM рассматривает каждый элемент (части, заключенные в угловые скобки: <title>, <body> и т. д.) как отдельный узел дерева, а тег <html> действует как корень. Все, что находится внутри элемента, рассматривается как еще один узел, потенциально имеющий других собственных дочерних элементов.

Если бы мы представили приведенный выше файл в виде (очень простого) дерева, мы могли бы увидеть что-то вроде этого:

Это представление позволяет нам, как разработчикам, визуализировать иерархические отношения между каждым элементом HTML и, что более важно, позволяет нашему JavaScript перемещаться по этим элементам при выполнении запросов DOM.

Рассмотрим этот запрос документа из веб-документов Mozilla:⁴

const paragraphs = document.querySelectorAll("p");

API DOM предлагается выбрать все элементы <p> и поместить их в массив. Это достигается за счет того, что DOM просматривает ветви дерева, описанного выше, где он сначала обнаружит узел <p>, который определен как дочерний элемент <header> в <body>.

Достигнув конца ветки, он вернется к узлу <body> и его дочерним элементам, погрузится в элемент <main> и его дочерние элементы и обнаружит <p> как дочерний элемент нашего первого <div>.

Далее самый низкий <p> дерева будет найден в другом <div>.

Наконец, DOM возвращается к узлу <body>, а элемент <p> находится в узле <footer>.

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

Заключение

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

Древовидные структуры данных и DOM

Древовидная структура данных

Применение деревьев

DOM как дерево

Заключение

Рекомендации

Вопросы по теме