Эта статья из двух частей будет посвящена древовидным структурам данных. В первой части мы рассмотрим, что такое древовидная структура данных, типы древовидных структур данных и некоторые приложения/случаи использования древовидных структур данных. Во второй части мы рассмотрим реализацию древовидной структуры данных в Javascript; давайте приступим к этому.
Деревья
Дерево — это нелинейная структура данных, которая используется для хранения иерархических данных, например, семейное дерево, структура сотрудников компании. Подобно связанным спискам, дерево состоит из узлов, хранящих значение и указатели на другие связанные узлы. Деревья позволяют быстро находить и организовывать данные на компьютере.
Структура древовидной структуры данных
Все деревья имеют вершину, называемую корнем; все остальные узлы являются потомками корневого узла.
Терминология дерева
Некоторые термины, используемые для описания отношений между узлами в дереве, следующие:
Родитель и Ребенок
Родительский узел относится к узлу, который непосредственно предшествует другому узлу. На рисунке выше видно, что узел [2] является родителем узлов [5, 6, 7], что также делает узлы [5,6,7] дочерними узлами узла [2]. Аналогично, узлы [9, 10] являются детьми узла [4], а узел [3] — родителем узла [8].
Sibling
Узлы, имеющие общий родительский узел, называются братьями и сестрами. Обратите внимание, что все узлы в дереве могут иметь только одного родителя, за исключением корневого узла, у которого нет родителя. На рисунке выше видно, что узлы [5, 6, 7] являются родными братьями и сестрами, также как и узлы [9, 10].
Лист
Узел, не имеющий дочерних узлов, называется листовым узлом. Узлы [5, 6, 7, 8, 9, 10] являются листовыми узлами.
Родоначальник и потомок
Предком узла называются узлы, которые имеют прямую обратную связь между данным узлом и корневым узлом; их можно считать прародителями. На рисунке выше видно, что узлы [6, 2, 1] являются предками узла [11], хотя узел [6] технически является предком узла [11], более понятно называть его родительским узлом.
Потомки — это тот же принцип, но в обратном порядке. Узел [11] является потомком узлов [6, 2, 1]. Как мы уже говорили, все узлы являются потомками узла [1], он же корневой узел.
Поддерево
Любой узел в дереве, имеющий потомков, можно считать поддеревом. Все поддеревья являются потомками корневого узла, например, узла [2] и его дочерних узлов.
Высота дерева
Высота дерева — это количество узлов/ребер между корневым узлом и его последними потомками или самыми удаленными листовыми узлами. Высота приведенного выше дерева равна 3.
Глубина узла
Глубина узла означает количество узлов/ребер между данным узлом и корневым узлом. На изображении выше глубина узла [10] равна 2.
Типы древовидных структур данных
Существует множество структур данных типа дерева, но мы рассмотрим лишь некоторые из них.
Общее дерево
Общее дерево — это дерево, которое не имеет ограничений на количество дочерних узлов, которые могут быть у родительского узла, включая корневой узел.
Бинарное дерево
Бинарное дерево — это дерево, узлы которого могут иметь не более 2 дочерних узлов на каждый родительский узел, включая корневой узел. Дочерние узлы в двоичном дереве называются левым и правым дочерними узлами.
Двоичное дерево поиска (BST)
BST — это дерево, узлы которого сортируются при создании. Узлы сортируются в зависимости от того, больше они или меньше своего родительского узла. Узлы, которые больше своего родительского узла, располагаются справа, а узлы, которые меньше, — слева.
Если вы хотите узнать, какие еще структуры данных древовидного типа существуют, прочитайте эту статью.
Использование/применение древовидных структур данных
-
Деревья используются в компьютерных файловых системах для отслеживания структуры папок.
-
BST часто используются в алгоритмах поиска и сортировки.
-
Пространство доменных имен (DNS) использует древовидные структуры данных для управления доменными именами.
-
Деревья используются при рендеринге компьютерной графики.
-
Словарные приложения, автозаполнение и проверка орфографии используют деревья.
Деревья — это очень сложная структура данных, поэтому если у вас есть вопросы, пожалуйста, оставьте комментарий, и я постараюсь ответить на них. В следующей части этой статьи мы рассмотрим, как создать BST в Javascript. Спасибо за чтение.
Часть 2
