В информатике , А 2-3 - дерево представляет собой древовидную структуру данных , где каждый узел с детьми ( внутренний узел ) имеет либо двух детей (2-узел) и один элемент данных или трех детей (3-узлы) и два элемента данных. Дерево 2–3 - это B-дерево порядка 3. [1] Узлы вне дерева ( листовые узлы ) не имеют потомков и одного или двух элементов данных. [2] [3] 2–3 дерева были изобретены Джоном Хопкрофтом в 1970 году. [4]
2–3 дерева | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Тип | дерево | ||||||||||||||||||||
Изобретенный | 1970 г. | ||||||||||||||||||||
Изобретенный | Джон Хопкрофт | ||||||||||||||||||||
Сложность времени в большой нотации O | |||||||||||||||||||||
|
Требуется сбалансировать 2–3 дерева, что означает, что каждый лист находится на одном уровне. Отсюда следует, что каждое правое, центральное и левое поддерево узла содержит одинаковый или почти одинаковый объем данных.
Определения
Мы говорим, что внутренний узел является 2-узлом, если он имеет один элемент данных и два потомка.
Мы говорим, что внутренний узел является 3-узлом, если он имеет два элемента данных и три дочерних узла .
4-узел , с элементами три данных, могут временно создаваться во время манипуляций с деревом , но никогда не постоянно хранится в дереве.
2 узел
3 узел
Мы говорим, что T является 2–3 деревом тогда и только тогда, когда выполняется одно из следующих утверждений: [5]
- Т пусто. Другими словами, у 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 .
Характеристики
- Каждый внутренний узел является двух- или трехузловым.
- Все листья находятся на одном уровне.
- Все данные хранятся в отсортированном порядке.
Операции
Searching
Поиск элемента в дереве 2–3 аналогичен поиску элемента в двоичном дереве поиска . Поскольку элементы данных в каждом узле упорядочены, функция поиска будет направлена на правильное поддерево и, в конечном итоге, на правильный узел, содержащий элемент.
- Пусть T будет 2–3 деревом, а d - элементом данных, который мы хотим найти. Если T пусто, значит, d нет в T, и мы закончили.
- Пусть т быть корнем Т .
- Предположим, что t - лист.
- Если d не в т , то 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-узел, чтобы создать временный 4-узел. На иллюстрации ключ 10 вставлен в 2-узел с 6 и 9. Средний ключ - 9, и он повышается до родительского 2-узла. В результате остается 3-узел из 6 и 10, который разделяется на два 2-узла, которые являются потомками родительского 3-узла.
Если целевой узел является 3-узлом, а родительский - 3-узлом, создается временный 4-узел и затем разделяется, как указано выше. Этот процесс продолжается вверх по дереву до корня. Если корень должен быть разделен, то следует процесс одного 3-узла: временный 4-узловой корень разбивается на три 2-узла, один из которых считается корнем. Эта операция увеличивает высоту дерева на единицу.
Параллельные операции
Поскольку 2–3 дерева аналогичны по структуре красно-черным деревьям , параллельные алгоритмы для красно-черных деревьев можно применять и к 2–3 деревьям.
Смотрите также
Рекомендации
- ^ Кнут, Дональд М (1998). «6.2.4». Искусство программирования . 3 (2-е изд.). Эддисон Уэсли. ISBN 9780201896855.
2–3 дерева, определенные в конце раздела 6.2.3, эквивалентны B-деревьям порядка 3.
- ^ Гросс, Р. Эрнандес, Дж. К. Лазаро, Р. Дормидо, С. Рос (2001). Estructura de Datos y Algoritmos . Прентис Холл. ISBN 84-205-2980-Х.
- ^ Ахо, Альфред V .; Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1974). Дизайн и анализ компьютерных алгоритмов . Эддисон-Уэсли., стр.145–147
- ^ Кормен, Томас (2009). Введение в алгоритмы . Лондон: MIT Press. С. 504 . ISBN 978-0262033848.
- ^ а б Седжвик, Роберт; Уэйн, Кевин. «3.3». Алгоритмы (4-е изд.). Эддисон Уэсли. ISBN 9780321573513.