Rivalry2

HTML Diff

1 added 1 removed

Original 2026-01-01

Modified 2026-03-10

1 <ul><li><a>Определение</a></li>

2 <li><a>Связанные определения</a></li>

3 <li><a>Области применения</a></li>

4 <li><a>Виды</a><ul><li><a>Древо поиска</a></li>

5 </ul></li>

6 <li><a>Реализация в коде</a></li>

7 <li><a>Операции над древами поиска</a><ul><li><a>Поиск</a></li>

8 <li><a>Вставка</a></li>

9 <li><a>Удаление</a></li>

10 <li><a>Обход</a></li>

11 </ul></li>

12 </ul><p>Хранение данных может быть организовано разными способами. Один из вариантов - использовать двоичное дерево. Соответствующий прием позволяет обойти ограничения, действующие в линейной структуризации информации. В последней не поддерживается возможность быстрого поиска компонентов одновременно. У бинарных деревьев соответствующая "опция" есть.</p>

13 <p>Сегодня предстоит изучить двоичные древа получше. Необходимо выяснить, что они собой представляют, для каких целей используются. Также предстоит изучить основные составляющие деревьев.</p>

14 <h2>Определение</h2>

15 <p>Дерево - это структура данных, которая представляет собой древовидную структуру в виде некоторого набора связанных между собой узлов.</p>

16 <p>Бинарное дерево - конечное множество элементов, которое или пусто, или содержит в себе элемент (корень), связанный с двумя разными бинарными древами. Это - левое и правое поддерево. Каждый элемент здесь выступает в качестве узла. Связи между ними - это ветви.</p>

17 - <p>Бинарные деревья - иерархические структуры данных. В них каждый узел может иметь не более двух потомков (детей). Обычно первый компонент выступает в качестве "родителя", а "дети" - это правые и левые наследниками. Такая информационная структура является упорядоченным ориентированным деревом.</p>

17 + <p>Бинарные деревья - иерархические структуры данных. В них каждый узел может иметь не более двух потомков (детей). Обычно первый компонент выступает в качестве "родителя", а "дети" - это правые и левые наследниками. Такая информационная струк��ура является упорядоченным ориентированным деревом.</p>

18 <p>Выше можно увидеть графическую интерпретацию рассматриваемого компонента. Здесь:</p>

19 <ul><li>A - корень;</li>

20 <li>B - корень левого поддерева;</li>

21 <li>C - корень правого поддерева.</li>

22 </ul><p>Корень всего древа располагается на уровне с минимальным значением.</p>

23 <h2>Связанные определения</h2>

24 <p>На примере ранее представленного бинарного дерева стоит познакомиться с несколькими связанными с этим элементом терминами. Они помогут лучше разобраться в двоичных информационных структурах и работать с ними.</p>

25 <p>Так, узел D в ранее представленном примере расположен непосредственно под узлом B. Он называется потомком. Если D размещается на уровне i, то B - на уровне i-1. B выступит в качестве предка D.</p>

26 <p>Глубиной или высотой древа называется максимальный уровень элемента рассматриваемой структуры. Если элемент не имеет потомков, он будет называться листом или терминальным узлом. Остальные составляющие - внутренние узлы (узлы ветвления).</p>

27 <p>Степень узла - это число потомков внутреннего узла. Максимальная степень всех имеющихся в структуре узлов - степень двоичного дерева. Длина пути - это количество веток, которое необходимо пройти в направлении от корня к узлу. Корень обладает нулевой длиной пути, узел на уровне i - длину, равную i.</p>

28 <h2>Области применения</h2>

29 <p>Иерархические структуры (деревья) широко используются. Они пригодятся тогда, когда в точке вычислительного процесса необходимо принять одно из двух возможных решений. В реальной жизни оно встречается повсеместно.</p>

30 <p>Наиболее распространенной задачей, решаемой через деревья, является выполнение операции p с каждым элементом древа. В качестве p рассматривается параметр более общей задачи посещения всех компонентов структуры или задачи обхода имеющегося дерева.</p>

31 <h2>Виды</h2>

32 <p>Двоичное дерево можно построить для принятия оптимального решения из заданного спектра. Оно может быть нескольких видов:</p>

33 <ol><li>Завершенное. У него каждый уровень, кроме последнего, является полностью заполненным. Заполнение последнего уровня производится в направлении слева направо.</li>

34 <li>Полное. Такие бинарные деревья предусматривают у каждого узла два или ноль дочерних компонентов.</li>

35 </ol><p>Оба подвида древовидных структур активно используются на практике. Они носят названия деревьев поиска и бинарных куч. Далее эти структуры будут рассмотрены более детально.</p>

36 <h3>Древо поиска</h3>

37 <p>Двоичное дерево поиска значительно отличается от обычных древ, упомянутых ранее. Они будут хранить информацию в отсортированном виде. Соответствующая операция организована по следующим принципам:</p>

38 <ul><li>значения в узлах левого дочернего поддерева меньше значения "родителя";</li>

39 <li>значения в узлах правого дочернего поддерева больше значения "родителя";</li>

40 <li>каждый дочерний узел - это тоже двоичное древо поиска.</li>

41 </ul><p>За счет такой концепции хранения данных поиск информации занимает O(logN). Это намного меньше, чем при хранении информации в виде списков - O(N).</p>

42 <p>Выше - наглядная интерпретация двоичного древа поиска и пример массива, с которым предстоит работать. Поиск здесь осуществляется при помощи метода половинного деления - дихотомии. Выше можно заметить, что аналогичная операция и на массиве, и на дереве поиска будет выполняться за 3 шага. В списке подобная операция отнимет 10 шагов.</p>

43 <h2>Реализация в коде</h2>

44 <p>Строить рассматриваемую структуру предлагается не только графически или от руки, но и в виде программного кода. Она встречается в Java, Python и других языках программирования. Перед ее построением необходимо помнить о таких правилах как:</p>

45 <ul><li>дочерних узлов у дерева должно быть не больше двух штук;</li>

46 <li>дочерние узлы должны быть бинарными древами;</li>

47 <li>дочерние узлы называются правыми и левыми - в зависимости от их расположения.</li>

48 </ul><p>В указанных условиях изучаемый компонент будет иметь следующую интерпретацию в программном коде:</p>

49 <p>А вот так - на Java и Python соответственно:</p>

50 <p>Теперь необходимо расширить имеющийся класс и реализовать в нем операции для взаимодействия с проектируемым классом.</p>

51 <h2>Операции над древами поиска</h2>

52 <p>Над двоичными деревьями поиска допустимо выполнять разнообразные операции. К ним можно отнести:</p>

53 <ul><li>поиск;</li>

54 <li>вставку узла;</li>

55 <li>удаление узла;</li>

56 <li>выполнение обхода дерева.</li>

57 </ul><p>Каждая представленная операция имеет свои ключевые особенности. Все перечисленные манипуляции предстоит изучить более подробно.</p>

58 <h3>Поиск</h3>

59 <p>Если искомое значение древа поиска меньше узлового значения, оно может размещаться только в левом поддереве. Если необходимый параметр больше узлового, оно расположено только в правом поддереве. Все это приводит к возможности использования рекурсивного подхода и операции поиска так:</p>

60 <p>Выше представлена не только структура, но и реализация поиска на Java и Python соответственно. Остальные операции над древами будут тоже базироваться на применении упомянутых языков разработки соответственно.</p>

61 <h3>Вставка</h3>

62 <p>Все значения дерева, которые меньше текущего узлового, допустимы для размещения только в левом поддереве. Те, что больше, - в правом. Для вставки нового узлового параметра требуется проверить текущий на отсутствие пустоты. Далее возможны два варианта развития событий:</p>

63 <ol><li>Если узловой параметр не пустой, его значение сравнивается со вставляемым. В зависимости от полученного результата проводится проверка правого или левого поддеревьев.</li>

64 <li>Если узловой параметр пуст, создается новый. Он заполняется ссылкой на текущий узел в качестве родительского компонента.</li>

65 </ol><p>Вставка пользуется рекурсивным подходом подобно поиску. Вот так выглядит этот алгоритм на JavaScript, а также на Java и Python соответственно:</p>

66 <p>Другие операции над двоичными деревьями поиска и их компонентами тоже возможны. Речь идет об удалении элементов и обходе древа.</p>

67 <h3>Удаление</h3>

68 <p>Для удаления компонента в связанном списке требуется отыскать его, а также ссылку на следующий компонент перенести в поле ссылки на предыдущем. Если нужно удалить корневой узел или промежуточные вершины с сохранением общей структуры древа, предстоит выбрать один из нескольких методов.</p>

69 <p>А именно:</p>

70 <ul><li>найти и удалить максимальный компонент левого поддерева. Его значение должно будет использоваться в качестве корневого или промежуточного узла дерева;</li>

71 <li>найти и удалить минимальный элемент правого поддерева. Соответствующий параметр выступит корнем или промежуточным узлом дерева.</li>

72 </ul><p>Оба варианта работают достаточно эффективно. Ниже - пример, для которого будет реализовано непосредственное удаление.</p>

73 <p>А вот примеры кодов, позволяющие реализовать второй подход на JS, Java и Python соответственно:</p>

74 <p>Первый вариант будет практически таким же. Только придется столкнуться с исключением - обходить в дереве нужно будет правое поддерево, а затем искать максимальное узловое значение вместо минимального.</p>

75 <h3>Обход</h3>

76 <p>Обход - специфическая, но очень важная операция. Так называется последовательное единоразовое посещение всех вершин древа. Обходы совершаются несколькими способами:</p>

77 <ol><li>Прямо. В этом случае направление обхода: корень-левое поддерево-правое поддерево.</li>

78 <li>Централизованно. Предстоит сначала обойти левое поддерево, затем - корень, а потом уже - правое поддерево.</li>

79 <li>Обратно. Обход осуществляется от левого поддерева к правому, а затем - к корню.</li>

80 </ol><p>Такие операции носят название поиска в глубину. На каждом шаге итератор будет стараться продвинуться вниз по дереву вертикально перед тем, как перейти к родственному узлу - узлу на том же уровне. Также есть поиск в ширину. Это когда обход дерева по уровням производится от корня и далее.</p>

81 <p>Поиск в глубину может проводиться при помощи рекурсии или стеков. А в ширину - только за счет использования очереди:</p>

82 <p>На Java это выглядит так:</p>

83 <p>А так - на Python:</p>

84 <p>Что такое бинарное дерево, ясно. Лучше работать с ними на языках программирования помогут дистанционные компьютерные курсы.</p>

85 <p><em>Хотите освоить современную IT-специальность? Огромный выбор курсов по востребованным IT-направлениям есть в <a>Otus</a>!</em> </p>