2–3 дерева

В информатике 2–3-дерево — это древовидная структура данных , в которой каждый узел с потомками ( внутренний узел ) имеет либо двух потомков (2-узел) и один элемент данных , либо трех потомков (3-узел) и два элемента данных. 2–3-дерево — это B-дерево порядка 3. ^[1] Узлы на внешней стороне дерева ( листовые узлы ) не имеют потомков и имеют один или два элемента данных. ^[2]^[3] 2–3-деревья были изобретены Джоном Хопкрофтом в 1970 году. ^[4]

Для балансировки требуется 2–3 дерева, что означает, что каждый лист находится на одном уровне. Из этого следует, что каждое правое, центральное и левое поддерево узла содержит одинаковое или близкое к одинаковому количество данных.

Определения

Мы говорим, что внутренний узел является 2-узлом, если он имеет один элемент данных и два дочерних элемента.

Мы говорим, что внутренний узел является 3-узлом, если он имеет два элемента данных и три дочерних элемента.

Четырехузел с тремя элементами данных может быть временно создан во время манипуляций с деревом, но никогда не сохраняется в дереве постоянно .

2 узла
3 узла

Мы говорим, что $T$ является 2–3-деревом тогда и только тогда, когда выполняется одно из следующих утверждений: ^[5]

$T$ пуст. Другими словами, $T$ не имеет узлов.
T — это 2-узел с элементом данных a . Если T имеет левого потомка p и правого потомка q , то
- $p$ и $q$ — 2–3 дерева одинаковой высоты ;
- $a$ больше, чем каждый элемент в $p$ ; и
- $a$ меньше каждого элемента данных в $q$ .
T — это 3-узел с элементами данных a и b , где a < b . Если T имеет левого потомка p , среднего потомка q и правого потомка r , то
- $p$ , $q$ и $r$ — 2–3 дерева одинаковой высоты;
- $a$ больше, чем каждый элемент данных в $p$ и меньше, чем каждый элемент данных в $q$ ; и
- $b$ больше каждого элемента данных в $q$ и меньше каждого элемента данных в $r$ .

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

Каждый внутренний узел является 2-узловым или 3-узловым.
Все листья находятся на одном уровне.
Все данные хранятся в отсортированном порядке.

Операции

Идет поиск

Поиск элемента в дереве 2–3 аналогичен поиску элемента в бинарном дереве поиска . Поскольку элементы данных в каждом узле упорядочены, функция поиска будет направлена на правильное поддерево и в конечном итоге на правильный узел, содержащий элемент.

Пусть $T$ будет деревом 2–3, а $d$ — элементом данных, который мы хотим найти. Если $T$ пуст, то $d$ не находится в $T$ , и мы закончили.
Пусть $t$ будет корнем $T.$
Предположим, что t — лист.
- Если $d$ не содержится в $t$ , то $d$ не содержится в $T.$ В противном случае $d$ содержится в $T.$ Нам не нужны дальнейшие шаги, и мы закончили.
Предположим, что t — это 2-узел с левым потомком p и правым потомком q . Пусть a — элемент данных в t . Возможны три случая:
- Если $d$ равно $a$ , то мы нашли $d$ в $T$ и все готово.
- Если , то установите $T$ в $p$ , что по определению является деревом 2–3, и вернитесь к шагу 2. $д<а$
- Если , то установите $T$ в $q$ и вернитесь к шагу 2. $д>а$
Предположим, что t — это 3-узел с левым потомком p , средним потомком q и правым потомком r . Пусть a и b — два элемента данных t , где . Существует четыре случая: $а<б$
- Если $d$ равно $a$ или $b$ , то $d$ содержится в $T$ , и мы закончили.
- Если , то установите $T$ в $p$ и вернитесь к шагу 2. $д<а$
- Если , то установите $T$ в $q$ и вернитесь к шагу 2. $а<д<б$
- Если , то установите $T$ в $r$ и вернитесь к шагу 2. $д>б$

Вставка

Вставка сохраняет сбалансированное свойство дерева. ^[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-узла, один из которых считается корнем. Эта операция увеличивает высоту дерева на единицу.

Удаление

Удаление ключа из нелистового узла можно выполнить, заменив его его непосредственным предшественником или преемником, а затем удалив предшественника или преемника из листового узла. Удаление ключа из листового узла легко, если лист является 3-узлом. В противном случае может потребоваться создание временного 1-узла, который может быть поглощен путем реорганизации дерева, или он может многократно перемещаться вверх, прежде чем его можно будет поглотить, как это может сделать временный 4-узел в случае вставки. В качестве альтернативы можно использовать алгоритм, который является как сверху вниз, так и снизу вверх, создавая временные 4-узла на пути вниз, которые затем уничтожаются при обратном движении вверх. Методы удаления более подробно описаны в ссылках. ^[5]^[6]

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

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

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

Ссылки

^ Кнут, Дональд М (1998). "6.2.4". Искусство программирования . Том 3 (2-е изд.). Эддисон Уэсли. ISBN 978-0-201-89685-5Деревья 2–3 , определенные в конце раздела 6.2.3, эквивалентны B-деревьям порядка 3.
^ Р. Эрнандес; Х. К. Лазаро; Р. Дормидо; С. Рось (2001). Структура данных и алгоритмов . Прентис Холл. ISBN 84-205-2980-X.
^ Ахо, Альфред В.; Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1974). Проектирование и анализ компьютерных алгоритмов . Эддисон-Уэсли., стр.145–147
^ Кормен, Томас (2009). Введение в алгоритмы . Лондон: The MIT Press. С. 504. ISBN 978-0-262-03384-8.
^ abc Седжвик, Роберт; Уэйн, Кевин. "3.3". Алгоритмы (4-е изд.). Эддисон Уэсли. ISBN 978-0-321-57351-3.
^ «2-3 Trees», Лин Турбак, раздаточный материал № 26, заметки курса, Структуры данных CS230, Колледж Уэллсли, 2 декабря 2004 г. Доступ 11 марта 2024 г.