Сбалансированные деревья

Сбалансированные деревья

В предыдущих статьях были рассмотрены два подхода и алгоритмы для поиска по деревьям: поиск в ширину и поиск в глубину. Здесь далее текст пойдёт о сбалансированных деревьях.

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

Балансировка

Помните бинарный поиск? С его помощью можно найти информацию намного быстрее, чем простым поиском — со сложностью O(log n) вместо O(n). Но, есть одна проблема: вставка. Конечно, поиск занимает время O(log n), но массив должен быть отсортирован. Если требуется вставить новое число в отсортированный массив, это займёт время O(n). Проблема здесь в том, чтобы найти место для нового значения. Придётся передвинуть несколько элементов, чтобы освободить для него место. Вот если бы вставку можно было выполнить как в связанном списке, где достаточно поменять пару указателей... Но минус связанного списка в том, что поиск выполняется за линейное время O(n). Как взять и использовать только лучшие стороны обоих решений из массивов и связанных списков?

Скорость вставки в деревьях

Нам понадобится структура данных объединяющая идеи вставки и поиска. Эта структура называется сбалансированное бинарное дерево поиска (BST). BST это разновидность бинарного дерева. Рассмотрим пример:

Как и в бинарном дереве, каждый узел имеет до двух дочерних узлов: левый и правый. Но у этого дерева есть одно свойство, относящее его к BST: значение левого дочернего узла всегда меньше, чем значение узла, а значение правого дочернего узла всегда больше. Таким образом, для корневого узла 10 левый дочерний узел имеет меньшее значение 4, а правый дочерний узел — большее значение 15. К тому же, все числа в поддереве левого дочернего узла меньше самого узла! Это особое свойство означает, что поиск будет выполняться очень быстро.

Давайте посмотрим на алгоритм, содержится ли число 6 в этом дереве? Начнём с корневого узла. Число 6 меньше 10, поэтому проверяем левое поддерево. Помните: все узлы с меньшими значениями находятся в левом поддереве, а все узлы с большими значениями — в правом. Следовательно, мы сразу понимаем, что проверять узлы справа не нужно, потому что 6 там не будет. Опускаясь по левому поддереву от 10, переходим к узлу 4. Число 6 больше 4, поэтому далее идём направо. И вот мы нашли число 6. Теперь поищем другое число — 8. Поиск происходит аналогично по такому же пути.

Собственно, все рассуждения о деревьях обусловлены одной необходимостью: знать, работают ли они быстрее массивов и связанных списков. Рассмотрим производительность деревьев, но для этого необходимо учитывать их высоту. Короткие деревья работают быстрее. В лучшем случае высота дерева равна 2. Это означает, что к любому узлу можно перейти от корневого узла максимум за 2 шага. Высота дерева для худшего случая с теми же данными будет равна 6. Это означает, что к любому узлу можно перейти от корневого узла максимум за 6 шагов. Помните игру с отгадыванием чисел? Чтобы угадать число из набора 100 чисел, бинарный поиск потребует максимум 7 попыток, а простому может потребоваться все 100 попыток. Нечто похожее происходит и с деревьями.

Дерево для худшего случая содержит больше уровней и у него хуже с производительностью. В нём все узлы выстроены в одну линию. Дерево имеет высоту O(n), так что поиск будет выполняться за время O(n). Представить можно так: дерево напоминает связанный список, так как один узел содержит ссылку на другой. Поиск по связанному списку выполняется за время O(n).

Дерево для худшего случая имеет высоту O(log n), а поиск по нему занимает время O(log n).

Таким образом, ситуация очень похожа на сравнение бинарного поиска с простым линейным поиском! Если высота дерева всегда будет обеспечиваться как log n, то поиск будет выполнятся за время O(log n). Но как добиться, чтобы высота составляла O(log n)? Кратчайшее время для BST может составлять O(log n). Чтобы этого добиться, нужно сбалансировать дерево. Рассмотрим сбалансированное дерево BST.

АВЛ-деревья

АВЛ-деревья (АВЛ аббревиатура образована от фамилий ученых придумавших эту структуру данных: Адельсон, Вельский, Ландис) составляют разновидность "самобалансируемых" BST. Это означает, что АВЛ-деревья сохраняют высоту O(log n). Каждый раз, когда дерево "разбалансируется", то есть его высота становится отличной от O(log n), оно корректирует себя. АВЛ-дерево обеспечивает нужную высоту O(log n) за счёт самобалансировки и поворотов.

Повороты АВЛ-дерева

Повороты — популярный метод балансировки деревьев. Представьте, что имеется дерево с тремя узлами. Любой из них может быть корневым. В результате поворота набор узлов смещается, образуя новую конфигурацию. Начнем с двух узлов, рассмотрим поворот:

Высоты дочерних узлов неодинаковы: разность между ними не превышает 1. Однако разность в 1 уровень приемлема для АВЛ-деревьев. Теперь добавим ещё один узел.

Дерево "разбалансировалось". Нужно его повернуть.

Выполнили поворот влево, теперь дерево снова сбалансировано. Добавим ещё один узел.

И ещё один.

Снова выполним поворот.

После поворота АВЛ-деревья перебалансируются. Заметим, что в последнем повороте вместо узла 15 поворачивался узел 30. Разберёмся далее почему так.

Как АВЛ-дерево узнает, что требуется поворот?

Чтобы дерево знало, когда требуется самобалансировка, оно должно хранить дополнительную информацию. В каждом узле хранится один или два вида информации: значение высоты или значение, которое иногда называют коэффициентом балансировки. Этот коэффициент должен быть равен -1, 0 или 1.

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

Коэффициент балансировки сообщает, какой дочерний узел выше и насколько. По коэффициенту балансировки дерево может определить, когда следует проводить перебалансировку. Значение 0 означает, что дерево сбалансировано. Со значениями -1 или 1 все нормально, потому что, АВЛ-деревья не обязаны быть идеально сбалансированы: разность 1 допустима. Но если коэффициент балансировки падает ниже -1 или поднимается выше 1, дерево нуждается в перебалансировке. Ниже пример двух таких деревьев:

В каждом узле должна храниться либо высота, либо коэффициент балансировки. Можно хранить и то и другое. Если известны высоты каждого поддерева, то легко вычисляется коэффициент балансировки. Рассмотрим пример:

Для начала запишем высоту и коэффициент балансировки для каждого узла. На этой схеме В – высота, а К – коэффициент балансировки. Храним в данном примере два значения, но достаточно в реализации хранить только одно. У всех корневых узлов коэффициент балансировки равен 0: у них нет дочерних узлов, поэтому и поддерживать баланс не нужно. Добавим в дерево новый узел:

После того как узел был добавлен, необходимо задать для него высоту и коэффициент балансировки. Затем следует подняться вверх по дереву, обновляя высоты и коэффициенты балансировки для всех его предков. После вставки нового элемента в дерево — обновляются все коэффициенты балансировки для предков вставленного узла. АВЛ-дерево проверяет коэффициент балансировки, чтобы после выполнять перебалансировку. В данном примере выше присутствует коэффициент балансировки -2, это означает что узел в дереве нужно повернуть! Повернём узел 10:

Теперь дерево сбалансировано. Если продолжить движение вверх по дереву то также ничего балансировать уже будет не нужно. Двигаться от "перебалансированного" узла вверх по дереву необязательно, потому что АВЛ-деревья требуют не более одной "перебалансировки".

Итак, АВЛ-деревья хороши, если требуется сбалансированное дерево BST. АВЛ-деревья обеспечивают производительность поиска O(log n). А что со вставкой? Вставка сводится к поиску места для вставки узла и добавления указателя, как в связанном списке. Например, если необходимо вставить элемент в сбалансированное АВЛ-дерево, то необходимо сначала определить, где добавить указатель. И таким образом, вставка тоже выполняется за время O(log n).

Получается что структура данных АВЛ-дерево или сбалансированное дерево BST обеспечивает и быструю вставку и быстрый поиск! Общая информация по трём структурам данных в таблице ниже:

Косые деревья

Косые деревья или Splay-деревья представляют другой подход к сбалансированным деревьям BST. Их самое лучшее свойство в том, что если был произведён недавно поиск какого-то элемента, то следующий поиск будет быстрее. Это свойство интуитивно рассматривается положительно. Представьте, что необходимо реализовать работу с программой, которая получает почтовый индекс и находит по нему город. И также представьте, что необходимо многократно каждый раз получать и проводить поиск одного и того же почтового индекса. Почему бы не запомнить прошлый результат поиска? Косые деревья позволяют это сделать. Когда происходит поиск в косом дереве, он становится после нахождения новым корневым узлом. Так при повторном поиске этот же узел будет найден сразу же! В общем случае узлы, которые недавно искали, группируются ближе к корню и находятся быстрее. С другой стороны, дерево заведомо не будет сбалансировано, а значит, некоторые операции поиска будут занимать время, большее чем O(log n), и даже достигать линейного времени! Кроме того, может потребоваться повернуть узел до корневой позиции, если он ещё некорневой,а это тоже потребует времени. Но в целом рассматривая реализацию конкретной задачи, нас должно устраивать, что дерево не будет сбалансировано постоянно. Главное, что при проведении n операций поиска общее время O(n log n) гарантированно — т.е. O(log n) на один поиск. Таким образом, хотя один поиск может занять время, превышающее O(log n), в среднем все операции поиска сходятся ко времени O(log n), а цель как раз и есть ускорение поиска.

B-деревья

B-деревья представляют собой обобщённую форму бинарных деревьев. Они часто используются для построения баз данных. Ниже представлен пример B-дерева:

Выглядит интересно, правда? Можно заметить, что некоторые узлы имеют более двух дочерних узлов. В отличие от других деревьев поиска (например, двоичного дерева, АВЛ‑дерева), где каждый узел хранит один ключ и максимум двух потомков, в B‑дереве:

• узел может содержать несколько ключей;
• узел может иметь более двух потомков.

B-дерево — это обобщенная форма бинарного дерева поиска.

Какие преимущества есть у B-деревьев?

Для B-деревьев существует оптимизация, интересная тем, что применяется на физическом уровне. При поиске по дереву получение данных требует перемещения механических компонентов оборудования (например, считывающей головки HDD диска). Время получения данных называется временем поиска. Оно может быть важным фактором, определяющим, насколько быстро или медленно работает алгоритм.

Ситуация можно сравнить с посещением магазина. Вы можете покупать продукты по одному. Представьте, что вы решаете купить яблоки. Вернувшись из магазина, вы понимаете, что было бы неплохо купить ещё и апельсины, и возвращаетесь в магазин. По возвращении вы видите, что у вас закончился шоколад, и снова поход в магазин... Это крайне неэффективно! Намного лучше зайти в магазин и купить за раз все необходимые товары, находясь в нём. Время похода в магазин и возвращения из него представляет собой время поиска.

Фундаментальная концепция B-деревьев заключается в том, что после выполнения поиска можно прочитать дополнительные данные в память. Это как сходить в магазин и купить сразу всё необходимое чтобы не ходить в него снова.

В B-деревьях используются большие узлы; каждый узел может иметь больше ключей и дочерних узлов, чем бинарное дерево. Таким образом, чтение каждого узла займёт больше времени. С другой стороны, поиск при больших данных ускоряется, потому что за один раз читается больший объём данных. Именно это обстоятельство обеспечивает высокую скорость работы с B-деревом.

Структура B-деревьев популярна в реализациях баз данных. И это не удивительно, ведь в базах данных много времени занимает чтение с дисков. Как происходит обход B-дерева? Начинается всё с нижнего крайнего левого или правого узла. А дальше змейкой обход остальных узлов.

Обратите внимание на свойство как у BST деревьев. Для каждого ключа значения ключей в левом поддереве меньше, а значения ключей в правом поддереве — больше него. Например, для ключа 6 левое поддерево состоит из ключей 4 и 5, а правое поддерево из ключей 7 и 8. Также количество дочерних узлов на 1 больше количества ключей. Таким образом, корневой узел имеет один ключ и два дочерних узла. Каждый из дочерних узлов имеет два ключа и три дочерних узла.

На этом можно завершить изучение деревьев. Вам вряд ли придётся реализовывать их самостоятельно, но важно знать, что деревья — это разновидность графов и они обладают отличной производительностью.

В следующей статье можно узнать о популярном алгоритме на взвешенных графах: Алгоритм Дейкстры.