Структуры данных: Деревья I

Эта статья из двух частей будет посвящена древовидным структурам данных. В первой части мы рассмотрим, что такое древовидная структура данных, типы древовидных структур данных и некоторые приложения/случаи использования древовидных структур данных. Во второй части мы рассмотрим реализацию древовидной структуры данных в 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

Оцените статью
Procodings.ru
Добавить комментарий