Нежное знакомство с деревьями 🌳

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

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

Линейная структура данных:

«Структура данных - это линейная структура данных, если ее элементы данных (элементы) образуют последовательность или линейный список».

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

Нелинейная структура данных:

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

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

«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их отношениях ». ~ Линус Торвальдс

При этом можно принять во внимание следующие факторы:

1. Что нужно хранить?
2. Стоимость операции.
3. Использование или потребление памяти.
4. Легкость реализации.

Обратимся к слону в комнате.

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

Вот семейное древо Старков из Игры престолов.

Глядя на это дерево, мы можем легко определить отношения между каждым персонажем.

Мы можем сказать, что Rickard и Unknown (еще предстоит раскрыть) являются бабушками и дедушками Arya и ее братьев и сестер, то есть Robb, Sansa, Bran Rickon и Eddard & Catelyn являются их родителями.

Также Arya и Jon Snow двоюродные братья, потому что их родители - братья и сестры. Надеюсь, Джон Сноу хотя бы знает об этом 😄.

Вот еще один пример, показывающий дерево каталога в файловой системе.

Терминология дерева:

  Sample tree
  -----------
       j    <-- root
     /   \
    f      k  
  /   \      \  <-- edge
 a     h      z    <-- leaves

• node: базовый объект в дереве, который может содержать data или value и ссылки на другие nodes. Можно сказать, что дерево - это совокупность этих узлов. В приведенном выше примере дерева j, f, k, a, h и z являются узлами дерева.
• root: самый верхний узел дерева. j - корневой узел.
• children: f и k - дети j. Аналогичным образом a и h являются дочерними элементами f, а z - дочерними элементами k.
• parent: j является родителем f и k, а также дедушкой a, h и z.
• sibling: дети, имеющие одного и того же родителя, называются братьями и сестрами. f и k брат и сестра. a и h тоже братья и сестры. Но z двоюродный брат a и h, потому что их родители - братья и сестры.
• leaf: узел без дочерних узлов называется leaf узлом. Здесь a, h и z - листовой узел.
• edge: Узлы соединены ребрами. Иногда края также обозначаются как links.

Свойства дерева:

   Sample tree
   -----------
       j    <-- root - L-0
     /   \
    f      k         - L-1
  /   \      \  
 a     h      z      - L-2  

1. Дерево с n узлами будет иметь точно n-1 ребра или связи (дерево с только корневым узлом имеет 0 связь / ребро). В образце дерева у нас 6 узлов и 5 ребер (6-1).
2. Глубина узла x = длина пути от root до узла x. Длина пути - это в основном количество ребер на пути. Таким образом, мы можем сказать, что глубина узла x - это количество ребер на пути от root до x. Глубина корневого узла равна 0. В примере дерева глубина узлов f и k равна 1, а глубина узлов a, h и z равна 2. Узлы с одинаковой глубиной имеют тот же уровень, что и в дереве. . Мы видим, что f и k имеют одинаковую глубину и находятся на одном уровне L-1.
3. Высота узла x = количество ребер на самом длинном пути от x до leaf узла. Высота узла leaf равна 0, а высота пустого дерева считается равной -1. Высота дерева может быть определена высотой узла root.

Примечание. В некоторых книгах под глубиной узла x понимается количество узлов на пути от root до узел x. В этом случае глубина узла root будет равна 1. Аналогично, высота узла x также называется числом узлов на самом длинном пути от узла x до leaf node, что означает, что высота узла leaf будет равна 1, а высота пустого дерева будет равна 0 вместо -1. В этой серии публикаций мы рассмотрим это определение высоты и глубины. Подробное обсуждение глубины и высоты вы можете прочитать здесь.

class Tree {
  constructor(...children) {
    this.children = children;
  }
countLeaves() {
    if (!this.children.length) {
      return 1;
    }
    return this.children.reduce((leaves, child) => {
      return leaves + child.countLeaves();
    }, 0);
  }
}
const tree = new Tree(new Tree(new Tree()), new Tree());
console.log(tree.countLeaves()); // 2 leaves