stringtranslate.com

2–3 дерева

В информатике дерево 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 аналогичен поиску элемента в бинарном дереве поиска . Поскольку элементы данных в каждом узле упорядочены, функция поиска будет направлена ​​к правильному поддереву и, в конечном итоге, к правильному узлу, содержащему элемент.

  1. Пусть T — дерево размером 2–3, а d — элемент данных, который мы хотим найти. Если T пусто, то d нет в T , и все готово.
  2. Пусть t будет корнем T .
  3. Предположим, что t — лист.
    • Если d нет в t , то d нет в T. В противном случае d находится в T . Нам не нужно никаких дальнейших шагов, и все готово.
  4. Предположим, что t — 2-узел с левым дочерним элементом p и правым дочерним элементом q . Пусть a будет элементом данных в t . Есть три случая:
    • Если d равно a , то мы нашли d в T и все готово.
    • Если , то присвойте T значение p , которое по определению является деревом 2–3, и вернитесь к шагу 2.
    • Если , то установите T равным q и вернитесь к шагу 2.
  5. Предположим, что 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-узла с соответствующими ключами и дочерними элементами.

Вставка числа в дерево 2–3 для 3 возможных случаев.

Если целевой узел является 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.

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

Рекомендации

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

Внешние ссылки