Skip to main content

Дерево DOM

Определение​

DOM (Document Object Model) — это иерархическая структура, представляющая HTML-документ в виде дерева узлов. Каждый узел может быть:

  • Элементом (например, <div>, <span>)
  • Текстом (например, Hello world!)
  • Атрибутом (например, class="example")

DOM позволяет взаимодействовать с HTML-страницей, изменять её содержимое, стили и структуру с помощью JavaScript.

Операции с document​

DOM предоставляет методы для работы с узлами:

  • document.querySelector(selector) — находит первый элемент по селектору.
  • document.querySelectorAll(selector) — находит все элементы по селектору.
  • document.getElementById(id) — получает элемент по id.
  • document.getElementsByClassName(className) — получает коллекцию элементов по class.
  • document.getElementsByTagName(tagName) — получает коллекцию элементов по тегу.

Поиск элементов определённого цвета (DFS и BFS)​

1. DFS (Поиск в глубину)​

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

function findElementsByColorDFS(root, color) {
  let result = [];

  function dfs(node) {
    if (!node) return;
    if (window.getComputedStyle(node).color === color) {
      result.push(node);
    }
    for (let child of node.children) {
      dfs(child);
    }
  }

  dfs(root);
  return result;
}

// Пример использования:
let elements = findElementsByColorDFS(document.body, "rgb(255, 0, 0)"); // ищем красные элементы
console.log(elements);

2. BFS (Поиск в ширину)​

Используется очередь (Queue), элементы обрабатываются "по уровням".

function findElementsByColorBFS(root, color) {
  let result = [];
  let queue = [root];

  while (queue.length) {
    let node = queue.shift();
    if (window.getComputedStyle(node).color === color) {
      result.push(node);
    }
    for (let child of node.children) {
      queue.push(child);
    }
  }

  return result;
}

// Пример использования:
let elements = findElementsByColorBFS(document.body, "rgb(255, 0, 0)");
console.log(elements);

Сравнение DFS и BFS в DOM-дереве

Когда использовать DFS и BFS в DOM?​

Оба алгоритма — DFS (глубина) и BFS (ширина) — применяются для обхода DOM-дерева, но их производительность и применимость зависят от размера и структуры документа.

Основные отличия в работе алгоритмов​

МетодСтруктура данныхПреимуществаНедостаткиКогда использовать
DFS (глубина)Стек (Stack) (рекурсия или массив)1. Экономит память на мелких деревьях. 2. Удобно применять при поиске глубоко вложенных элементов.1. Риск переполнения стека в больших деревьях (Stack Overflow). 2. В среднем требует больше операций возврата, чем BFS. 3. Может быть непредсказуемым при работе с асинхронными изменениями DOM.Редкие случаи: 1. Если DOM-дерево глубокое, но узкое. 2. Когда нужен поиск только одного элемента в глубине.
BFS (ширина)Очередь (Queue) (массив или shift())1. Гарантирует, что первый найденный элемент — ближайший. 2. Не вызывает переполнение стека, так как использует итеративный подход. 3. Эффективен при работе с широкими деревьями.1. Требует больше памяти при очень широком дереве (может расти в ширину). 2. Операция shift() в JS-массиве медленнее, чем pop() (но это можно обойти).Лучший вариант в 90% случаев: 1. Если документ большой (например, сайт с тысячами элементов). 2. Когда нужен поиск первого найденного элемента. 3. При массовых обновлениях (BFS обходит ближайшие элементы первым).

Почему BFS предпочтительнее для DOM?​

  1. Безопасность против Stack Overflow

    • DFS использует стек, а стек в JavaScript имеет ограниченный размер (~10,000 вызовов, но браузеры могут отличаться).
    • Глубокий DOM (например, таблицы или вложенные div) может привести к Maximum call stack size exceeded.
    • BFS не использует рекурсию, поэтому не имеет этой проблемы.

  2. Оптимизированный поиск ближайшего элемента

    • BFS обходит узлы "по уровням", поэтому находит нужный элемент быстрее, если он ближе к корню.
    • DFS может уйти вглубь и пропустить более близкий элемент.

  3. Хорошо работает с динамическим DOM

    • В реальном мире элементы DOM могут добавляться и удаляться асинхронно (например, при бесконечной прокрутке или динамических изменениях контента).
    • BFS быстрее адаптируется, так как проходит "первый уровень", обновляя список дочерних элементов.
    • DFS может столкнуться с удалёнными узлами и выбрасывать ошибки.

  4. Более предсказуемый при модификациях

    • Если во время обхода изменяется структура DOM, BFS лучше справляется.
    • DFS может "застрять", если ожидает определённое количество дочерних элементов, а они изменились.

Когда DFS всё же полезен в DOM?​

  1. Когда точно знаем, что глубина ограничена

    • Например, поиск элемента в простом списке вложенных ul > li.
    • В этом случае DFS может работать быстрее, так как тратит меньше памяти.

  2. Когда нужен поиск только в глубине

    • Например, поиск самого вложенного элемента (<div><div><div>...</div></div></div>).
    • BFS в этом случае обойдет слишком много ненужных элементов, а DFS сразу пойдет вниз.

Вывод​

BFS почти всегда предпочтителен для обхода DOM, потому что:

Гарантирует, что первый найденный элемент — ближайший
Не вызывает переполнение стека
Лучше работает с динамическим DOM

DFS стоит применять только если дерево гарантированно маленькое и неглубокое.

Если приходит массив элементов​

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

1. Статическая коллекция (Set, Map)​

Если элементы не меняются и важно исключать дубликаты, лучше использовать Set:

let elements = new Set([element1, element2, element3]); // Уникальные элементы

Если нужен доступ по ключу, выбираем Map:

let elements = new Map();
elements.set(element1, true);

2. Динамическая коллекция (Array, WeakSet, WeakMap)​

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

WeakSet / WeakMap полезны для временных элементов, чтобы избежать утечек памяти.

let weakElements = new WeakSet();
weakElements.add(element1);

Задачи​

  1. 102. Binary Tree Level Order Traversal (аналог BFS в DOM)
  2. 94. Binary Tree Inorder Traversal (аналог DFS в DOM)
  3. 199. Binary Tree Right Side View (поиск первого видимого элемента)
  4. 144. Binary Tree Preorder Traversal (DFS Preorder)
  5. 145. Binary Tree Postorder Traversal (DFS Postorder)