В информатике дерево 2–3 — это древовидная структура данных , где каждый узел с дочерними элементами ( внутренний узел ) имеет либо двух дочерних элементов (2-узла) и один элемент данных , либо трех дочерних элементов (3-узла) и два элемента данных. Дерево 2–3 — это B-дерево порядка 3. [1] Узлы снаружи дерева ( листовые узлы ) не имеют дочерних элементов и имеют один или два элемента данных. [2] [3] 2–3 дерева были изобретены Джоном Хопкрофтом в 1970 году. [4]
2–3 дерева должны быть сбалансированы, то есть каждый лист находится на одном уровне. Отсюда следует, что каждое правое, центральное и левое поддерево узла содержит одинаковый или почти одинаковый объем данных.
Мы говорим, что внутренний узел является 2-узлом, если он имеет один элемент данных и двух дочерних элементов.
Мы говорим, что внутренний узел является 3-узлом, если он имеет два элемента данных и три дочерних элемента.
4-узловой узел с тремя элементами данных может быть временно создан во время манипуляций с деревом, но никогда не сохраняется в дереве постоянно.
Мы говорим, что T является деревом 2–3 тогда и только тогда, когда выполнено одно из следующих утверждений: [5]
Поиск элемента в дереве 2–3 аналогичен поиску элемента в бинарном дереве поиска . Поскольку элементы данных в каждом узле упорядочены, функция поиска будет направлена к правильному поддереву и, в конечном итоге, к правильному узлу, содержащему элемент.
Вставка сохраняет сбалансированность дерева. [5]
Для вставки в 2-узел новый ключ добавляется к 2-узлу в соответствующем порядке.
Для вставки в 3-узел может потребоваться дополнительная работа в зависимости от расположения 3-узла. Если дерево состоит только из 3-узлов, узел разбивается на три 2-узла с соответствующими ключами и дочерними элементами.
Если целевой узел является 3-узлом, родителем которого является 2-узел, ключ вставляется в 3-узел, чтобы создать временный 4-узел. На рисунке ключ 10 вставлен во 2-узел вместе с 6 и 9. Средний ключ — 9, и он повышается до родительского 2-узла. В результате остается 3-узел из 6 и 10, который разделяется на два 2-узла, которые являются дочерними элементами родительского 3-узла.
Если целевой узел является 3-узлом, а родительский — 3-узлом, создается временный 4-узел, а затем разделяется, как указано выше. Этот процесс продолжается вверх по дереву до корня. Если корень необходимо разделить, то следует процесс единого 3-узла: временный 4-узловой корень разбивается на три 2-узла, один из которых считается корнем. Эта операция увеличивает высоту дерева на единицу.
Удаление ключа из неконечного узла можно выполнить, заменив его его непосредственным предшественником или преемником, а затем удалив предшественника или преемника из листового узла. Удалить ключ из листового узла легко, если лист является трехузлом. В противном случае может потребоваться создание временного 1-узла, который может быть поглощен путем реорганизации дерева, или он может неоднократно перемещаться вверх, прежде чем его можно будет поглотить, как это может сделать временный 4-узел в случае вставки. В качестве альтернативы можно использовать алгоритм, который работает как сверху вниз, так и снизу вверх, создавая временные 4 узла на пути вниз, которые затем уничтожаются при обратном движении вверх. Более подробно методы удаления описаны в ссылках. [5] [6]
Поскольку деревья 2–3 по структуре аналогичны красно-черным деревьям , параллельные алгоритмы для красно-черных деревьев можно применить и к деревьям 2–3.
2–3 дерева, определенные в конце раздела 6.2.3, эквивалентны B-деревьям порядка 3.