Деревья (часть 2)
Бинарные деревья поиска подвергаются изменениям при операциях вставки и удаления. Чтобы сохранить свойства бинарных деревьев, структура данных должна быть адаптирована так, чтобы отражать эти изменения. Вставка нового элемента в бинарное дерево поиска относительно проста, в то время как удаление представляет собой более сложную задачу.
void tree_Insert(TreeNode*& root, TreeNode* z) {
Этот код представляет собой реализацию бинарного дерева поиска. Давайте разберемся, что он делает:
- TreeNode - это структура, представляющая узел в бинарном дереве.
- key (ключ) - значение, которое определяет порядок узлов в дереве.
- Указатели на левого и правого потомков (left и right).
- Указатель на родителя (parent).
- Эта функция вставляет новый узел z в бинарное дерево поиска, представленное корнем root.
- Инициализируем указатели y и x.
- Пока x не равен nullptr, продолжаем следующее:
- y присваивается текущее значение x.
- Если z->key меньше x->key, переходим к левому потомку (x = x->left), иначе к правому (x = x->right).
- Устанавливаем родителя узла z в y.
- Если y равен nullptr, то root устанавливается в z.
- Иначе, если z->key меньше y->key, устанавливаем z как левого потомка y, иначе как правого.
Этот код позволяет добавлять новые узлы в бинарное дерево поиска в соответствии с их ключами. Если ключ z меньше ключа текущего узла, он добавляется в левую ветвь, иначе - в правую. Таким образом, дерево остается отсортированным по значениям ключей.
TreeNode* parent; // Добавляем указатель на родителя
TreeNode(int k) : key(k), left(nullptr), right(nullptr), parent(nullptr) {}
TreeNode* tree_Successor(TreeNode* node) {
TreeNode* root = nullptr; // Глобальная переменная для корня
TreeNode* tree_Delete(TreeNode* T, TreeNode* z) {
else if (y == y->parent->left)
return root; // Возвращаем корень дерева
- `struct TreeNode` описывает узел в бинарном дереве поиска.
- Узел содержит ключ `key`, указатели на левого (`left`) и правого (`right`) потомков, а также указатель на родителя (`parent`).
- Конструктор `TreeNode(int k)` устанавливает ключ равным `k` и инициализирует указатели на потомков и родителя.
- `tree_Successor` находит следующий узел (инордер преемник) относительно узла `node` в бинарном дереве поиска.
- Если у узла `node` есть правый потомок, то следующий узел - самый левый потомок правого поддерева.
- Функция возвращает найденный следующий узел.
1. Проверка наличия левого и правого потомка у узла `z` - если одного из них нет, то корень устанавливается равным `z`.
2. В противном случае, для узла `z` находится его преемник, который становится новым корнем.
3. Определяется узел `y` для удаления (либо сам узел `z`, либо его преемник).
4. Находится потомок `x` узла `y` для перенастройки связей в дереве.
5. Устанавливаются новые родительские связи для потомков `x`.
6. Коррекция связей в дереве из-за удаления узла `y` и переопределение указателей.
7. Если `y` не равен `z`, то ключ из `y` копируется в `z` для сохранения порядка.
8. Удаляется узел `y` из дерева.
9. Возвращается корень дерева после удаления.
- Функция `tree_Delete` основана на принципах бинарного дерева поиска и служит для удаления узла `z`.
- В случае отсутствия одного из потомков узел удаляется непосредственно.
- При наличии обоих потомков для узла `z` находится преемник `y`, который заменяет `z` и удаляется.
- При удалении узла, связи в дереве корректно перестраиваются с учетом порядка ключей.
- Вставка нового узла в бинарное дерево поиска (функция tree_Insert) имеет временную сложность O(h), где h - высота дерева.
- Удаление узла (функция tree_Delete) также имеет временную сложность O(h), где h - высота дерева.
- В сбалансированных деревьях (например, AVL-деревья или красно-черные деревья), высота ограничена и равна O(log n), где n - количество узлов в дереве. В таких деревьях операции вставки и удаления выполняются за O(log n) времени.
- Однако в худшем случае (несбалансированное дерево) высота может быть равна n, и операции вставки и удаления будут выполняться за O(n) времени.
Сбалансированные деревья это специальный тип данных, который обеспечивает эффективный доступ, вставку и удаление элементов. Они характеризуются тем, что глубина поддеревьев отличается не более чем на 1. Это означает, что при правильной реализации высота дерева будет близка к оптимальной и операции над ним имеют логарифмическую сложность.
Один из самых известных сбалансированных деревьев - АВЛ-дерево. В АВЛ-дереве для каждого узла сбалансированность означает, что разница высот левого и правого поддеревьев (баланс-фактор) ограничена значениями -1, 0 или 1. Если это условие нарушается, происходит перебалансировка путем одной или нескольких операций поворота.
Пример сбалансированного дерева - АВЛ-дерево:
1. Пусть есть следующие значения для вставки: 10, 5, 15, 7, 2.
2. Начинаем с вставки узла с ключом 10 - это станет корневым узлом.
3. Вставляем узел с ключом 5 - он станет левым потомком узла 10.
4. Вставляем узел с ключом 15 - он станет правым потомком узла 10.
5. Вставляем узел с ключом 7 - это вызовет несбалансированность, произойдет балансировка.
6. Вставляем узел с ключом 2 - дерево останется сбалансированным.
Результирующее сбалансированное АВЛ-дерево:
Это пример сбалансированного дерева, где каждый узел обладает свойством баланса, что гарантирует хорошую производительность при операциях над данными структурами.
При использовании стандартного алгоритма вставки элементов в бинарное дерево существует риск построения вырожденного дерева, особенно при случайных входных данных. Чтобы избежать этого риска и поддерживать дерево в оптимальном состоянии, необходимо разработать алгоритм поддерживающий сбалансированность структуры. В данном контексте оптимальность означает сбалансированность дерева.
Идеально сбалансированным называется дерево, в котором для каждой вершины выполняется следующее требование:
- Количество вершин в левом и правом поддеревьях отличается на единицу.
Такой подход к управлению структурой дерева поддерживает баланс и обеспечивает эффективные операции вставки, удаления и поиска. Концепция идеально сбалансированных деревьев играет важную роль в обеспечении оптимальной производительности и снижении риска построения вырожденной структуры дерева.