Введение

Алгоритмы на основе деревьев широко используются в области больших данных. Преимуществом таких алгоритмов в основном является их эффективная временная сложность O(log(n)). Одним из наиболее репрезентативных древовидных алгоритмов является бинарное дерево поиска (BST). Однако основным недостатком этого алгоритма является отсутствие самобалансировки и, следовательно, сходство с несбалансированным или перекошенным деревом. Из-за этой проблемы на сцене появились деревья Red Black и AVL. Эти два алгоритма преодолели основной недостаток BST и получили возможность балансировать себя. Этот пост предназначен для ознакомления с основной структурой и функциональностью этих алгоритмов.

1. Дерево РБ

Красно-черное дерево — это бинарное дерево поиска, в котором каждый узел окрашен либо в красный, либо в черный цвет. Это тип самобалансирующегося бинарного дерева поиска. В наихудшем сценарии красно-черные деревья могут иметь временную сложность O(logN) для всех основных операций, таких как извлечение, вставка и удаление, тогда как бинарные деревья поиска имеют O(N). Красно-черные деревья обладают невероятным свойством сохранять временную сложность примитивных операций благодаря тому, что они окрашивают каждый узел в красный или черный цвет.

Красно-черное дерево используется, потому что дерево AVL требует много оборотов, когда дерево большое, тогда как красно-черное дерево требует максимум двух оборотов для балансировки дерева. Основное различие между AVL-деревом и красно-черным деревом заключается в том, что AVL-дерево строго сбалансировано, а красно-черное дерево не полностью сбалансировано по высоте. Итак, дерево AVL более сбалансировано, чем красно-черное дерево, но красно-черное дерево гарантирует O(LogN)

1.1 Красно-черная древовидная структура

  • Каждый узел окрашен в красный или черный цвет. Однако корень всегда черный, и каждый лист (NIL) черный.
  • Если у красного узла есть потомки, они всегда черные.
  • Для каждого узла любой простой путь от этого узла к любому из его дочерних листьев имеет одинаковую глубину черного (количество черных узлов).
  • Каждый узел в красно-черном дереве имеет следующие атрибуты:
    - ключ, цвет
    - левый дочерний элемент — правый дочерний элемент
    - родитель (кроме корня)
  • В Red Black Trees реализованы два метода самобалансировки:
    - Перекрашивание: включает изменение цвета узла. Если он красный, то измените его на черный и так далее. Однако цвет узлов NULL и ROOT всегда должен быть черным.
    - Вращение: сначала выполняется перекрашивание. Однако, если это не сработает, реализуется ротация.

1.2 Запись и чтение

  • Запись
    Каждый новый вставленный узел в красно-черном дереве имеет красный цвет. Он должен нарушать красно-черное свойство дерева для самобалансировки. Также потому, что вставка красного узла не нарушает свойство глубины красно-черного дерева. Если красный узел присоединен к красному узлу, то правило нарушено, но исправить это будет проще, чем вопрос о нарушении свойства глубины.

  • Чтение
    Поиск в дереве AVL выполняется так же, как и в любом двоичном дереве поиска. Однако деревья AVL имеют лучшую временную сложность поиска из-за того, что дерево RB имеет тенденцию быть более асимметричным, чем дерево AVL.

2. Дерево АВЛ

AVL-дерево — это самобалансирующееся бинарное дерево поиска, в котором разница высот левого и правого поддеревьев любого узла не превышает единицы. Это достигается выполнением вращения дерева, когда коэффициент баланса узла становится больше 1 или меньше -1.

Деревья ALV в основном используются для индексации огромных записей в базе данных, а также для эффективного поиска. Деревья AVL иногда используются в деревьях LSM из-за его запоминаемой основной структуры данных для сортировки и балансировки данных, несмотря на то, что деревья AVL реже используются для вставок и удалений и больше для поиска данных.

2.1 Структура и свойства AVL-дерева

  • У каждого узла должно быть как минимум два потомка, кроме корня.
  • AVL Tree применяет повороты для самобалансировки.
  • Каждый узел должен иметь коэффициент баланса для выполнения последующих поворотов.
  • Дерево всегда сбалансировано путем применения поворотов в соответствии с коэффициентами баланса узлов.
  • Все основные операции (вставки, удаления, поиски) имеют временную сложность Log(N)
    — поиски являются основным доменом
  • Каждый узел в дереве AVL имеет
    — ключ, коэффициент баланса
    — левый дочерний элемент — правый дочерний элемент
    — родитель (кроме корня)

2.2 Запись и чтение

Записывает

Вставки в дерево AVL выполняются так же, как и в двоичные деревья поиска. Однако основное различие между деревьями BST и AVL заключается в том, что деревья AVL поддерживают самобалансировку в соответствии с коэффициентом баланса каждого узла, существующего в дереве. AVL не будет выполнять балансировку каждый раз при вставке данных, если дерево хорошо сбалансировано. Как видно на изображении слева, деревья AVL выполняют 4 различных случая самобалансировки, чтобы обеспечить сбалансированные свойства дерева.

  • Лево-правый случай: правое нижнее дерево (дочернее) смещается вместе с родителем, если родитель находится слева от дерева от прародительского узла.
  • Право-левый случай: левое нижнее дерево (дочернее) смещается вместе с родителем, если родитель находится справа от дерева от прародительского узла.
  • Левый-левый случай: дерево будет вращаться вправо
  • Право-правый случай: дерево будет вращаться влево

Читает

Поиск в дереве AVL выполняется так же, как и в любом бинарном дереве поиска. Преимущество деревьев AVL заключается в том, что количество сравнений для поиска данных гарантированно равно log(N) благодаря сохранению высоты дерева.

3. Плюсы и минусы дерева RB и AVL

Деревья AVL

Плюсы

  • Деревья AVL могут самобалансироваться.
  • Это не перекошено.
  • Он обеспечивает более быстрый поиск, чем Red-Black Trees.
  • Лучшая временная сложность поиска по сравнению с другими деревьями, такими как бинарное дерево.
  • Высота не может превышать log(N), где N — общее количество узлов в дереве.

Минусы

  • Он имеет высокие постоянные коэффициенты для некоторых операций.
  • Менее используется по сравнению с красно-черными деревьями.
  • AVL имеет сложные операции вставки и удаления, поскольку выполняется больше поворотов из-за свойства строгого баланса.
  • Требуется больше обработки для балансировки

Деревья РБ

Плюсы

  • RB Trees также предоставляют методы самобалансировки. По сравнению с деревьями AVL, деревья RB имеют два метода балансировки (окраска, повороты).
  • Деревья RB имеют лучшую производительность при приеме и удалении, потому что не нужно постоянно вращать дерево, чтобы сбалансировать его. Сначала он меняет цвет узлов, чтобы сбалансировать дерево.
  • Высота не может превышать log(N), где N — общее количество черных узлов в дереве.

Минусы

  • Деревья RB имеют более низкую производительность для операций поиска.
  • Это немного более искажено, чем деревья AVL, из-за того, что у него есть своего рода ленивый метод самобалансировки (раскрашивание).

4. Таблица сравнения деревьев RB, AVL, B

  • В следующей таблице показаны основные различия между деревьями RB и AVL по сравнению с известным B-деревом.

Рекомендации

Дерево РБ

  1. Введение в Red-Black Tree [Гики для гиков]
  2. Знакомство с красно-черными деревьями
  3. https://www.programiz.com/dsa/red-black-tree
  4. https://www.eecs.umich.edu/courses/eecs380/ALG/red_black.html
  5. https://www.programiz.com/dsa/insertion-in-a-red-black-tree
  6. https://www.geeksforgeeks.org/insertion-in-red-black-tree/
  7. ВВЕДЕНИЕ В БИНАРНЫЙ ПОИСК И КРАСНО-ЧЕРНЫЕ ДЕРЕВЬЯ
  8. https://www.youtube.com/watch?v=2MdsebfJOyM&ab_channel=쉬운코드
  9. https://yongdanielliang.github.io/animation/web/RBTree.html [Попробуйте сами]
  10. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html [Попробуйте сами 2]
  11. https://www.codesdope.com/course/data-structures-red-black-trees-insertion/

АВЛ-дерево

  1. https://www.geeksforgeeks.org/introduction-to-avl-tree/
  2. https://www.geeksforgeeks.org/insertion-in-an-avl-tree/
  3. https://www.geeksforgeeks.org/how-is-an-avl-tree-different-from-a-b-tree/?ref=rp
  4. https://www.geeksforgeeks.org/insertion-in-an-avl-tree/
  5. https://www.geeksforgeeks.org/deletion-in-an-avl-tree/
  6. https://www.geeksforgeeks.org/avl-trees-content-a-parent-node-pointer/
  7. https://ijirt.org/master/publishedpaper/IJIRT101072_PAPER.pdf
  8. https://www.youtube.com/watch?v=syGPNOhsnI4&ab_channel=쉬운코드
  9. https://en.wikipedia.org/wiki/AVL_tree