[原文] Структуры данных, которые должны знать новички: дерево

Node.js база данных внешний интерфейс алгоритм

Оригинальная ссылка:Tree Data Structures for Beginners

Адрес перевода Чжунчэн:Структуры данных, которые должны знать новички: дерево

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

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

Tree Data Structures for Beginners

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

Эта статья является частью следующих руководств:

Структуры данных и алгоритмы (DSA), которые должны знать новички

  1. Временная сложность алгоритмов и нотация Big O
  2. Восемь сложностей со временем, которые должен знать каждый программист
  3. Структуры данных, которые должны знать новички: массив, HashMap и список (перевод)
  4. Структуры данных, которые должны знать новички: граф (перевод)
  5. Структуры данных, которые должны знать новички: дерево👈 Это эта статья
  6. Самобалансирующееся бинарное дерево поиска
  7. Приложение I: Анализ рекурсивных алгоритмов

Основные понятия деревьев

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

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

Вот некоторые свойства дерева:

  • Самый верхний узел называетсякорень(корневой) узел (Примечание переводчика: узел без какого-либо родительского узла).
  • Узел без дочерних элементов называетсялистлистовой узел илиТерминалузел (терминальный узел).
  • деревоПроводить(Высота) — это расстояние (то есть количество ребер) между самым глубоким листовым узлом и корневым узлом.
    • AСтепень 3.
    • IСтепень равна 0.
  • глубина(Глубина) илиуровень(уровень) — это расстояние между узлом и корневым узлом.
    • HУровень 2.
    • BУровень 1.

Простая реализация дерева

Как мы видели ранее, узел дерева имеет значение и содержит ссылки на каждого из своих потомков.

Ниже приведены примеры узлов:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.descendents = [];
  }
}

Мы можем создать дерево с тремя листовыми узлами:

// create nodes with values
const abe = new TreeNode('Abe');
const homer = new TreeNode('Homer');
const bart = new TreeNode('Bart');
const lisa = new TreeNode('Lisa');
const maggie = new TreeNode('Maggie');
// associate root with is descendents
abe.descendents.push(homer);
homer.descendents.push(bart, lisa, maggie);

Вот и все, у нас есть дерево!

Simpson tree data structure

узелabeдакореньузел и узелbart,lisaа такжеmaggieэто это дереволистузел. Обратите внимание, что узел дерева может иметь любое количество дочерних элементов, будь то 0, 1, 3 или более.

бинарное дерево

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

Бинарное дерево — одна из самых распространенных форм дерева, оно широко используется, например:

  • Maps
  • Sets
  • база данных
  • приоритетная очередь
  • Найдите соответствующую информацию в LDAP (Lightweight Directory Access Protocol).
  • В файлах XML/HTML поиск выполняется с использованием интерфейса объектной модели документа (DOM).

совершенное бинарное дерево, полное бинарное дерево, совершенное бинарное дерево

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

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

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

На следующем рисунке показан пример описанной выше концепции:

Full vs. Complete vs. Perfect Binary Tree

Совершенное бинарное дерево, совершенное бинарное дерево и совершенное бинарное дерево не всегда исключают друг друга:

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

Двоичное дерево поиска (BST)

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

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

Давайте вместе реализуем бинарное дерево поиска!

Внедрение BST

Реализация BST аналогична реализации дерева выше, но с двумя отличиями:

  • Узел может иметь не более двух потомков.
  • Значение узла удовлетворяет следующему соотношению:左子节点 < 父节点 < 右子节点.

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

const LEFT = 0;
const RIGHT = 1;
class TreeNode {
  constructor(value) {
    this.value = value;
    this.descendents = [];
    this.parent = null;
    //译者注：原文并没有以下两个属性，但不加上去话下文的实现会报错
    this.newNode.isParentLeftChild = false;
    this.meta = {};  
  }
  get left() {
    return this.descendents[LEFT];
  }
  set left(node) {
    this.descendents[LEFT] = node;
    if (node) {
      node.parent = this;
    }
  }
  get right() {
    return this.descendents[RIGHT];
  }
  set right(node) {
    this.descendents[RIGHT] = node;
    if (node) {
      node.parent = this;
    }
  }
}

Хорошо, теперь вы можете добавить левый и правый дочерние узлы. Далее класс BST будет написан так, чтобы он удовлетворял左子节点 < 父节点 < 右子节点.

class BinarySearchTree {
  constructor() {
    this.root = null;
    this.size = 0;
  }
  add(value) { /* ... */ }
  find(value) { /* ... */ }
  remove(value) { /* ... */ }
  getMax() { /* ... */ }
  getMin() { /* ... */ }
}

Давайте сначала напишем код, связанный со вставкой нового узла.

Вставка узлов BST

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

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

Проиллюстрируем на следующем примере, где 30, 40, 10, 15, 12, 50 будут вставлены в дерево:

Inserting nodes on a Binary Search Tree (BST)

Код реализован следующим образом:

add(value) {
  const newNode = new TreeNode(value);
  if (this.root) {
    const { found, parent } = this.findNodeAndParent(value);
    if (found) { // duplicated: value already exist on the tree
      found.meta.multiplicity = (found.meta.multiplicity || 1) + 1;
    } else if (value < parent.value) {
      parent.left = newNode;
      //译者注：原文并没有这行代码，但不加上去的话下文实现会报错
      newNode.isParentLeftChild = true;
    } else {
      parent.right = newNode;
    }
  } else {
    this.root = newNode;
  }
  this.size += 1;
  return newNode;
}

Мы использовали имяfindNodeAndParentвспомогательная функция. Если узел (с тем же значением, что и вновь вставленный узел) уже существует в дереве, то увеличьте счетчик статистических дубликатов узла на единицу. Посмотрите, как реализована эта вспомогательная функция:

findNodeAndParent(value) {
  let node = this.root;
  let parent;
  while (node) {
    if (node.value === value) {
      break;
    }
    parent = node;
    node = ( value >= node.value) ? node.right : node.left;
  }
  return { found: node, parent };
}

findNodeAndParentПоиск значений по структуре дерева. Он начинается с корневого узла и ищет слева или справа в зависимости от значения узла. Если узел с таким же значением уже существует, функция возвращает найденный узел (то есть узел с таким же значением) и его родителя. Если нет узла с таким же значением, возвращает последний найденный узел (тот, который должен стать родителем вновь вставленного узла).

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

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

удалить листовые узлы (т.е. узлы, у которых нет дочерних элементов)

    30                             30
 /     \         remove(12)     /     \
10      40       --------->    10      40
  \    /  \                      \    /  \
  15  35   50                    15  35   50
  /
12*

Просто удалите ссылку на узел №12, сохраненную в родительском узле (т.е. узел №15).

удалить узел, у которого есть один дочерний элемент

    30                              30
 /     \         remove(10)      /     \
10*     40       --------->     15      40
  \    /  \                            /  \
  15  35   50                         35   50

В этом случае мы заменяем ссылку на дочерний узел № 10, хранящуюся в родительском узле № 30, ссылкой на дочерний узел № 15 дочернего узла.

удалить узел с двумя дочерними элементами

   30                              30
 /     \         remove(40)      /     \
15      40*      --------->     15      50
       /  \                            /
      35   50                         35

У удаляемого узла № 40 есть два потомка (№ 35 и № 50). Мы заменяем удаляемый узел узлом № 50. Левый дочерний узел № 35, подлежащий удалению, останется на месте, но его родительский узел будет заменен.

Другой способ удалить узел № 40 — переместить левый дочерний узел № 35 на позицию узла № 40, оставив положение правого дочернего узла без изменений.

    30
 /     \
15      35
          \
           50

Любая форма хороша, потому что обе они следуют принципам бинарного дерева поиска:左子节点 < 父节点 < 右子节点.

удалить корневой узел

   30*                            50
 /     \       remove(30)      /     \
15      50     --------->     15      35
       /
      35

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

Следующая анимация является конкретной демонстрацией описанной выше операции:

Removing a node with 0, 1, 2 children from a binary search tree

В анимации перемещаемый узел является левым дочерним узлом или левым поддеревом, а положение правого дочернего узла или правого поддерева остается неизменным.

Идея по удалению узлов уже есть, давайте ее реализуем:

remove(value) {
  const nodeToRemove = this.find(value);
  if (!nodeToRemove) return false;
  // Combine left and right children into one subtree without nodeToRemove
  const nodeToRemoveChildren = this.combineLeftIntoRightSubtree(nodeToRemove);
  if (nodeToRemove.meta.multiplicity && nodeToRemove.meta.multiplicity > 1) {
    nodeToRemove.meta.multiplicity -= 1; // handle duplicated
  } else if (nodeToRemove === this.root) {
    // Replace (root) node to delete with the combined subtree.
    this.root = nodeToRemoveChildren;
    this.root.parent = null; // clearing up old parent
  } else {
    const side = nodeToRemove.isParentLeftChild ? 'left' : 'right';
    const { parent } = nodeToRemove; // get parent
    // Replace node to delete with the combined subtree.
    parent[side] = nodeToRemoveChildren;
  }
  this.size -= 1;
  return true;
}

Вот некоторые моменты, на которые стоит обратить внимание при реализации:

  • Сначала проверьте, существует ли удаляемый узел. Если он не существует, вернитеfalse.
  • Если удаляемый узел существует, его левое поддерево объединяется с правым поддеревом, образуя новое поддерево.
  • Замените удаляемый узел объединенным поддеревом.

Функция объединения левого поддерева в правое поддерево выглядит следующим образом:

combineLeftIntoRightSubtree(node) {
  if (node.right) {
    //译者注：原文是  getLeftmost，寻找左子树最大的节点，这肯定有问题，应该是找最小的节点才对
    const leftLeast = this.getLefLeast(node.right);  
    leftLeast.left = node.left;
    return node.right;
  }
  return node.left;
}

Как показано в примере ниже, мы хотим удалить узел № 30 и интегрировать левое поддерево удаляемого узла в правое поддерево.В результате получается следующее:

   30*                             40
 /     \                          /  \
10      40    combine(30)       35   50
  \    /  \   ----------->      /
  15  35   50                  10
                                \
                                 15

Теперь возьмите корень нового поддерева в качестве корня всего двоичного дерева, и узел № 30 больше не будет существовать!

обход бинарного дерева

В соответствии с порядком обхода существует несколько форм обхода бинарного дерева: обход по порядку, обход в прямом порядке и обход в обратном порядке. В то же время мы также можем использовать структуры данных, которые должны знать новички: Graph (переводDFS или BFS научились в статье обходить все дерево. Ниже приведена конкретная реализация:

Неупорядоченный обход(Обход по порядку)

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

* inOrderTraversal(node = this.root) {
    if (node.left) { yield* this.inOrderTraversal(node.left); }
    yield node;
    if (node.right) { yield* this.inOrderTraversal(node.right); }
  }

В качестве примера возьмем следующее дерево:

         10
       /    \
      5      30
    /       /  \
   4       15   40
 /
3

Неупорядоченный обход выведет соответствующие значения в следующем порядке: 3, 4, 5, 10, 15, 30, 40. То есть, если дерево для обхода является бинарным деревом поиска, порядок выходных значений будет возрастающим.

пост-порядковый обход(Обход после заказа)

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

* postOrderTraversal(node = this.root) {
    if (node.left) { yield* this.postOrderTraversal(node.left); }
    if (node.right) { yield* this.postOrderTraversal(node.right); }
    yield node;
  }

Обход в обратном порядке выведет соответствующие значения в следующем порядке: 3, 4, 5, 15, 40, 30, 10.

Обход предварительного заказа и DFS(Обход предварительного заказа)

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

* preOrderTraversal(node = this.root) {
    yield node;
    if (node.left) { yield* this.preOrderTraversal(node.left); }
    if (node.right) { yield* this.preOrderTraversal(node.right); }
  }

Обход предварительного порядка выведет соответствующие значения в следующем порядке: 10, 5, 4, 3, 30, 15, 40. Порядок поиска в глубину (DPS) постоянный.

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

BFS деревьев можно реализовать очередями:

* bfs() {
    const queue = new Queue();
    queue.add(this.root);
    while (!queue.isEmpty()) {
      const node = queue.remove();
      yield node;
      node.descendents.forEach(child => queue.add(child));
    }
  }

BFS будет выводить соответствующие значения в следующем порядке: 10, 5, 30, 4, 15, 40, 3.

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

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

Предполагая, что числа добавляются в порядке возрастания:

Inserting values in ascending order in a Binary Search Tree

В левой части дерева нет узлов! Поиск элементов в таком несбалансированном дереве занимает не меньше времени, чем использование связного списка, какO(n). 😱

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

Нужно найти способ сделать дерево сбалансированным!

если деревоостаток средств, поиск элемента больше не требует обхода всех элементов, а временная сложность снижается доO(log n). Давайте рассмотрим, что означает сбалансированное дерево.

Balanced vs unbalanced Tree

Если вы ищете узел со значением 7 в несбалансированном дереве, вам нужно перейти от узла № 1 вниз к узлу № 7. Однако в сбалансированном дереве после того, как мы по очереди посетим #4, #6, следующий узел достигнет #7. По мере увеличения размера дерева производительность (несбалансированных деревьев) становится все хуже и хуже. Если в дереве миллионы узлов, то для нахождения несуществующего элемента потребуются миллионы посещений по сравнению с 20 в сбалансированном дереве! Это разные миры!

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

Суммировать

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

  • Дерево — это структура данных, узлы которой имеют 0 или более дочерних элементов.
  • У деревьев нет циклов, у графов есть.
  • В бинарном дереве каждый узел имеет не более двух дочерних элементов.
  • В бинарном дереве, когда значение левого дочернего узла меньше значения узла, а значение правого дочернего узла больше значения узла, дерево называетсябинарное дерево поиска.
  • Доступ к дереву можно получить в предварительном порядке, в обратном порядке и в порядке.
  • Временная сложность поиска в несбалансированном дереве равнаO(n). 🤦🏻
  • Временная сложность поиска в сбалансированном дереве равнаO(log n). 🎉
Категории