Введение в самобалансирующиеся двоичные деревья поиска
Структуры данных - это специализированные средства организации и хранения данных на компьютерах таким образом, чтобы мы могли более эффективно выполнять операции с сохраненными данными. Из множества имеющихся структур данных двоичные деревья поиска играют важную роль, когда дело доходит до эффективных операций. Поскольку я получил большой интерес и добрые ответы на свою предыдущую статью 8 общих структур данных, которые должен знать каждый программист, в этой статье я кратко расскажу о самобалансирующихся двоичных деревьях поиска (BST).
Что такое деревья двоичного поиска?
Если вы читали мою предыдущую статью о структурах данных, вы знаете, что двоичное дерево поиска (BST) - это двоичное дерево, в котором данные организованы в иерархическую структуру.
Бинарное дерево поиска обладает уникальным свойством, известным как свойство двоичного дерева поиска.
Пусть x будет узлом в двоичном дереве поиска.
- Если y является узлом в левом поддереве x, тогда y.key ≤ x.key
- Если y является узлом в правом поддереве x, тогда y.key ≥ x.key
Что такое самобалансирующиеся двоичные деревья поиска?
Самобалансирующееся двоичное дерево поиска (BST) - это двоичное дерево поиска, которое автоматически пытается поддерживать минимальную высоту в любое время (даже после выполнения таких операций, как вставка или удаление).
Если вы ознакомились с Шпаргалкой по сложности алгоритма Big-O, то увидите, что средняя временная сложность операций BST составляет Θ (h), где h - высота дерева. Следовательно, когда речь идет о выполнении большого количества операций, лучше иметь как можно меньшую высоту. Следовательно, были введены самобалансирующиеся BST, которые автоматически поддерживают минимальную высоту. Однако вы можете подумать, что необходимость самобалансировки каждый раз при выполнении операции неэффективна, но это компенсируется обеспечением большого количества быстрых операций, которые будут выполняться позже на BST.
Бинарное дерево с высотой h может иметь не более 2⁰+2¹+···+2ʰ = 2⁽ʰ⁺¹⁾−1 узлов.
n ≤ 2⁽ʰ⁺¹⁾ − 1
h ≥ log₂ (n + 1) - 1⌉ ≥ log₂ (n) ⌋
Следовательно, для самобалансирующихся BST минимальная высота всегда должна быть log ₂ (n) с округлением в меньшую сторону. Более того, двоичное дерево называется сбалансированным, если высота левого и правого потомков каждого узла отличается на -1, 0 или +1. Это значение известно как коэффициент баланса.
Коэффициент баланса = высота левого поддерева - высота правого поддерева
Как балансируются самобалансирующиеся деревья двоичного поиска?
Когда дело доходит до самобалансировки, BST выполняют вращения после выполнения операций вставки и удаления. Ниже приведены два типа операций поворота, которые могут быть выполнены для балансировки BST без нарушения свойства двоичного дерева поиска.
1. Левое вращение
Когда мы оставили поворот вокруг узла x, узел y становится новым корнем поддерева. Узел x становится левым потомком узла y, а поддерево b становится правым потомком узла x.
2. Правое вращение
Когда мы поворачиваем вправо вокруг узла y, узел x становится новым корнем поддерева. Узел y становится правым потомком узла x, а поддерево b становится левым потомком узла y.
Обратите внимание, что после того, как вы выполнили ротации, обход узлов по порядку как в предыдущем, так и в последнем деревьях будет одинаковым, и свойство binary-search-tree сохраняется.
Типы самобалансирующихся двоичных деревьев поиска
Ниже приведены несколько типов самобалансирующихся BST.
- Деревья АВЛ
- Красно-черные деревья
- Раскидистые деревья
- Treaps
Применение самобалансирующихся двоичных деревьев поиска
Самобалансирующиеся BST используются для создания и поддержки упорядоченных списков, таких как очереди приоритетов. Они также используются для ассоциативных массивов, где пары ключ-значение вставляются в соответствии с порядком, основанным только на ключе.
Многие алгоритмы вычислительной геометрии используют самобалансирующиеся BST для эффективного решения таких проблем, как пересечение отрезков прямой. Более того, самобалансирующиеся BST могут быть расширены для выполнения новых операций, которые можно использовать для оптимизации запросов к базе данных или других алгоритмов обработки списков.
Деревья AVL как пример самобалансирующихся BST
Деревья Адельсона-Вельского и Ландиса (AVL) - это сбалансированные бинарные деревья. Все узлы в дереве AVL хранят свой собственный коэффициент баланса.
В дереве AVL коэффициент баланса каждого узла равен -1, 0 или +1.
Другими словами, разница между высотой левого поддерева и высотой правого поддерева не может быть больше 1 для всех узлов в дереве AVL.
Пример дерева AVL
На рисунке 4 значения красного цвета над узлами являются соответствующими коэффициентами баланса. Вы можете видеть, что условие коэффициента сбалансированности выполняется во всех узлах дерева AVL, показанного на рисунке 4.
Повороты в деревьях AVL
После выполнения вставок или удалений в дереве AVL мы должны проверить, удовлетворяется ли условие коэффициента баланса всеми узлами. Если дерево не сбалансировано, мы должны сделать повороты, чтобы сделать его сбалансированным.
Вращения, выполняемые на деревьях AVL, могут быть четырех основных типов, которые сгруппированы по двум категориям. Они есть,
- Одиночное вращение - вращение влево (LL) и вращение вправо (RR)
- Двойное вращение - Вращение влево-вправо (LR) и Вращение вправо-влево (RL)
Приведенные ниже диаграммы поясняют каждый тип вращения.
1. Одиночное вращение влево (вращение LL)
В этом типе вращения мы перемещаем все узлы влево на одну позицию.
2. Одиночное правое вращение (правое вращение)
В этом типе вращения мы перемещаем все узлы вправо на одну позицию.
3. Вращение влево-вправо (Вращение LR)
Как следует из названия, этот тип вращения состоит из левого и правого вращения.
4. Вращение вправо-влево (Вращение RL)
Этот тип вращения состоит из правого вращения, за которым следует левое вращение.
Вставка элемента в дерево AVL
Рассмотрим дерево AVL, показанное на рисунке 4. Мы хотим добавить новый узел 105 к этому дереву. На рисунке 9 показаны шаги, выполняемые для вставки нового узла и повторной балансировки дерева.
После добавления узла 105 в дереве будет всего 12 узлов. Если мы посчитаем возможную высоту для уравновешенного дерева,
h ≥ log₂ (n + 1) - 1⌉
h ≥ log₂ (12 + 1) - 1⌉
h ≥ log₂ (12) ⌋ = ⌊3.58496250072⌋ = 3
Однако высота результирующего дерева после вставки равна 4. Более того, коэффициент балансировки узла 102 равен -2. Из этих фактов видно, что результирующее дерево после вставки не сбалансировано. Следовательно, мы должны сбалансировать это вращением. Вы можете видеть, что поддерево, основанное на узле 102, должно быть повернуто, и следует использовать поворот RL. После выполнения этого поворота мы получаем сбалансированное дерево высотой 3.
Последние мысли
Я надеюсь, что вы нашли эту статью полезной как простое введение в самобалансирующиеся деревья двоичного поиска, где мы обсуждали деревья AVL в качестве примера. Я хотел бы услышать твои мысли. 😇
Большое спасибо за чтение. 😊 Следите за новостями в следующих статьях, в которых я расскажу больше о самобалансирующихся BST.
Ваше здоровье! 😃
использованная литература
[1] CS241 - Лекция: самобалансирующееся двоичное дерево поиска
[2] Самобалансирующееся двоичное дерево поиска - Википедия
[3] Учебники по структурам данных - AVL Tree | Примеры | Фактор баланса
