0 added
8 removed
Original
2026-01-01
Modified
2026-02-26
1
<p>Древовидные структуры достаточно гибкие по своей задумке. Один и тот же набор значений можно расположить в виде дерева, если использовать разные топологические решения. В итоге два дерева с одинаковым содержимым будут обладать противоположными характеристиками, например, по скорости поиска узлов.</p>
1
<p>Древовидные структуры достаточно гибкие по своей задумке. Один и тот же набор значений можно расположить в виде дерева, если использовать разные топологические решения. В итоге два дерева с одинаковым содержимым будут обладать противоположными характеристиками, например, по скорости поиска узлов.</p>
2
<p>Ученые еще в середине прошлого века заинтересовались вопросом оптимизации хранения данных в деревьях. Они хотели обеспечить максимальную скорость поиска в них. Так появились сбалансированные деревья.</p>
2
<p>Ученые еще в середине прошлого века заинтересовались вопросом оптимизации хранения данных в деревьях. Они хотели обеспечить максимальную скорость поиска в них. Так появились сбалансированные деревья.</p>
3
<p>В этом уроке мы детально познакомимся с балансировкой деревьев, способами ребалансировки при добавлении новых узлов, а также рассмотрим новые виды древовидных структур.</p>
3
<p>В этом уроке мы детально познакомимся с балансировкой деревьев, способами ребалансировки при добавлении новых узлов, а также рассмотрим новые виды древовидных структур.</p>
4
<h2>Сбалансированные деревья</h2>
4
<h2>Сбалансированные деревья</h2>
5
<p><strong>Идеальная сбалансированность</strong>- это свойство дерева, при котором все его уровни, иногда кроме последнего, полностью заполнены.</p>
5
<p><strong>Идеальная сбалансированность</strong>- это свойство дерева, при котором все его уровни, иногда кроме последнего, полностью заполнены.</p>
6
<p>Для сравнения рассмотрим два бинарных дерева поиска, которые будут представлять собой одну последовательность элементов - 1,2,3,4,5,6. Из этой последовательности можно построить несколько деревьев, например:</p>
6
<p>Для сравнения рассмотрим два бинарных дерева поиска, которые будут представлять собой одну последовательность элементов - 1,2,3,4,5,6. Из этой последовательности можно построить несколько деревьев, например:</p>
7
<p>В дереве (б) каждый из уровней, кроме левой ветки узла 1, заполнены. Значит, дерево (б) - идеально сбалансированное дерево. Что нельзя сказать о дереве (а).</p>
7
<p>В дереве (б) каждый из уровней, кроме левой ветки узла 1, заполнены. Значит, дерево (б) - идеально сбалансированное дерево. Что нельзя сказать о дереве (а).</p>
8
<p>Дерево (а) и дерево (б) можно отнести к бинарным деревьям поиска. Но для худшего случая - поиска в дереве элемента №6 в дереве (а) - требуется выполнить шесть операций перехода между вершинами, а в случае (б) - только три.</p>
8
<p>Дерево (а) и дерево (б) можно отнести к бинарным деревьям поиска. Но для худшего случая - поиска в дереве элемента №6 в дереве (а) - требуется выполнить шесть операций перехода между вершинами, а в случае (б) - только три.</p>
9
<p>Дерево с максимально возможной высотой (а) называется<strong>разбалансированным</strong>или<strong>вырожденным деревом</strong>. Оно не отличается от двусвязного списка, значит, теряет свое основное преимущество - скорость поиска.</p>
9
<p>Дерево с максимально возможной высотой (а) называется<strong>разбалансированным</strong>или<strong>вырожденным деревом</strong>. Оно не отличается от двусвязного списка, значит, теряет свое основное преимущество - скорость поиска.</p>
10
<p>Для разбалансированных деревьев скорость составляет O(N). А для идеально сбалансированного дерева (б) поиск будет завершен за число шагов, которые не превышают высоту дерева или за O(logN).</p>
10
<p>Для разбалансированных деревьев скорость составляет O(N). А для идеально сбалансированного дерева (б) поиск будет завершен за число шагов, которые не превышают высоту дерева или за O(logN).</p>
11
<p>Состояние идеальной сбалансированности в дереве трудно поддерживать. Любое добавление или удаление узла в сбалансированном дереве может привести к ситуации, когда дерево выйдет из идеально сбалансированного состояния. В таком случае скорость поиска будет значительно деградировать после каждой вставки или удаления узла.</p>
11
<p>Состояние идеальной сбалансированности в дереве трудно поддерживать. Любое добавление или удаление узла в сбалансированном дереве может привести к ситуации, когда дерево выйдет из идеально сбалансированного состояния. В таком случае скорость поиска будет значительно деградировать после каждой вставки или удаления узла.</p>
12
<p>Чтобы вернуть дерево в сбалансированный вид, его перестраивают после каждой манипуляции с составом узлов. Рассмотрим пример с добавлением элемента №7 в наше дерево. Это можно сделать несколькими способами:</p>
12
<p>Чтобы вернуть дерево в сбалансированный вид, его перестраивают после каждой манипуляции с составом узлов. Рассмотрим пример с добавлением элемента №7 в наше дерево. Это можно сделать несколькими способами:</p>
13
<p>В случае (б) дерево вышло из состояния идеальной сбалансированности, так как оба нижних уровня не заполнены полностью. В таком случае поиск элемента №7 будет выполнен за четыре операции.</p>
13
<p>В случае (б) дерево вышло из состояния идеальной сбалансированности, так как оба нижних уровня не заполнены полностью. В таком случае поиск элемента №7 будет выполнен за четыре операции.</p>
14
<p>В случае (а) элементы были перераспределены, чтобы сохранить сбалансированное состояние. В таком случае поиск элемента №7 будет выполнен всего за три операции.</p>
14
<p>В случае (а) элементы были перераспределены, чтобы сохранить сбалансированное состояние. В таком случае поиск элемента №7 будет выполнен всего за три операции.</p>
15
<p>На таких маленьких примерах выигрыш в одну операцию во время поиска может показаться слишком незначительным, чтобы постоянно перестраивать дерево. Но при работе с деревьями из миллионов узлов и повышенных требованиях к скорости выборки такое перестроение может себя оправдать. Пользователям очень нравится, когда приложение работает со скоростью человеческой мысли.</p>
15
<p>На таких маленьких примерах выигрыш в одну операцию во время поиска может показаться слишком незначительным, чтобы постоянно перестраивать дерево. Но при работе с деревьями из миллионов узлов и повышенных требованиях к скорости выборки такое перестроение может себя оправдать. Пользователям очень нравится, когда приложение работает со скоростью человеческой мысли.</p>
16
<p>Ресурсы вычислительных машин не безграничны. Чтобы снизить нагрузку на них и одновременно с этим максимально сохранить преимущества идеально сбалансированного дерева, придумали новые виды деревьев. Среди них особенно выделяются АВЛ-деревья и красно-черные деревья, с которыми мы познакомимся подробнее.</p>
16
<p>Ресурсы вычислительных машин не безграничны. Чтобы снизить нагрузку на них и одновременно с этим максимально сохранить преимущества идеально сбалансированного дерева, придумали новые виды деревьев. Среди них особенно выделяются АВЛ-деревья и красно-черные деревья, с которыми мы познакомимся подробнее.</p>
17
<h3>АВЛ-деревья</h3>
17
<h3>АВЛ-деревья</h3>
18
<p>Этот вид деревьев представили в 1962 году двое советских ученых: Адельсон-Вельский Г.М. и Ландис Е.М. Именно по сокращению от их фамилий<strong>АВЛ-деревья</strong>и получили такое название.</p>
18
<p>Этот вид деревьев представили в 1962 году двое советских ученых: Адельсон-Вельский Г.М. и Ландис Е.М. Именно по сокращению от их фамилий<strong>АВЛ-деревья</strong>и получили такое название.</p>
19
<p>АВЛ-деревья отличаются от идеально сбалансированных. АВЛ-дерево считается сбалансированным, если для каждого узла дерева высота его правого и левого поддеревьев отличаются не более чем на единицу. Если модификация структуры узлов приводит к нарушению сбалансированности дерева, то необходимо выполнить его балансировку.</p>
19
<p>АВЛ-деревья отличаются от идеально сбалансированных. АВЛ-дерево считается сбалансированным, если для каждого узла дерева высота его правого и левого поддеревьев отличаются не более чем на единицу. Если модификация структуры узлов приводит к нарушению сбалансированности дерева, то необходимо выполнить его балансировку.</p>
20
<p>Поиск в АВЛ-дереве выполняется аналогично работе с бинарным деревом поиска. При этом благодаря поддержке возможности ребалансировки при вставки и удалении узлов в АВЛ-деревьях есть особенности реализации.</p>
20
<p>Поиск в АВЛ-дереве выполняется аналогично работе с бинарным деревом поиска. При этом благодаря поддержке возможности ребалансировки при вставки и удалении узлов в АВЛ-деревьях есть особенности реализации.</p>
21
<p>В качестве индикатора наличия разбалансированности в поддереве на узел выносят показатель баланса, который принимает значения от -1 до +1. Их значения:</p>
21
<p>В качестве индикатора наличия разбалансированности в поддереве на узел выносят показатель баланса, который принимает значения от -1 до +1. Их значения:</p>
22
<ul><li>-1 - в правом поддереве больше высота</li>
22
<ul><li>-1 - в правом поддереве больше высота</li>
23
<li>0 - поддеревья равной высоты</li>
23
<li>0 - поддеревья равной высоты</li>
24
<li>+1 - высота больше в левом поддереве</li>
24
<li>+1 - высота больше в левом поддереве</li>
25
</ul><p>В итоге код нашего узла принимает следующий вид:</p>
25
</ul><p>В итоге код нашего узла принимает следующий вид:</p>
26
-
<p><strong>Javascript</strong></p>
27
-
<p><strong>Java</strong></p>
28
-
<p><strong>Python</strong></p>
29
-
<p><strong>PHP</strong></p>
30
<p>Этот фрагмент кода определяет базовый скелет узла нашего будущего дерева. Чтобы превратить его в полноценное АВЛ-дерево, нужно добавить возможность искать и модифицировать узлы. Операцию поиска можно переиспользовать из бинарных деревьев поиска, а изменение в структуре дерева потребует дополнительной частичной ребалансировки.</p>
26
<p>Этот фрагмент кода определяет базовый скелет узла нашего будущего дерева. Чтобы превратить его в полноценное АВЛ-дерево, нужно добавить возможность искать и модифицировать узлы. Операцию поиска можно переиспользовать из бинарных деревьев поиска, а изменение в структуре дерева потребует дополнительной частичной ребалансировки.</p>
31
<p>Далее мы подробно поговорим об операциях добавления и удаления узлов в АВЛ-деревьях.</p>
27
<p>Далее мы подробно поговорим об операциях добавления и удаления узлов в АВЛ-деревьях.</p>
32
<h3>Модификация структуры узлов</h3>
28
<h3>Модификация структуры узлов</h3>
33
<p>Добавить новую вершину можно с помощью рекурсивного спуска к месту вставки нового узла. Если возвращаться к корневой вершине через каждый промежуточный узел, то добавивший новую вершину метод модифицирует значение balanceFactor. Если новое значение выходит из допустимого диапазона, то выполняется ребалансировка данного поддерева.</p>
29
<p>Добавить новую вершину можно с помощью рекурсивного спуска к месту вставки нового узла. Если возвращаться к корневой вершине через каждый промежуточный узел, то добавивший новую вершину метод модифицирует значение balanceFactor. Если новое значение выходит из допустимого диапазона, то выполняется ребалансировка данного поддерева.</p>
34
<p>Ребалансировка деревьев осуществляется при помощи специальных механизмов -<strong>методов вращения</strong>. Вращения бывают двух видов: левое и правое.</p>
30
<p>Ребалансировка деревьев осуществляется при помощи специальных механизмов -<strong>методов вращения</strong>. Вращения бывают двух видов: левое и правое.</p>
35
<p>Вращение вправо выполняется за три шага:</p>
31
<p>Вращение вправо выполняется за три шага:</p>
36
<ol><li>Текущий корень поддерева (D) заменяется на левый дочерний узел (B)</li>
32
<ol><li>Текущий корень поддерева (D) заменяется на левый дочерний узел (B)</li>
37
<li>Предыдущий корень (D) становится правым дочерним узлом для (B)</li>
33
<li>Предыдущий корень (D) становится правым дочерним узлом для (B)</li>
38
<li>Предыдущее правое поддерево узла (B) становится левым поддеревом для (D)</li>
34
<li>Предыдущее правое поддерево узла (B) становится левым поддеревом для (D)</li>
39
</ol><p>Вращение влево выполняется аналогично:</p>
35
</ol><p>Вращение влево выполняется аналогично:</p>
40
<ol><li>Текущий корень поддерева (D) заменяется на правый дочерний узел (C)</li>
36
<ol><li>Текущий корень поддерева (D) заменяется на правый дочерний узел (C)</li>
41
<li>Предыдущий корень (D) становится левым дочерним узлом для (C)</li>
37
<li>Предыдущий корень (D) становится левым дочерним узлом для (C)</li>
42
<li>Предыдущее левое поддерево узла (C) становится правым поддеревом для (D)</li>
38
<li>Предыдущее левое поддерево узла (C) становится правым поддеревом для (D)</li>
43
</ol><p>В зависимости от того, куда добавили новую вершину, возможны различные комбинации выполнения вращений. Они помогут вернуть дерево в сбалансированное состояние.</p>
39
</ol><p>В зависимости от того, куда добавили новую вершину, возможны различные комбинации выполнения вращений. Они помогут вернуть дерево в сбалансированное состояние.</p>
44
<p>Всего выделяется четыре варианта развития событий:</p>
40
<p>Всего выделяется четыре варианта развития событий:</p>
45
<ul><li>Левое поддерево левой дочерней вершины</li>
41
<ul><li>Левое поддерево левой дочерней вершины</li>
46
<li>Левое поддерево правой дочерней вершины</li>
42
<li>Левое поддерево правой дочерней вершины</li>
47
<li>Правое поддерево левой дочерней вершины</li>
43
<li>Правое поддерево левой дочерней вершины</li>
48
<li>Правое поддерево правой дочерней вершины</li>
44
<li>Правое поддерево правой дочерней вершины</li>
49
</ul><p>Рассмотрим пример, который описывает первый случай - вставку в левое поддерево левой дочерней вершины. Изображенные треугольники представляют собой сбалансированные АВЛ-поддеревья. Они могут содержать большое количество вершин. У вершины В дерево не сбалансировано, поскольку поддерево А1 в вершине А на два уровня выше, чем поддерево В2:</p>
45
</ul><p>Рассмотрим пример, который описывает первый случай - вставку в левое поддерево левой дочерней вершины. Изображенные треугольники представляют собой сбалансированные АВЛ-поддеревья. Они могут содержать большое количество вершин. У вершины В дерево не сбалансировано, поскольку поддерево А1 в вершине А на два уровня выше, чем поддерево В2:</p>
50
<p>Чтобы сбалансировать дерево, необходимо совершить правое вращение - заменить вершину В вершиной А и сделать поддерево А2 левым поддеревом вершины В. После такого преобразования наше поддерево примет следующий вид:</p>
46
<p>Чтобы сбалансировать дерево, необходимо совершить правое вращение - заменить вершину В вершиной А и сделать поддерево А2 левым поддеревом вершины В. После такого преобразования наше поддерево примет следующий вид:</p>
51
<p>Четвертый сценарий будет выглядеть аналогично кроме замены способа вращения на левое.</p>
47
<p>Четвертый сценарий будет выглядеть аналогично кроме замены способа вращения на левое.</p>
52
<p>Для второго и третьего сценариев необходимо выполнить вращение дважды:</p>
48
<p>Для второго и третьего сценариев необходимо выполнить вращение дважды:</p>
53
<p>Удаление узлов также осуществляется при помощи механизмов вращения. При возврате во время рекурсивного спуска осуществляется вычисление balanceFactor. Если он отклоняется от допустимых значений, то выполняется ребалансировка аналогично добавлению узла.</p>
49
<p>Удаление узлов также осуществляется при помощи механизмов вращения. При возврате во время рекурсивного спуска осуществляется вычисление balanceFactor. Если он отклоняется от допустимых значений, то выполняется ребалансировка аналогично добавлению узла.</p>
54
<p>Другим видом автоматически балансирующихся деревьев являются красно-черные деревья, с которыми мы познакомимся дальше.</p>
50
<p>Другим видом автоматически балансирующихся деревьев являются красно-черные деревья, с которыми мы познакомимся дальше.</p>
55
<h3>Красно-черные деревья</h3>
51
<h3>Красно-черные деревья</h3>
56
<p><strong>Красно-черные деревья</strong>- одни из наиболее активно используемых на практике самобалансирующихся деревьев. Они так называются из-за наличия на узле дополнительного поля, в котором размещается цвет узла. В качестве стандартных цветов используют обычно красные и черные узлы, а сам цвет узла используется во время балансировки.</p>
52
<p><strong>Красно-черные деревья</strong>- одни из наиболее активно используемых на практике самобалансирующихся деревьев. Они так называются из-за наличия на узле дополнительного поля, в котором размещается цвет узла. В качестве стандартных цветов используют обычно красные и черные узлы, а сам цвет узла используется во время балансировки.</p>
57
<p>Так как красно-черные деревья самобалансирующиеся, то среднее и худшее время поиска тоже составляют O(logN). А операции вставки и удаления узла могут потребовать поворот поддерева.</p>
53
<p>Так как красно-черные деревья самобалансирующиеся, то среднее и худшее время поиска тоже составляют O(logN). А операции вставки и удаления узла могут потребовать поворот поддерева.</p>
58
<p>Для красно-черного дерева наш код узла примет следующий вид:</p>
54
<p>Для красно-черного дерева наш код узла примет следующий вид:</p>
59
-
<p><strong>Javascript</strong></p>
60
-
<p><strong>Java</strong></p>
61
-
<p><strong>Python</strong></p>
62
-
<p><strong>PHP</strong></p>
63
<p>В отличие от других видов деревьев в листовых узлах красно-черных деревьев не хранят полезную нагрузку. А цвет листовых узлов без данных всегда считается черным. Такая особенность позволяет считать ссылку на null валидным узлом. Эта особенность позволит сэкономить память. А само дерево принимает следующий вид:</p>
55
<p>В отличие от других видов деревьев в листовых узлах красно-черных деревьев не хранят полезную нагрузку. А цвет листовых узлов без данных всегда считается черным. Такая особенность позволяет считать ссылку на null валидным узлом. Эта особенность позволит сэкономить память. А само дерево принимает следующий вид:</p>
64
<p>Помимо особенностей работы с листовыми узлами к свойствам красно-черного так же относят:</p>
56
<p>Помимо особенностей работы с листовыми узлами к свойствам красно-черного так же относят:</p>
65
<ol><li>Корень красно-черного дерева черный</li>
57
<ol><li>Корень красно-черного дерева черный</li>
66
<li>Две красные вершины не могут идти подряд ни на одном пути. Оба потомка каждого красного узла - черные</li>
58
<li>Две красные вершины не могут идти подряд ни на одном пути. Оба потомка каждого красного узла - черные</li>
67
<li>Для каждой вершины, в каждом исходящем из нее пути, одинаковое число черных вершин</li>
59
<li>Для каждой вершины, в каждом исходящем из нее пути, одинаковое число черных вершин</li>
68
</ol><p>Иногда при работе с узлами красно-черного дерева используют<strong>черную высоту</strong>- количество черных вершин на исходящих из нее путях, не включая саму исходную вершину.</p>
60
</ol><p>Иногда при работе с узлами красно-черного дерева используют<strong>черную высоту</strong>- количество черных вершин на исходящих из нее путях, не включая саму исходную вершину.</p>
69
<p>Чтобы вставить узел, мы сначала ищем в дереве место, куда его следует добавить. Новый узел всегда добавляется как лист, поэтому оба его потомка являются пустыми узлами и предполагаются черными. После вставки красим узел в красный цвет. Далее смотрим на предка и проверяем, не нарушается ли свойства дерева, которые описали выше. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево.</p>
61
<p>Чтобы вставить узел, мы сначала ищем в дереве место, куда его следует добавить. Новый узел всегда добавляется как лист, поэтому оба его потомка являются пустыми узлами и предполагаются черными. После вставки красим узел в красный цвет. Далее смотрим на предка и проверяем, не нарушается ли свойства дерева, которые описали выше. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево.</p>
70
<p>Сбалансированность этих деревьев хуже, чем у АВЛ-деревьев. При этом затраты на поддержание состояния сбалансированности и потребление памяти меньше, а операцию поиска можно выполнять одновременно с выполнением перестроения дерева.</p>
62
<p>Сбалансированность этих деревьев хуже, чем у АВЛ-деревьев. При этом затраты на поддержание состояния сбалансированности и потребление памяти меньше, а операцию поиска можно выполнять одновременно с выполнением перестроения дерева.</p>
71
<p>Благодаря этим преимуществам сфера применения красно-черных деревьев существенно шире. Так, например, в стандартной библиотеке шаблонов языка C++ STL и TreeMap в Java применяются именно красно-черные деревья.</p>
63
<p>Благодаря этим преимуществам сфера применения красно-черных деревьев существенно шире. Так, например, в стандартной библиотеке шаблонов языка C++ STL и TreeMap в Java применяются именно красно-черные деревья.</p>
72
<h2>Выводы</h2>
64
<h2>Выводы</h2>
73
<p>Хранение данных в идеально сбалансированных деревьях позволяет достичь скорости поиска O(logN). Но чтобы поддерживать идеальную сбалансированность, требуются существенные ресурсные затраты на полное перестроение дерева при добавлении нового элемента.</p>
65
<p>Хранение данных в идеально сбалансированных деревьях позволяет достичь скорости поиска O(logN). Но чтобы поддерживать идеальную сбалансированность, требуются существенные ресурсные затраты на полное перестроение дерева при добавлении нового элемента.</p>
74
<p>Чтобы решить эту проблему, были придуманы новые виды деревьев: АВЛ-деревья и красно-черные деревья. Использование таких подходов поможет сохранить преимущества бинарных деревьев поиска и не тратить большое количество ресурсов. Так можно поддерживать идеальную согласованность.</p>
66
<p>Чтобы решить эту проблему, были придуманы новые виды деревьев: АВЛ-деревья и красно-черные деревья. Использование таких подходов поможет сохранить преимущества бинарных деревьев поиска и не тратить большое количество ресурсов. Так можно поддерживать идеальную согласованность.</p>