Rivalry2

HTML Diff

0 added 4 removed

Original 2026-01-01

Modified 2026-02-26

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

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

3 <h2>Что такое деревья и для чего они нужны</h2>

4 Деревья используют, чтобы отразить в памяти компьютера иерархические взаимосвязи. Их применяют для реестра Windows, XML-документов, DOM-структур HTML-страниц, родословных, каталогов запчастей или файловых систем. Например, так файловую структуру видят конечные пользователи:

5 При этом для программистов она выглядит иначе:

6 Это древовидное представление структуры. Из этой схемы можно сделать вывод, чтодерево- это конечное множество, которое состоит извершинилиузлов, а еще есть выделенный узел -корень дерева. В примере выше вершины - это все папки, а корень дерева - "Новая папка".

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

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

9 <ul><li>Организация быстрого поиска в отсортированных данных, например, в индексах баз данных</li>

10 <li>Кластеризация данных. Возможность разбивать данные на кластеры применяется в базах данных и машинном обучении</li>

11 <li>Решение сложных арифметических выражений. Дерево используется, чтобы хранить порядок выполнения операций, значений аргументов и промежуточных результатов</li>

12 <li>Алгоритмы принятия решений. Дерево решений - инструмент интеллектуального анализа данных и проведения предсказаний. Он считается более простым в работе инструментом, чем нейросети, так как формулирует правила на естественном языке</li>

13 <li>Сетевое взаимодействие. Деревья используют для маршрутизации и работы механизмов определения IP-адресов по URL сайта, например, DNS-сервера</li>

14 </ul>Деревья часто используют в проектах по разработке программ. Как результат - разработчики выделили терминологию описания узлов и формы деревьев.

15 <h2>Какие узлы есть в деревьях</h2>

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

17 <ul><li>Родительский узелилипредок- узел, который находится на первом уровне иерархии</li>

18 <li>Дочерний узелилипотомок- узел, на который есть ссылки из рассматриваемого узла</li>

19 <li>Корневой узел- узел, на который нет ссылок из других узлов</li>

20 <li>Сестринские узлы- два узла, у которых общие родители</li>

21 <li>Листовой узел,лист дереваилитерминальный узел- узел, у которого количество поддеревьев равно нулю</li>

22 <li>Узел ветвленияиливнутренняя вершина- узел, у которого есть дочерние структуры</li>

23 </ul>Количество поддеревьев у узла называется егостепенью*. Максимальное значение степени узла -степень дерева. Если степень дерева равна двум, значит, у каждого узла может быть не более двух потомков:

24 <h2>Какие формы деревьев бывают</h2>

25 Из-за определенных особенностей задач и алгоритмов, разработчики применяют разные формы деревьев со своими особенностями организации вершин:

26 <ul><li>Упорядоченное дерево- дерево, в котором все вершины отсортированы. Такие деревья еще называютсяплоскими, так как при последовательном обходе вершин получится отсортированный массив:</li>

27 </ul>Далее в курсе мы будем считать все деревья упорядоченными, если в условии не сказано обратное.

28 <ul><li>Полное дерево- дерево, в котором количество дочерних узлов у каждой внутренней вершины равно степени дерева:</li>

29 </ul><ul><li>Завершенное дерево- дерево, у которого каждый уровень, кроме последнего, является полным:</li>

30 </ul><ul><li>Идеальное дерево- полное дерево, у которого все терминальные узлы располагаются на одном уровне:</li>

31 </ul>Мы познакомились с основной терминологией, которая используется при работе с деревьями. Теперь рассмотрим, какие есть способы представления деревьев в графическом виде и в коде.

32 <h2>Как могут выглядеть деревья</h2>

33 Чтобы изображать иерархические структуры, используют следующие варианты:

34 <ul><li>Древовидное схематическое представление</li>

35 <li>Круги Эйлера</li>

36 <li>Списки с отступами</li>

37 <li>Код</li>

38 </ul>Разберем каждый способ изображения дерева.

39 <h3>Древовидное схематическое представление</h3>

40 В качестве основного способа представления деревьев используют имена, номера вершин или содержимое полезных данных узла. Они соединяются линиями, которые обозначают связи между вершинами:

41 Этот способ похож на природные деревья, только в информатике корень дерева обычно рисуется вверху схемы.

42 <h3>Круги Эйлера</h3>

43 Мы можем изобразить алгоритмическое дерево по правилам теории множеств с помощью кругов Эйлера:

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

45 <h3>Списки с отступами</h3>

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

47 Такой формат используют при работе с книгой, так как оглавление - это дерево.

48 <h3>Код</h3>

49 Чтобы работать с деревьями, их нужно уметь не только рисовать, но и хранить в памяти компьютера.

50 В виде кода мы получаем следующий класс узла:

51 - Javascript

52 - Java

53 - Python

54 - PHP

55 Чтобы организовать из узла дерево, нужно добавить методы, которые заполняют ссылки на поддеревья child1 и child2. Как реализуются деревья в коде, разберем подробно в следующих уроках.

51 Чтобы организовать из узла дерево, нужно добавить методы, которые заполняют ссылки на поддеревья child1 и child2. Как реализуются деревья в коде, разберем подробно в следующих уроках.

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

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

57 <h2>Выводы</h2>

53 <h2>Выводы</h2>

58 Мы познакомились с такой структурой данных как деревья. Они используются, чтобы хранить информацию в иерархическом виде, индексировать и кластеризировать большие последовательности данных.

54 Мы познакомились с такой структурой данных как деревья. Они используются, чтобы хранить информацию в иерархическом виде, индексировать и кластеризировать большие последовательности данных.

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

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