В информатике дерево 2–3–4 (также называемое деревом 2–4 ). представляет собой самобалансирующуюся структуру данных , которая обычно используется для реализации словарей. Цифры означают дерево , где каждый узел с дочерними узлами (внутренний узел ) имеет два, три или четыре дочерних узла:
- 2-узел имеет один элемент данных, и если внутренний имеет два дочерних узла;
- 3-узел имеет два элемента данных, а если внутренний имеет три дочерних узла;
- а 4 -node имеет три элемента данных, а если internal имеет четыре дочерних узла;
2–3–4 дерева - это B-деревья порядка 4; как и B-деревья в целом, они могут выполнять поиск, вставку и удаление за O (log n) времени. Одно из свойств дерева 2–3–4 состоит в том, что все внешние узлы находятся на одной глубине.
2–3–4 дерева - это изометрия красно-черных деревьев, что означает, что они являются эквивалентными структурами данных. Другими словами, для каждого 2–3–4 дерева существует как минимум одно красно-черное дерево с элементами данных в том же порядке. Более того, операции вставки и удаления на 2–3–4 деревьях, которые вызывают расширение, разбиение и слияние узлов, эквивалентны переворачиванию цвета и повороту в красно-черных деревьях. При знакомстве с красно-черными деревьями обычно сначала вводятся 2–3–4 дерева, поскольку они концептуально проще. Однако 2–3–4 дерева может быть трудно реализовать на большинстве языков программирования из-за большого количества особых случаев, связанных с операциями с деревом. Красно-черные деревья проще реализовать, поэтому, как правило, используются вместо них.
Содержание
- 1 Свойства
- 2 Вставка
- 3 Удаление
- 4 Параллельные операции
- 5 См. Также
- 6 Ссылки
- 7 Внешние ссылки
Свойства
- Каждый узел (листовой или внутренний) является 2-узлом, 3-узлом или 4-узлом и содержит один, два или три элемента данных соответственно.
- Все листья находятся в одинаковая глубина (нижний уровень).
- Все данные хранятся в отсортированном порядке.
Вставка
Чтобы вставить значение, мы начинаем с корня дерева 2–3–4 :
- Если текущий узел - 4 узла:
- Удалите и сохраните среднее значение, чтобы получить 3 узла.
- Разделите оставшиеся 3 узла на пару 2 узла (теперь отсутствующее среднее значение обрабатывается на следующем шаге).
- Если это корневой узел (у которого, таким образом, нет родителя):
- среднее значение становится новым корнем 2 узла, и высота дерева увеличивается на 1. Поднимитесь в корень.
- В противном случае переместите среднее значение вверх в родительский узел. Поднимитесь к родительскому узлу.
- Найдите дочерний элемент, интервал которого содержит значение, которое нужно вставить.
- Если этот дочерний элемент является листом, вставьте значение в дочерний узел и закончите.
- В противном случае спуститесь в дочерний элемент и повторите с шага 1.
Пример
Чтобы вставить значение «25» в это дерево 2–3–4:
- Начните с корень (10, 20) и спускаемся к самому правому дочернему элементу (22, 24, 29). (Его интервал (20, ∞) содержит 25.)
- Узел (22, 24, 29) является 4-узлом, поэтому его средний элемент 24 вставляется в родительский узел.
- Оставшиеся 3-узел (22, 29) разбивается на пару 2-узлов (22) и (29). Вернитесь к новому родителю (10, 20, 24).
- Спуститесь к самому правому дочернему элементу (29). (Его интервал (24, ∞) содержит 25.)
- Узел (29) не имеет крайнего левого потомка. (Дочерний элемент для interval (24, 29) пуст.) Остановитесь здесь и вставьте в этот узел значение 25.
Удаление
Простейшая возможность удалить элемент - просто оставить элемент там и отметить это как «удалено», адаптируя предыдущие алгоритмы так, чтобы удаленные элементы игнорировались. Затем удаленные элементы можно повторно использовать, перезаписав их при последующей вставке. Однако недостатком этого метода является то, что размер дерева не уменьшается. Если большая часть элементов дерева будет удалена, то дерево станет намного больше, чем текущий размер хранимых элементов, и удаленные элементы негативно повлияют на производительность других операций.
Когда это нежелательно, можно использовать следующий алгоритм для удаления значения из дерева 2–3–4:
- Найдите элемент, который нужно удалить.
- Если элемент не находится в листовом узле, запомните его расположение и продолжайте поиск, пока не будет достигнут лист, который будет содержать преемника элемента. Последующим может быть либо самый большой ключ, который меньше удаляемого, либо самый маленький ключ, который больше, чем тот, который нужно удалить. Проще всего вносить изменения в дерево сверху вниз, чтобы найденный листовой узел не был двухузлом. Таким образом, после замены не будет пустого листового узла.
- Если элемент находится в листе с двумя узлами, просто внесите изменения ниже.
Внесите следующие настройки, когда 2- узел - за исключением корневого узла - встречается на пути к листу, который мы хотим удалить:
- Если одноуровневый узел по обе стороны от этого узла является 3-узлом или 4-узлом (таким образом, имеет более 1 ключа), выполните ротацию с этим узлом:
- Ключ от другого брата, ближайшего к этому узлу, перемещается вверх до родительского ключа, который перекрывает два узла.
- Родительский ключ перемещается вниз к этому узлу чтобы сформировать 3-узел.
- Дочерний элемент, который изначально был с повернутым ключом-братом, теперь является дополнительным дочерним узлом этого узла.
- Если родительский узел является 2-узлом, а его брат также является 2-узлом, объедините все три элемента, чтобы сформировать новый 4-узел, и сократите дерево. (Это правило может сработать только в том случае, если родительский 2-узел является корнем, поскольку все остальные 2-узлы на этом пути будут изменены, чтобы не быть 2-узлами. Вот почему здесь «сокращение дерева» сохраняет баланс; это также важное предположение для операции слияния.)
- Если родитель является 3-узлом или 4-узлом, а все соседние узлы являются 2-узлами, выполните операцию слияния с родителем и соседним узлом:
- Соседний одноуровневый ключ и родительский ключ, выходящий на два одноуровневых узла, объединяются, чтобы сформировать 4 узла.
- Перенести дочерних узлов на этот узел.
После достижения искомого значения, теперь его можно без проблем разместить в месте удаленной записи, потому что мы убедились, что конечный узел имеет более одного ключа.
Удаление в дереве 2–3–4 составляет O (log n), при условии, что передача и объединение выполняются за постоянное время (O (1)).
Параллельные операции
Поскольку 2–3–4 дерева аналогичны по структуре красно-черным деревьям, параллельные алгоритмы для красно-черных деревьев могут применяться также к 2–3–4 деревьям.
См. Также
Портал компьютерного программирования
Ссылки
Внешние ссылки
 | Wikimedia У Commons есть медиафайлы, связанные с 2-3-4-деревьями. |
Портал компьютерного программирования 
