stringtranslate.com

2–3–4 дерева

В информатике дерево 2–3–4 (также называемое деревом 2–4 ) — это самобалансирующаяся структура данных , которая может использоваться для реализации словарей . Числа означают дерево , в котором каждый узел с потомками ( внутренний узел ) имеет два, три или четыре потомка:

Деревья 2–3–4 являются B-деревьями порядка 4; [1] как и B-деревья в целом, они могут выполнять поиск, вставку и удаление за время O (log n ). Одним из свойств дерева 2–3–4 является то, что все внешние узлы находятся на одной глубине.

Деревья 2–3–4 тесно связаны с красно-черными деревьями , интерпретируя красные связи (то есть связи с красными потомками) как внутренние связи 3-узлов и 4-узлов, хотя это соответствие не является однозначным. [2] Красно-черные деревья с левым уклоном ограничивают красно-черные деревья, запрещая узлы с единственным красным правым потомком, что дает однозначное соответствие между красно-черными деревьями с левым уклоном и деревьями 2–3–4.

Характеристики

Вставка

Чтобы вставить значение, начнем с корня дерева 2–3–4:

  1. Если текущий узел является 4-узлом:
    • Удалите и сохраните среднее значение, чтобы получить 3-узел.
    • Разделите оставшиеся 3 узла на пару из 2 узлов (теперь отсутствующее среднее значение обрабатывается на следующем шаге).
    • Если это корневой узел (у которого, таким образом, нет родителя):
      • среднее значение становится новым корневым 2-узлом, а высота дерева увеличивается на 1. Поднимаемся в корень.
    • В противном случае, проталкиваем среднее значение вверх в родительский узел. Поднимаемся в родительский узел.
  2. Найдите дочерний элемент, интервал которого содержит значение, которое необходимо вставить.
  3. Если этот дочерний узел является листом, вставьте значение в дочерний узел и завершите работу.
    • В противном случае спуститесь к ребенку и повторите с шага 1. [3] [4]

Пример

Чтобы вставить значение «25» в это дерево 2–3–4:

Удаление

Самая простая возможность удалить элемент — просто оставить элемент там и пометить его как «удаленный», адаптировав предыдущие алгоритмы так, чтобы удаленные элементы игнорировались. Удаленные элементы затем можно повторно использовать, перезаписав их при выполнении вставки позже. Однако недостатком этого метода является то, что размер дерева не уменьшается. Если удалить большую часть элементов дерева, то дерево станет намного больше текущего размера сохраненных элементов, а производительность других операций будет отрицательно влиять на удаленные элементы.

Если это нежелательно, можно воспользоваться следующим алгоритмом для удаления значения из дерева 2–3–4:

  1. Найдите элемент, который нужно удалить.
    • Если элемент не находится в листовом узле, запомните его местоположение и продолжайте поиск, пока не будет достигнут лист, который будет содержать преемника элемента. Преемником может быть либо наибольший ключ, который меньше удаляемого, либо наименьший ключ, который больше удаляемого. Проще всего вносить изменения в дерево сверху вниз таким образом, чтобы найденный листовой узел не был 2-узлом. Таким образом, после обмена не будет пустого листового узла.
    • Если элемент находится в листе с 2 узлами, просто внесите изменения, указанные ниже.

Внесите следующие изменения, если на пути к листу, который мы хотим удалить, встречается 2-узел (за исключением корневого узла):

  1. Если собрат по обе стороны от этого узла является 3-узлом или 4-узлом (имеющим, таким образом, более 1 ключа), выполните поворот с этим собратом:
    • Ключ от другого ближайшего к этому узлу родственного узла перемещается вверх к родительскому ключу, который просматривает два узла.
    • Родительский ключ перемещается вниз к этому узлу, образуя 3-узел.
    • Дочерний элемент, который изначально имел повернутый родственный ключ, теперь является дополнительным дочерним элементом этого узла.
  2. Если родительский узел является 2-узлом, а родственный узел также является 2-узлом, объедините все три элемента, чтобы сформировать новый 4-узел, и сократите дерево. (Это правило может сработать только в том случае, если родительский 2-узел является корнем, поскольку все остальные 2-узлы по пути будут изменены, чтобы не быть 2-узлами. Вот почему «сократить дерево» здесь сохраняет баланс; это также важное предположение для операции слияния.)
  3. Если родительский узел является 3-узлом или 4-узлом, а все смежные с ним узлы являются 2-узлами, выполните операцию слияния с родительским узлом и смежным с ним узлом:
    • Соседний родственный узел и родительский ключ, просматривающий два родственных узла, объединяются, образуя 4-узел.
    • Перенесите дочерние элементы брата или сестры в этот узел.

Как только искомое значение будет достигнуто, его можно без проблем поместить на место удаленной записи, поскольку мы гарантируем, что конечный узел имеет более 1 ключа.

Удаление в дереве 2–3–4 выполняется за O(log n), предполагая, что перенос и слияние выполняются за постоянное время (O(1)). [3] [5]

Параллельные операции

Поскольку 2–3–4-деревья по своей структуре похожи на красно-черные деревья , параллельные алгоритмы для красно-черных деревьев можно применять и к 2–3–4-деревьям.

Смотрите также

Ссылки

  1. ^ Кнут, Дональд (1998). Сортировка и поиск . Искусство программирования . Том 3 (Второе изд.). Эддисон–Уэсли. ISBN 0-201-89685-0.. Раздел 6.2.4: Многоканальные деревья, стр. 481–491. Также, стр. 476–477 раздела 6.2.3 (Сбалансированные деревья) обсуждают 2–3 дерева.
  2. ^ Седжвик, Роберт (2008). "Левые красно-черные деревья" (PDF) . Левые красно-черные деревья . Кафедра компьютерных наук, Принстонский университет.
  3. ^ Форд, Уильям; Топп, Уильям (2002), Структуры данных с C++ с использованием STL (2-е изд.), Нью-Джерси: Prentice Hall, стр. 683, ISBN 0-13-085850-1
  4. ^ Гудрич, Майкл Т .; Тамассиа, Роберто ; Маунт, Дэвид М. (2002), Структуры данных и алгоритмы в C++ , Wiley , ISBN 0-471-20208-8
  5. ^ Grama, Ananth (2004). "(2,4) Деревья" (PDF) . CS251: Конспект лекций по структурам данных . Кафедра компьютерных наук, Университет Пердью . Получено 10 апреля 2008 г. .

Внешние ссылки

На Викискладе есть медиафайлы по теме 2-3-4-Деревья .