Share This
Связаться со мной
Крути в низ
Categories
//☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Третья часть цикла об алгоритмах и структурах данных в JavaScript посвящена древовидным иерархическим структурам.

rasprostranennye algoritmy i struktury dannyh v javascript derevja c193f14 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

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

Другие статьи цикла:

  • Часть 1. Основные понятия и работа с массивами
  • Часть 2. Стеки, очереди и связные списки

Структура данных «Дерево»

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

rasprostranennye algoritmy i struktury dannyh v javascript derevja 6775605 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Древообразная структура DOM (объектной модели документа).

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

Устройство дерева

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

rasprostranennye algoritmy i struktury dannyh v javascript derevja 200cb74 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Пример дерева.

  • У корневого элемента (на картинке узел со значением 2) есть несколько дочерних узлов (7 и 5), каждый из которых в свою очередь сам является корнем поддерева. Таких уровней может быть сколько угодно.
  • Элемент, у которого нет дочерних узлов, называется листом, или терминальным узлом (2, 5, 11, 4). Все остальные узлы (кроме корневого), у которых есть потомки, называются внутренними.
  • Каждый узел дерева имеет только одного родителя, не больше. Кроме корневого узла, у которого родителей нет вообще.
  • Высота дерева – длина самой длинной ветви (количество ребер). У дерева на картинке она равна 3 – ветка от корня 2 до листа 5. Высоту также можно найти для любого внутреннего узла, например, для узла 6 высота равна 1.

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

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

Основные операции

Деревья – довольно сложные структуры. Для работы с иерархическими данными они должны предоставлять ряд алгоритмов.

Основные операции, которые нам нужны:

  • Добавление нового узла (add);
  • Удаление узла по его значению (remove);
  • Поиск узла по значению (find);
  • Обход всех элементов (traverse).

При необходимости этот список можно расширить более сложными алгоритмами:

  • Вставка/удаление поддерева;
  • Вставка/удаление ветви;
  • Вставка элемента в определенную позицию;
  • Поиск наименьшего общего предка для двух узлов.

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

Реализация дерева на JavaScript

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

При этом важно, чтобы не было дубликатов и у каждого узла был только один родитель.

         class BinaryTreeNode {   constructor(value) {     this.left = null;     this.right = null;     this.parent = parent;     this.value = value;   }    get height() {     let leftHeight = this.left ? this.left.height + 1 : 0;     let rightHeight = this.right ? this.right.height + 1 : 0;     return Math.max(leftHeight, rightHeight);   } }  let tree = new BinaryTreeNode('a');     

Высота узла (height) вычисляется рекурсивно, на основе высоты его дочерних узлов.

Добавление узлов

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

         class BinaryTreeNode {   // …    setLeft(node) {     if (this.left) {       this.left.parent = null;     }     if (node) {       this.left = node;       this.left.parent = this;     }   }    setRight(node) {     if (this.right) {       this.right.parent = null;     }     if (node) {       this.right = node;       this.right.parent = this;     }   } }     

При вставке важно обновить все затронутые ссылки: left или right для родительского узла и parent для дочернего. Если у родителя уже был потомок, его свойство parent нужно обнулить.

Создание дерева

Реализация очень простая, но с ее помощью мы уже можем построить настоящее двоичное дерево, например, такое как на картинке:

rasprostranennye algoritmy i struktury dannyh v javascript derevja 22ba50d - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

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

         let aNode = new BinaryTreeNode('a');  let bNode = new BinaryTreeNode('b'); aNode.setLeft(bNode);  let cNode = new BinaryTreeNode('c'); aNode.setRight(cNode);  let dNode = new BinaryTreeNode('d'); bNode.setRight(dNode);  let eNode = new BinaryTreeNode('e'); cNode.setLeft(eNode);  let fNode = new BinaryTreeNode('f'); cNode.setRight(fNode);     

Обход дерева

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

Мы разберем два популярных алгоритма обхода дерева:

  • поиск в глубину (depth-first search);
  • поиск в ширину (breadth-first search).

DFS: Поиск в глубину

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

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

rasprostranennye algoritmy i struktury dannyh v javascript derevja be9c4a1 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Визуализация работы алгоритма поиска в глубину.

         function traverseDFRecursive(node, callback) {  // выполнение коллбэка для самого узла  callback(node);    // выполнение коллбэка для левого потомка  if (node.left) {    traverseDFRecursive(node.left, callback);  }    // выполнение коллбэка для правого потомка  if (node.right) {    traverseDFRecursive(node.right, callback);  } }   function traverseDF(root, callback) {  traverseDFRecursive(root, callback); }      

Запустим перебор для нашего бинарного дерева:

         traverseDF(aNode, node => console.log(node.value));      

В консоли мы увидим следующее:

rasprostranennye algoritmy i struktury dannyh v javascript derevja 7d1ec91 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

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

Существует три модификации алгоритма с разным способом перебора узлов:

  • обход в прямом порядке, или предупорядоченный обход (pre-order walk). Перебор начинается с родительского узла и идет вниз, к дочерним.
  • обход в обратном порядке, или поступорядоченный (post-order walk). Сначала перебираем левого и правого потомков, а потом родителя.
  • симметричный обход. Начинаем с левого потомка, потом родитель, потом правый потомок.

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

BFS: Поиск в ширину

Обход в ширину работает не по веткам, а по уровням дерева.

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

rasprostranennye algoritmy i struktury dannyh v javascript derevja 0c21bcf - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Визуализация работы алгоритма поиска в ширину.

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

Можно использовать реализацию очереди из предыдущей статьи или воспользоваться простой очередью на базе JavaScript-массива.

         class Queue {   constructor() { 	this.arr = [];   }   enqueue(value) { 	this.arr.push(value);   }   dequeue() { 	return this.arr.shift();   }   isEmpty() { 	return this.arr.length == 0;   } }   function traverseBF(root, callback) {  let nodeQueue = new Queue();  nodeQueue.enqueue(root);    while(!nodeQueue.isEmpty()) {    let currentNode = nodeQueue.dequeue();      // Вызываем коллбэк для самого узла    callback(currentNode);      // Добавляем в очередь левого потомка    if (currentNode.left) {      nodeQueue.enqueue(currentNode.left);    }      // Добавляем в очередь правого потомка    if (currentNode.right) {      nodeQueue.enqueue(currentNode.right);    }  } }     

Запустим перебор в ширину:

         traverseBF(aNode, node => console.log(node.value));     

Результат выглядит так:

rasprostranennye algoritmy i struktury dannyh v javascript derevja 99ccb0c - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Порядок перебора узлов при поиске в ширину.

Бинарное дерево поиска

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

Двоичное (бинарное) дерево поиска (binary search tree, BST) – это дерево, в котором элементы размещаются согласно определенному правилу (упорядоченно):

  • Каждый узел должен быть “больше” любого элемента в своем левом поддереве.
  • Каждый узел должен быть “меньше” любого элемента в своем правом поддереве.

Слова “больше” и “меньше” соответственно означают результат сравнения двух узлов функцией-компаратором.

rasprostranennye algoritmy i struktury dannyh v javascript derevja 9dfec0f - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Пример бинарного дерева поиска.

Благодаря такой сортировке мы можем использовать все преимущества стратегии “разделяй и властвуй” – при поиске элемента можно смело отбрасывать половину дерева. Такие алгоритмы работают гораздо быстрее, чем линейный перебор каждого узла.

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

Реализация на JavaScript

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

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

         class BinarySearchTreeNode extends BinaryTreeNode {   constructor(value, comparator) {     super(value);     this.comparator = comparator;   }    insert(value) {     if (this.comparator(value, this.value) < 0) {       if (this.left) return this.left.insert(value);       let newNode = new BinarySearchTreeNode(value, this.comparator);       this.setLeft(newNode);        return newNode;     }      if (this.comparator(value, this.value) > 0) {       if (this.right) return this.right.insert(value);       let newNode = new BinarySearchTreeNode(value, this.comparator);       this.setRight(newNode);        return newNode;     }     return this;   } }  class BinarySearchTree {   constructor(value, comparator) {     this.root = new BinarySearchTreeNode(value, comparator);     this.comparator = comparator;   }    insert(value) {     this.root.insert(value);   } }      

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

Создадим дерево как на картинке выше:

         const tree = new BinarySearchTree(8, (a, b) => a - b); tree.insert(3); tree.insert(10); tree.insert(14); tree.insert(1); tree.insert(6); tree.insert(4); tree.insert(7); tree.insert(13);      

А теперь обойдем все его элементы, чтобы убедиться, что оно сформировано правильно:

         traverseBF(tree.root);      

rasprostranennye algoritmy i struktury dannyh v javascript derevja d5f48af - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Поиск в бинарном дереве поиска

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

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

         class BinarySearchTree {   find(value) {     return this.root.find(value);   } }  class BinarySearchTreeNode {   find(value) {     if (this.comparator(this.value, value) === 0) return this;      if (this.comparator(this.value, value) < 0 && this.left) {       return this.left.find(value);     }      if (this.comparator(this.value, value) > 0 && this.right) {       return this.right.find(value);     }      return null;   } }     

Алгоритм поиска рекурсивно проверяет все узлы, пока не найдет подходящий.

Удаление узлов

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

Есть три сценария:

  1. У удаляемого узла нет потомков (листовой узел).
  2. У удаляемого узла один потомок (левый или правый).
  3. У удаляемого узла два потомка.
  • Первый случай самый простой и не требует перестройки дерева после удаления.
  • Во втором случае после удаления нужно установить связь между родителем удаленного узла и его потомком. Все потомки удаленного узла в любом случае находятся с той же стороны от его родителя, что и сам узел. Поэтому мы записываем их с той же стороны, на которой находился удаленный узел.
  • Третий случай самый сложный. Мы должны найти следующий по порядку узел (минимальный узел в правом поддереве удаляемого узла) и поставить его вместо удаляемого.

Для реализации алгоритма удаления нам понадобится несколько вспомогательных методов.

         class BinarySearchTreeNode {  // ...    findMin() {    if (!this.left) {      return this;    }      return this.left.findMin();  }    removeChild(nodeToRemove) {    if (this.left && this.left === nodeToRemove) {      this.left = null;      return true;    }      if (this.right && this.right === nodeToRemove) {      this.right = null;      return true;    }      return false;  }    replaceChild(nodeToReplace, replacementNode) {    if (!nodeToReplace || !replacementNode) {      return false;    }      if (this.left && this.left === nodeToReplace) {      this.left = replacementNode;      return true;    }      if (this.right && this.right === nodeToReplace) {      this.right = replacementNode;      return true;    }      return false;  } }      
  • findMin ищет минимальный элемент в поддереве.
  • removeChild удаляет указанный элемент, если он является дочерним для данного узла.
  • replaceChild заменяет дочерний элемент на новый.

Теперь добавим в класс BinarySearchTree новый метод remove:

         class BinarySearchTree {  //...    insert(value) {    if (!this.root.value) this.root.value = value;    else this.root.insert(value);  }    remove(value) {    const nodeToRemove = this.find(value);      if (!nodeToRemove) {      throw new Error('Item not found');    }      const parent = nodeToRemove.parent;      // Нет потомков, листовой узел    if (!nodeToRemove.left && !nodeToRemove.right) {      if (parent) {        // Удалить у родителя указатель на удаленного потомка        parent.removeChild(nodeToRemove);      } else {        // Нет родителя, корневой узел        nodeToRemove.value = undefined;      }    }      // Есть и левый, и правый потомки    else if (nodeToRemove.left && nodeToRemove.right) {      // Ищем минимальное значение в правом поддереве      // И ставим его на место удаляемого узла      const nextBiggerNode = nodeToRemove.right.findMin();        if (this.comparator(nextBiggerNode, nodeToRemove.right) === 0) {        // Правый потомок одновременно является минимальным в правом дереве        // то есть у него нет левого поддерева        // можно просто заменить удаляемый узел на его правого потомка        nodeToRemove.value = nodeToRemove.right.value;        nodeToRemove.setRight(nodeToRemove.right.right);      } else {        // Удалить найденный узел (рекурсия)        this.remove(nextBiggerNode.value);        // Обновить значение удаляемого узла        nodeToRemove.value = nextBiggerNode.value;      }    }          // Есть только один потомок (левый или правый)    else {      // Заменить удаляемый узел на его потомка      const childNode = nodeToRemove.left || nodeToRemove.right;        if (parent) {        parent.replaceChild(nodeToRemove, childNode);      } else {        this.root = childNode;      }    }      // Удалить ссылку на родителя    nodeToRemove.parent = null;      return true;  } }     

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

Полный код

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

         class BinarySearchTreeNode extends BinaryTreeNode {  constructor(value, comparator) {    super(value);    this.comparator = comparator;  }    insert(value) {    if (this.comparator(value, this.value) < 0) {      if (this.left) return this.left.insert(value);      let newNode = new BinarySearchTreeNode(value, this.comparator);      this.setLeft(newNode);        return newNode;    }      if (this.comparator(value, this.value) > 0) {      if (this.right) return this.right.insert(value);      let newNode = new BinarySearchTreeNode(value, this.comparator);      this.setRight(newNode);        return newNode;    }    return this;  }    find(value) {    if (this.comparator(this.value, value) === 0) return this;      if (this.comparator(this.value, value) < 0 && this.left) {      return this.left.find(value);    }      if (this.comparator(this.value, value) > 0 && this.right) {      return this.right.find(value);    }      return null;  }    findMin() {    if (!this.left) {      return this;    }      return this.left.findMin();  }    removeChild(nodeToRemove) {    if (this.left && this.left === nodeToRemove) {      this.left = null;      return true;    }      if (this.right && this.right === nodeToRemove) {      this.right = null;      return true;    }      return false;  }    replaceChild(nodeToReplace, replacementNode) {    if (!nodeToReplace || !replacementNode) {      return false;    }      if (this.left && this.left === nodeToReplace) {      this.left = replacementNode;      return true;    }      if (this.right && this.right === nodeToReplace) {      this.right = replacementNode;      return true;    }      return false;  } }   class BinarySearchTree {  constructor(value, comparator) {    this.root = new BinarySearchTreeNode(value, comparator);    this.comparator = comparator;  }    insert(value) {    if (!this.root.value) this.root.value = value;    else this.root.insert(value);  }    find(value) {    return this.root.find(value);  }    remove(value) {    const nodeToRemove = this.find(value);      if (!nodeToRemove) {      throw new Error('Item not found');    }      const parent = nodeToRemove.parent;      // Нет потомков, листовой узел    if (!nodeToRemove.left && !nodeToRemove.right) {      if (parent) {        // Удалить у родителя указатель на удаленного потомка        parent.removeChild(nodeToRemove);      } else {        // Нет родителя, корневой узел        nodeToRemove.value = undefined;      }    }      // Есть и левый, и правый потомки    else if (nodeToRemove.left && nodeToRemove.right) {      // Ищем минимальное значение в правом поддереве      // И ставим его на место удаляемого узла      const nextBiggerNode = nodeToRemove.right.findMin();        if (this.comparator(nextBiggerNode, nodeToRemove.right) === 0) {        // Правый потомок одновременно является минимальным в правом дереве        // то есть у него нет левого поддерева        // можно просто заменить удаляемый узел на его правого потомка        nodeToRemove.value = nodeToRemove.right.value;        nodeToRemove.setRight(nodeToRemove.right.right);      } else {        // Удалить найденный узел (рекурсия)        this.remove(nextBiggerNode.value);        // Обновить значение удаляемого узла        nodeToRemove.value = nextBiggerNode.value;      }    }      // Есть только один потомок (левый или правый)    else {      // Заменить удаляемый узел на его потомка      const childNode = nodeToRemove.left || nodeToRemove.right;        if (parent) {        parent.replaceChild(nodeToRemove, childNode);      } else {        this.root = childNode;      }    }      // Удалить ссылку на родителя    nodeToRemove.parent = null;      return true;  } }      

Эффективность

Временная сложность всех основных операций в бинарном дереве составляет log(n) – это довольно эффективная структура данных.

Индексация Поиск Вставка Удаление
O(log(n)) O(log(n)) O(log(n)) O(log(n))

Сбалансированные бинарные деревья

Несмотря на строгие правила сортировки элементов бинарное дерево поиска может оказаться крайне неэффективным.

rasprostranennye algoritmy i struktury dannyh v javascript derevja 8363be2 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Вырожденное бинарное дерево поиска.

На картинке изображено валидное бинарное дерево поиска. Для каждого узла соблюдается правило: все узлы в правом поддереве имеют большее значение. Однако такое дерево не позволяет нам пользоваться преимуществами стратегии “разделяй и властвуй”, ведь тут нечего отбрасывать. Говорят, что дерево выродилось в список.

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

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

Эти деревья используют различные алгоритмы “выравнивания” при вставке и удалении элементов.

Легким движением руки несбалансированное дерево поиска превращается в сбалансированное:

rasprostranennye algoritmy i struktury dannyh v javascript derevja eb1f369 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Автоматическая балансировка AVL-дерева.

Визуализация самобалансирующихся деревьев:

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

Двоичная куча

Еще одна древоподобная структура, о которой следует знать – это куча.

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

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

rasprostranennye algoritmy i struktury dannyh v javascript derevja ac5f8b4 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Пример max-кучи.

Бывают также min-кучи, которые следуют противоположному правилу: все потомки узла должны быть больше его. Таким образом, корнем всегда оказывается минимальный элемент кучи.

rasprostranennye algoritmy i struktury dannyh v javascript derevja 899af46 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

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

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

Каждую кучу можно представить в виде линейного массива:

rasprostranennye algoritmy i struktury dannyh v javascript derevja ccf6588 - ☕ Распространенные алгоритмы и структуры данных в JavaScript: деревья

Представление одних и тех же данных в виде дерева и в виде массива.

Чаще всего используется именно линейная реализация, однако дерево более наглядно демонстрирует принцип распределения.

Основные операции

Базовые операции с кучей такие же, как и с очередью:

  • найти элемент с максимальным приоритетом (максимальный элемент в max-куче или минимальный элемент в min-куче);
  • удалить элемент с максимальным приоритетом;
  • добавить в очередь новый элемент.

Реализация

Мы реализуем на JavaScript min-кучу. Для max-кучи нужно только изменить операцию сравнения.

         class Heap {   constructor(comparator) {     this.arr = [];     this.comparator = comparator;   }     isCorrectOrder(first, second) {     return this.comparator(first, second) < 0;   } }      

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

         class Heap {   // ...     getLeftChildIndex(parentIndex) {     return (2 * parentIndex) + 1;   }       getRightChildIndex(parentIndex) {     return (2 * parentIndex) + 2;   }       getParentIndex(childIndex) {     return Math.floor((childIndex - 1) / 2);   }     leftChild(parentIndex) {     return this.arr[this.getLeftChildIndex(parentIndex)];   }     rightChild(parentIndex) {     return this.arr[this.getRightChildIndex(parentIndex)];   }     parent(childIndex) {     return this.arr[this.getParentIndex(childIndex)];   } }     

Добавим еще несколько вспомогательных методов для удобных проверок:

         class Heap {   // ...      hasParent(childIndex) {     return this.getParentIndex(childIndex) >= 0;   }     hasLeftChild(parentIndex) {     return this.getLeftChildIndex(parentIndex) < this.arr.length;   }     hasRightChild(parentIndex) {     return this.getRightChildIndex(parentIndex) < this.arr.length;   }     isEmpty() {     return !this.arr.length;   } }      

Добавление элемента

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

         class Heap {   // ...     push(item) {     this.arr.push(item);     this.heapifyUp();     return this;   }     heapifyUp(startIndex) {     let currentIndex = startIndex || this.arr.length - 1;       while (       this.hasParent(currentIndex)       && !this.isCorrectOrder(this.parent(currentIndex), this.arr[currentIndex])     ) {       let parentIndex = this.getParentIndex(currentIndex);       this.swap(currentIndex, parentIndex);       currentIndex = parentIndex;     }   }     swap(indexOne, indexTwo) {     const tmp = this.arr[indexTwo];     this.arr[indexTwo] = this.arr[indexOne];     this.arr[indexOne] = tmp;   } }      

Получение элемента с максимальным приоритетом

Для получения элемента с начала очереди может быть два метода:

  • peek – просмотр без удаления;
  • pop – получение элемента и удаление его из очереди.

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

         class Heap {   // ...      peek() {     if (this.arr.length === 0) {       return null;     }       return this.arr[0];   }     pop() {     if (this.arr.length === 0) {       return null;     }       if (this.arr.length === 1) {       return this.arr.pop();     }       const item = this.arr[0];       this.arr[0] = this.arr.pop();     this.heapifyDown();       return item;   }     heapifyDown(customStartIndex = 0) {     let currentIndex = customStartIndex;     let nextIndex = null;       while (this.hasLeftChild(currentIndex)) {       if (         this.hasRightChild(currentIndex)         && this.isCorrectOrder(this.rightChild(currentIndex), this.leftChild(currentIndex))       ) {         nextIndex = this.getRightChildIndex(currentIndex);       } else {         nextIndex = this.getLeftChildIndex(currentIndex);       }         if (this.isCorrectOrder(         this.arr[currentIndex],         this.arr[nextIndex],       )) {         break;       }         this.swap(currentIndex, nextIndex);       currentIndex = nextIndex;     }   } }     

Полный код

         class Heap {   constructor(comparator) {     this.arr = [];     this.comparator = comparator;   }     isCorrectOrder(first, second) {     return this.comparator(first, second) < 0;   }     getLeftChildIndex(parentIndex) {     return (2 * parentIndex) + 1;   }       getRightChildIndex(parentIndex) {     return (2 * parentIndex) + 2;   }       getParentIndex(childIndex) {     return Math.floor((childIndex - 1) / 2);   }     leftChild(parentIndex) {     return this.arr[this.getLeftChildIndex(parentIndex)];   }     rightChild(parentIndex) {     return this.arr[this.getRightChildIndex(parentIndex)];   }     parent(childIndex) {     return this.arr[this.getParentIndex(childIndex)];   }     hasParent(childIndex) {     return this.getParentIndex(childIndex) >= 0;   }     hasLeftChild(parentIndex) {     return this.getLeftChildIndex(parentIndex) < this.arr.length;   }     hasRightChild(parentIndex) {     return this.getRightChildIndex(parentIndex) < this.arr.length;   }     isEmpty() {     return !this.arr.length;   }     swap(indexOne, indexTwo) {     const tmp = this.arr[indexTwo];     this.arr[indexTwo] = this.arr[indexOne];     this.arr[indexOne] = tmp;   }     push(item) {     this.arr.push(item);     this.heapifyUp();     return this;   }     heapifyUp(startIndex) {     let currentIndex = startIndex || this.arr.length - 1;       while (       this.hasParent(currentIndex)       && !this.isCorrectOrder(this.parent(currentIndex), this.arr[currentIndex])     ) {       let parentIndex = this.getParentIndex(currentIndex);       this.swap(currentIndex, parentIndex);       currentIndex = parentIndex;     }   }     peek() {     if (this.arr.length === 0) {       return null;     }       return this.arr[0];   }     pop() {     if (this.arr.length === 0) {       return null;     }       if (this.arr.length === 1) {       return this.arr.pop();     }       const item = this.arr[0];       this.arr[0] = this.arr.pop();     this.heapifyDown();       return item;   }     heapifyDown(customStartIndex = 0) {     let currentIndex = customStartIndex;     let nextIndex = null;       while (this.hasLeftChild(currentIndex)) {       if (         this.hasRightChild(currentIndex)         && this.isCorrectOrder(this.rightChild(currentIndex), this.leftChild(currentIndex))       ) {         nextIndex = this.getRightChildIndex(currentIndex);       } else {         nextIndex = this.getLeftChildIndex(currentIndex);       }         if (this.isCorrectOrder(         this.arr[currentIndex],         this.arr[nextIndex],       )) {         break;       }         this.swap(currentIndex, nextIndex);       currentIndex = nextIndex;     }   } }      
  • Прекрасная визуализация работы кучи.

Заключение

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

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

В следующей статье мы пойдем еще дальше и поговорим самой нелинейной структуре – графах – и алгоритмах работы с ней.

***

Больше полезной информации вы найдете на наших телеграм-каналах «Библиотека программиста» и «Книги для программистов».

Интересно, перейти к каналу «Библиотека программиста»

  • 1 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Свежие комментарии

    Рубрики

    About Author 01.

    blank
    Roman Spiridonov

    Моя специальность - Back-end Developer, Software Engineer Python. Мне 39 лет, я работаю в области информационных технологий более 5 лет. Опыт программирования на Python более 3 лет. На Django более 2 лет.

    Categories 05.

    © Speccy 2020 / All rights reserved

    Связаться со мной
    Close