6. Бинарные Деревья, Часть 1

• Бинарные деревья - одна из самых мощных структур данных.  

• Они превосходят все предыдущие структуры данных по скорости операций.  

• Поддерживают два интерфейса: последовательности и наборы.  

• Массивы и связанные списки не подходят для вставки и удаления в середине.  

• Хэш-таблицы хороши для точного поиска, но не для поиска предыдущих и следующих элементов.  

• Отсортированные массивы не подходят для динамических операций.  

• Бинарные деревья позволяют динамически поддерживать порядок элементов.  

• Они обеспечивают быстрые операции, такие как поиск предыдущего ключа.  

• Сегодня мы рассмотрим высоту дерева, а в четверг - все операции.  

• Бинарное дерево состоит из узлов с элементами и указателями.  

• Узел имеет родительский указатель, левый и правый дочерние указатели.  

• Пример: узел A, B, C, D, E, F, где A - корневой узел.  

• Указатели в бинарном дереве двунаправленные.  

• Родительский указатель всегда является обратной операцией для указателей "влево" и "вправо".  

• Бинарное дерево напоминает связанный список, но с логарифмической структурой.  

• Поддерево - часть дерева с корнем в определенном узле.  

• Глубина узла - количество ребер до корня.  

• Высота узла - количество ребер на самом длинном нисходящем пути от листа до узла.  

• Высота дерева измеряется вверх, а глубина вниз.  

• Высота корня дерева обозначается как h.  

• Цель - манипулировать деревом так, чтобы время выполнения операций было порядка h, а не log n.  

• Плохие деревья имеют большую высоту, например, елка.  

• Высота узла с равна нулю, так как это длина самого длинного пути до листа.  

• Высота дерева равна его максимальной глубине.  

• В деревьях существует естественный порядок обхода.  

• Пример порядка обхода: f, d, b, e, a, c.  

• Порядок обхода определяется рекурсивно: узлы в левом поддереве идут раньше, в правом - позже.  

• Алгоритм обхода по порядку: итерация по левому поддереву, затем по правому, и вывод самого узла.  

• Этот алгоритм позволяет последовательно выводить все узлы в поддереве.  

• Порядок обхода используется для представления последовательностей и наборов.  

• Для последовательностей порядок обхода соответствует порядку следования элементов.  

• Для наборов порядок обхода представляет отсортированный порядок ключей.  

• Операция "поддерево 1-й" определяет узел, занимающий 1-е место в порядке обхода поддерева.  

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

• Операция ищет самый левый лист в поддереве.  

• Операция "преемник" определяет узел, следующий за текущим в порядке обхода дерева.  

• Преемник может быть правильным дочерним элементом или родителем, если правильного дочернего элемента нет.  

• Если узел является левым дочерним элементом, его преемник - это родитель.  

• Преемник узла e не может быть b, так как все элементы в поддереве b появляются раньше или равны e.  

• Преемником e является a, так как поддерево b было левым дочерним элементом a.  

• Общая стратегия: идти вверх по дереву до левого обходного пути.  

• Узел равен родительскому узлу до тех пор, пока не поднимется по левой ветке.  

• После обхода родительский узел будет искомым.  

• Начинаем с узла, родительский узел которого справа.  

• Преемник перемещается влево, все узлы в правом поддереве появляются позже.  

• Если у узла нет правого поддерева, то это его преемник.  

• Порядок обхода не вычисляется явно, а поддерживается в голове.  

• Это позволяет манипулировать порядком и выполнять итерации.  

• Операции выполняются в порядке h, где h - высота дерева.  

• Вставка и удаление в середине поддерева.  

• Вставка нового узла после существующего узла.  

• Удаление узла, если он является листом, просто стирается.  

• Удаление корня дерева сложнее, так как нужно поддерживать связь с деревом.  

• Используется функция "преемник-предшественник" для поддержания структуры дерева.  

• Определение предшественника узла "а" - это "е".  

• Перемещение "а" вниз по дереву и замена его на "е".  

• Повторное обращение к предшественнику "а" - это "g".  

• Замена "а" на "g" и удаление "а" как листа.  

• Иногда нужно использовать предшественников, иногда преемников.  

• Если узел конечный, просто отделите его от родительского узла.  

• Если узел не является листом, есть левый или правый дочерний элемент.  

• Если есть левый дочерний элемент, предшественник узла находится ниже в дереве.  

• Перемещение содержимого узла с элементом предшественника.  

• Рекурсивное удаление предшественника.  

• Если есть правый дочерний элемент, но нет левого, меняем местами элемент с преемником.  

• Рекурсивно удаляем преемника.  

• Общее время выполнения операции пропорционально высоте дерева.  

• Изменение идентификаторов узлов при перемещении элементов.  

• Порядок обхода дерева сохраняется.  

• Пример удаления узлов "f" и "a".  

• Для последовательности делаем порядок обхода равным порядку последовательности.  

• Для сортировки элементов набора по ключам делаем порядок обхода по возрастанию ключа.  

• Пример поиска ключа в дереве с использованием бинарного поиска.  

• Ключи в левом поддереве меньше корня, корень меньше ключей в правом поддереве.  

• Пример поиска ключа 13 в дереве.  

• Поиск предыдущего и следующего элементов в дереве.