2–3 дерева - 2–3 tree

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

Требуется сбалансировать 2–3 дерева, что означает, что каждый лист находится на одном уровне. Отсюда следует, что каждое правое, центральное и левое поддерево узла содержит одинаковый или почти одинаковый объем данных.

• 1 Определения
• 2 Свойства
• 3 Операции
  • 3.1 Поиск
  • 3.2 Вставка
  • 3.3 Параллельные операции
• 4 См. Также
• 5 Ссылки
• 6 Внешние ссылки

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

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

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

• 

  2 узла

• 

  3 узла

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

• T пусто. Другими словами, T не имеет узлов.
• T - это 2-узел с элементом данных a. Если у T есть левый дочерний элемент p и правый дочерний элемент q, то
  • p и q непустые. 2–3 дерева одинаковой высоты ;
  • a больше, чем каждый элемент в p; и
  • a меньше или равно каждому элементу данных в q.
• T представляет собой 3-узел с элементами данных a и b, где a < b. If T has left child p, middle child q, and right child r, then
  • p, q и r не являются пустые 2–3 дерева одинаковой высоты;
  • a больше каждого элемента данных в p и меньше или равно каждому элементу данных в q; и
  • b больше каждого элемента данных в q и меньше или равно каждому элементу данных в r.

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

Поиск

Поиск элемента в 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.
   • Если $d>a\; \{\backslash \; displaystyle\; d>a\}$, затем установите T на q и вернитесь к шагу 2.
5. Предположим, что t - 3-узел с левым дочерним элементом p, средним дочерним элементом q и правым дочерним элементом r. Пусть a и b - два элемента данных t, где . Возможны четыре случая:
   • Если d равно a или b, тогда d находится в T, и все готово.
   • Если , тогда установите T на p и вернитесь к шагу 2.
   • Если , затем установите T равным q и вернитесь к шагу 2.
   • Если $d>b\; \{\backslash \; displaystyle\; d>b\}$, затем установите T на r и вернитесь к шагу 2.

Insertio n

Вставка поддерживает сбалансированное свойство дерева.

Чтобы вставить в 2-узел, новый ключ добавляется к 2-узлу в соответствующем порядке.

Для вставки в 3-узел может потребоваться дополнительная работа в зависимости от расположения 3-узла. Если дерево состоит только из трех узлов, узел разбивается на три двухузловых с соответствующими ключами и дочерними элементами.

Вставка числа в дерево 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 деревьям.

• 2–3–4 дерево
• 2–3 куча
• AA-дерево
• B-tree
• (a, b) -дерево
• Finger tree

• 2–3 Дерево. Подробное описание