Rivalry2

HTML Diff

1 added 21 removed

Original 2026-01-01

Modified 2026-02-26

1 Организация хранения данных в виде дерева позволяет обойти ограничения линейной структуры данных. Например, в последней нельзя организовать быстрыми поиск и вставку элементов одновременно. При этом в иерархической структуре данных можно эффективно выбирать и обновлять большие объемы данных.

2 Один из наиболее часто используемых и простых в реализации подвидов деревьев - бинарные деревья. Помимо организации поиска, бинарные деревья используют, когда разбирают математические выражения и компьютерные программы. Еще их используют, чтобы хранить данные для алгоритмов сжатия, а также они лежат в основе других структур данных, например, очереди с приоритетом, кучи и словари.

3 В этом уроке мы познакомимся с устройством и особенностями бинарных деревьев и разберем основные операции с его узлами.

4 <h2>Что такое бинарные деревья</h2>

5 Бинарное деревоилидвоичное дерево- это дерево, в котором у каждого из его узлов не более двух дочерних узлов. При этом каждый дочерний узел тоже представляет собой бинарное дерево.

6 Рассмотрим примеры деревьев на следующем рисунке:

7 Дерево (а) - бинарное. У каждого его узла не более двух дочерних узлов, у каждого из которых тоже не более двух дочерних. Например, узлы E, G, H, I и K - листовые, значит, у них ноль дочерних узлов. У узла C только один дочерний узел, а у узлов A, B, D и F по два дочерних.

8 Как только правило двух дочерних нарушается, то дерево перестает относиться к классу бинарных. Так, дерево (б) не является бинарным, так как у узла E три дочерних узла.

9 Благодаря тому, что дочерних узлов всегда не больше двух, их называютправыйилевыйдочерние узлы.

10 Напомним, что есть завершенное и полное деревья. Для бинарных деревьев они приобретают следующий вид:

11 <ul><li>Завершенное бинарное дерево- это бинарное дерево, в котором каждый уровень, кроме последнего, полностью заполнен, а заполнение последнего уровня производится слева направо</li>

12 <li>Полное бинарное дерево- это бинарное дерево, в котором у каждого узла ноль или два дочерних узла</li>

13 </ul>На практике чаще применяются два подвида бинарных деревьев: бинарные деревья поиска и бинарные кучи. Последние разберем в следующих уроках, а в этом сосредоточимся на первых.

14 <h2>Что такое бинарные деревья поиска</h2>

15 Бинарные деревья поискаотличаются от обычных бинарных деревьев тем, что хранят данные в отсортированном виде. Хранение значений внутри бинарного дерева поиска организовано в следующем виде:

16 - <ul><li>��се значения в узлах левого дочернего поддерева меньше значения родительского узла</li>

16 + <ul><li>Все значения в узлах левого дочернего поддерева меньше значения родительского узла</li>

17 <li>Все значения в узлах правого дочернего поддерева больше значения родительского узла</li>

18 <li>Каждый дочерний узел тоже является бинарным деревом поиска</li>

19 </ul>Благодаря такой структуре хранения данных поиск узла в бинарном дереве поиска занимает O(logN). Это значительно меньше, если хранить значения в списках - O(N).

20 Если использовать отсортированный массив для хранения данных, скорость поиска элементов сравняется. Но при оценке времени вставки хранение в массиве значительно проигрывает работе с деревьями - O(N) против O(logN) соответственно.

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

22 Рассмотрим на примере поиска элемента (10) сравнение операций поиска в отсортированном массиве, списке и бинарном дереве поиска:

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

24 Далее поговорим о структуре бинарных деревьев и начнем реализовывать бинарное дерево в коде.

25 <h2>Как бинарные деревья поиска реализуются в коде</h2>

26 Напомним свойства бинарных деревьев:

27 <ul><li>Должно быть не более двух дочерних узлов</li>

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

29 <li>Дочерние узлы называют левыми и правыми</li>

30 </ul>В этом случае структура узла принимает следующий вид:

31 - Javascript

32 - Java

33 - Python

34 - PHP

35 Теперь нам необходимо расширить наш класс и реализовать необходимые операции, чтобы взаимодействовать с проектируемым классом. Начнем с операции поиска узла.

31 Теперь нам необходимо расширить наш класс и реализовать необходимые операции, чтобы взаимодействовать с проектируемым классом. Начнем с операции поиска узла.

36 С бинарными деревьями поиска можно выполнять следующие операции:

32 С бинарными деревьями поиска можно выполнять следующие операции:

37 <ul><li>Искать узел</li>

33 <ul><li>Искать узел</li>

38 <li>Вставлять узел</li>

34 <li>Вставлять узел</li>

39 <li>Удалять узел</li>

35 <li>Удалять узел</li>

40 <li>Выполнять обход дерева</li>

36 <li>Выполнять обход дерева</li>

41 </ul>Разберем каждую операцию подробнее.

37 </ul>Разберем каждую операцию подробнее.

42 <h3>Поиск узла</h3>

38 <h3>Поиск узла</h3>

43 Если искомое значение бинарного дерева поиска меньше значения узла, то оно может находиться только в левом поддереве. Искомое значение, которое больше значения узла, может быть только в правом поддереве. В таком случае мы можем применить рекурсивный подход и операция поиска будет выглядеть так:

39 Если искомое значение бинарного дерева поиска меньше значения узла, то оно может находиться только в левом поддереве. Искомое значение, которое больше значения узла, может быть только в правом поддереве. В таком случае мы можем применить рекурсивный подход и операция поиска будет выглядеть так:

44 - Javascript

45 - Java

46 - Python

47 - PHP

48 <h3>Вставка узла</h3>

40 <h3>Вставка узла</h3>

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

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

50 <ul><li>Если это так, сравниваем значение со вставляемым. По результату сравнения проводим проверку для правого или левого поддеревьев</li>

42 <ul><li>Если это так, сравниваем значение со вставляемым. По результату сравнения проводим проверку для правого или левого поддеревьев</li>

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

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

52 </ul>Операция вставки использует рекурсивный подход аналогично операции поиска. Переведем данный алгоритм на язык JavaScript и получим следующий код метода вставки:

44 </ul>Операция вставки использует рекурсивный подход аналогично операции поиска. Переведем данный алгоритм на язык JavaScript и получим следующий код метода вставки:

53 - Javascript

54 - Java

55 - Python

56 - PHP

57 <h3>Удаление узла</h3>

45 <h3>Удаление узла</h3>

58 Чтобы удалить элемент в связном списке, нужно найти его и ссылку на следующий элемент перенести в поле ссылки на предыдущем элементе.

46 Чтобы удалить элемент в связном списке, нужно найти его и ссылку на следующий элемент перенести в поле ссылки на предыдущем элементе.

59 Если необходимо удалить корневой узел или промежуточные вершины и сохранить структуру бинарного дерева поиска, выбирают один из следующих двух способов:

47 Если необходимо удалить корневой узел или промежуточные вершины и сохранить структуру бинарного дерева поиска, выбирают один из следующих двух способов:

60 <ul><li>Находим и удаляем максимальный элемент левого поддерева и используем его значение в качестве корневого или промежуточного узла</li>

48 <ul><li>Находим и удаляем максимальный элемент левого поддерева и используем его значение в качестве корневого или промежуточного узла</li>

61 <li>Находим и удаляем минимальный элемент правого поддерева и используем его значение в качестве корневого или промежуточного узла</li>

49 <li>Находим и удаляем минимальный элемент правого поддерева и используем его значение в качестве корневого или промежуточного узла</li>

62 </ul>Оба варианта приемлемы для нашего дерева. Реализуем в коде второй вариант:

50 </ul>Оба варианта приемлемы для нашего дерева. Реализуем в коде второй вариант:

63 - Javascript

64 - Java

65 - Python

66 - PHP

67 Реализация первого варианта будет выглядеть практически идентично. Только есть исключение: мы будем обходить правое поддерево и искать максимальное значение узла вместо минимального.

51 Реализация первого варианта будет выглядеть практически идентично. Только есть исключение: мы будем обходить правое поддерево и искать максимальное значение узла вместо минимального.

68 Для деревьев также существуют специфические операции, важнейшая из которых - обход дерева. Рассмотрим эту операцию подробнее.

52 Для деревьев также существуют специфические операции, важнейшая из которых - обход дерева. Рассмотрим эту операцию подробнее.

69 <h3>Обход деревьев</h3>

53 <h3>Обход деревьев</h3>

70 Когда мы поработали с деревом и нам нужно его сохранить в файл или вывести в печать, нам больше не нужен древовидный формат. Здесь мы прибегаем кобходу дерева- последовательное единоразовое посещение всех вершин дерева.

54 Когда мы поработали с деревом и нам нужно его сохранить в файл или вывести в печать, нам больше не нужен древовидный формат. Здесь мы прибегаем кобходу дерева- последовательное единоразовое посещение всех вершин дерева.

71 Существуют такие три варианта обхода деревьев:

55 Существуют такие три варианта обхода деревьев:

72 <ul><li>Прямой обход (КЛП): корень → левое поддерево → правое поддерево</li>

56 <ul><li>Прямой обход (КЛП): корень → левое поддерево → правое поддерево</li>

73 <li>Центрированный обход (ЛКП): левое поддерево → корень → правое поддерево</li>

57 <li>Центрированный обход (ЛКП): левое поддерево → корень → правое поддерево</li>

74 <li>Обратный обход (ЛПК): левое поддерево → правое поддерево → корень</li>

58 <li>Обратный обход (ЛПК): левое поддерево → правое поддерево → корень</li>

75 </ul>Такие обходы называютсяпоиском в глубину*. На каждом шаге итератор пытается продвинуться вертикально вниз по дереву перед тем, как перейти к родственному узлу - узлу на том же уровне. Еще естьпоиск в ширину- обход узлов дерева по уровням: от корня и далее:

59 </ul>Такие обходы называютсяпоиском в глубину*. На каждом шаге итератор пытается продвинуться вертикально вниз по дереву перед тем, как перейти к родственному узлу - узлу на том же уровне. Еще естьпоиск в ширину- обход узлов дерева по уровням: от корня и далее:

76 Реализация поиска в глубину может осуществляться или с использованием рекурсии, или с использованием стека. А поиск в ширину реализуется за счет использования очереди:

60 Реализация поиска в глубину может осуществляться или с использованием рекурсии, или с использованием стека. А поиск в ширину реализуется за счет использования очереди:

77 - Javascript

78 - Java

79 - Python

80 - PHP

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

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

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

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