Из Википедии, бесплатной энциклопедии
  (Перенаправлено с 2-3-4 дерева )
Перейти к навигации Перейти к поиску
2-3-4 дерево
Типдерево
Сложность времени в большой нотации O
АлгоритмСреднийХудший случай
КосмосО ( п )О ( п )
ПоискO (журнал n )O (журнал n )
ВставлятьO (журнал n )O (журнал n )
УдалитьO (журнал n )O (журнал n )

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

  • 2-узел имеет один элемент данных , а если внутренний - два дочерних узла;
  • 3-узел имеет два элемента данных, а если внутренний - три дочерних узла;
  • 4-узел имеет три элемента данных, а если внутренний - четыре дочерних узла;

  • 2 узла

  • 3 узла

  • 4 узла

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

2-3-4 деревья являются изометрией из красно-черных деревьев , а это означает , что они представляют собой эквивалентные структуры данных. Другими словами, для каждого 2–3–4 дерева существует по крайней мере одно красно-черное дерево с элементами данных в том же порядке. Более того, операции вставки и удаления на 2–3–4 деревьях, которые вызывают расширение, разбиение и слияние узлов, эквивалентны переворачиванию цвета и повороту в красно-черных деревьях. При знакомстве с красно-черными деревьями обычно сначала вводятся 2–3–4 дерева, потому что они концептуально проще. Однако 2–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.svg
  • Начните с корня (10, 20) и спускайтесь к самому правому дочернему элементу (22, 24, 29). (Его интервал (20, ∞) содержит 25.)
  • Узел (22, 24, 29) - это 4-узел, поэтому его средний элемент 24 вставлен в родительский узел.
2-3-4-этап-вставки-дерева-2.svg
  • Оставшийся 3-узел (22, 29) разбивается на пару 2-узлов (22) и (29). Вернитесь к новому родителю (10, 20, 24).
  • Спуститесь к самому правому ребенку (29). (Его интервал (24, ∞) содержит 25.)
2-3-4-этап-вставки-дерева-3.svg
  • Узел (29) не имеет крайнего левого потомка. (Дочерний элемент для интервала (24, 29) пуст.) Остановитесь здесь и вставьте значение 25 в этот узел.
2-3-4-этап-вставки-дерева-4.svg

Удаление [ править ]

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

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

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

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

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

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

Удаление в дереве 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-е изд.), Нью-Джерси: Прентис Холл, стр. 683, ISBN 0-13-085850-1
  4. ^ Гудрич, Майкл Т ; Тамассия, Роберто ; Маунт, Дэвид М. (2002), Структуры данных и алгоритмы в C ++ , Wiley , ISBN 0-471-20208-8
  5. ^ Грама, Анант (2004). «(2,4) Деревья» (PDF) . CS251: Конспекты лекций по структурам данных . Департамент компьютерных наук, Университет Пердью . Проверено 10 апреля 2008 .

Внешние ссылки [ править ]

  • Алгоритмы в действии, с анимацией 2–3–4 дерева
  • Красно-черные деревья, склоняющиеся влево - Принстонский университет, 2008 г.
  • Структуры открытых данных - Раздел 9.1 - 2–4 дерева , Пат Морин
  • 2-3-4 Деревья: Визуальное введение, 2017