13. Красно чёрное дерево
Красно-чёрное дерево (англ. red-black tree, RB tree) — один из видов самобалансирующихся двоичных деревьев поиска. Название происходит от стандартной раскраски узлов в красный и чёрный цвета. Свойства: Узел может быть либо красным, либо чёрным и имеет двух потомков. Корень — как правило чёрный. Все листья, не содержащие данных, — чёрные. Оба потомка каждого красного узла — чёрные. Любой простой путь от узла-предка до листового узла-потомка содержит одинаковое число чёрных узлов. Принцип организации Сбалансированность достигается за счёт введения дополнительного атрибута узла — «цвета». В каждом узле помимо элемента хранится 1 бит информации о том, красный ли узел или чёрный. Количество чёрных узлов на ветви от корня до листа называется чёрной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви. Операции Красно-чёрное дерево поддерживает основные операции дерева поиска: добавление, удаление и поиск узла. Вставка нового элемента требует присваивания ему красного цвета, а при необходимости новые вершины перекрашиваются в необходимый цвет. Удаление элемента происходит с последующим перекрашиванием узлов и выполнением поворотов, что позволяет восстановить структуру дерева. Поиск выполняется по тому же алгоритму, что и в бинарном дереве поиска: выполняется обход дерева, и каждая вершина сравнивается с ключевым элементом, подлежащим поиску. Если поиск найден, возвращается результат успешного поиска, в противном случае — результат безуспешного поиска. Алгоритмы После вставки или удаления требуется операция перекраски, которая требует смен цветов и не более чем трёх поворотов дерева (для вставки — не более двух). Каждая операция балансировки занимает константное время, поскольку состоит из перезаписи ссылок у дочерних и родительских элементов, а также информации об их цвете. Теорема Асимптотическая сложность операций над красно-чёрным деревом — O(log n), где n — количество узлов в дереве. Это следует из свойств дерева: для их выполнения нужно дойти до нужного узла, на каждом шаге отмечая одно из поддеревьев
Красно-чёрное дерево (англ. red-black tree, RB tree) — один из видов самобалансирующихся двоичных деревьев поиска. Название происходит от стандартной раскраски узлов в красный и чёрный цвета. Свойства: Узел может быть либо красным, либо чёрным и имеет двух потомков. Корень — как правило чёрный. Все листья, не содержащие данных, — чёрные. Оба потомка каждого красного узла — чёрные. Любой простой путь от узла-предка до листового узла-потомка содержит одинаковое число чёрных узлов. Принцип организации Сбалансированность достигается за счёт введения дополнительного атрибута узла — «цвета». В каждом узле помимо элемента хранится 1 бит информации о том, красный ли узел или чёрный. Количество чёрных узлов на ветви от корня до листа называется чёрной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви. Операции Красно-чёрное дерево поддерживает основные операции дерева поиска: добавление, удаление и поиск узла. Вставка нового элемента требует присваивания ему красного цвета, а при необходимости новые вершины перекрашиваются в необходимый цвет. Удаление элемента происходит с последующим перекрашиванием узлов и выполнением поворотов, что позволяет восстановить структуру дерева. Поиск выполняется по тому же алгоритму, что и в бинарном дереве поиска: выполняется обход дерева, и каждая вершина сравнивается с ключевым элементом, подлежащим поиску. Если поиск найден, возвращается результат успешного поиска, в противном случае — результат безуспешного поиска. Алгоритмы После вставки или удаления требуется операция перекраски, которая требует смен цветов и не более чем трёх поворотов дерева (для вставки — не более двух). Каждая операция балансировки занимает константное время, поскольку состоит из перезаписи ссылок у дочерних и родительских элементов, а также информации об их цвете. Теорема Асимптотическая сложность операций над красно-чёрным деревом — O(log n), где n — количество узлов в дереве. Это следует из свойств дерева: для их выполнения нужно дойти до нужного узла, на каждом шаге отмечая одно из поддеревьев