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

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

• Они превосходят все ранее изученные структуры данных по эффективности.  

• В этой лекции будут рассмотрены операции вставки и удаления элементов в середине списка.  

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

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

• Словари Python хорошо справляются с поиском ключей, но не с предыдущими и следующими элементами.  

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

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

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

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

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

• Родительский узел не имеет родителя, а корневой узел - это узел без родителя.  

• Инвариант бинарного дерева: переход к левому указателю узла и затем к его родительскому узлу должен привести к тому же узлу.  

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

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

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

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

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

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

• Высота дерева - это максимальная глубина узла в поддереве.  

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

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

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

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

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

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

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

• Представление отсортированного порядка ключей по возрастанию.  

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

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

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

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

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

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

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

• Преемник e находится в левом поддереве a.  

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

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

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

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

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

• В худшем случае время операций будет порядка высоты дерева.  

• Вставка и удаление в середине поддерева требуют манипуляций с деревом.  

• Пример: вставка g перед e.  

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

• Вставка нового узла g перед e.  

• Новый узел помещается в левое поддерево, если нет подходящего дочернего элемента.  

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

• Удаление узла f1st.  

• Удаление листа просто стирает указатель.  

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

• Определение "преемника" и "предшественника" для узла "а".  

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

• Замена "а" на "е" для перемещения "а" вниз по дереву.  

• Замена "а" на "g" для сохранения порядка обхода.  

• Узел "а" становится листом и может быть удален.  

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

• Отделение конечного узла от родительского узла.  

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

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

• Замена содержимого узла с содержимым преемника и рекурсивное удаление.  

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

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

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

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

• Сортировка элементов набора по ключам.  

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

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

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

• Сравнение ключа с корневым узлом и рекурсивный поиск в левом или правом поддереве.  

• Поиск предыдущего и следующего узлов при падении с дерева.  

• Возможность найти либо предыдущий, либо следующий узел.