2-3 дерево
Содержание
Свойства
2-3 дерево — сбалансированное дерево поиска, обладающее следующими свойствами:
- нелистовые вершины имеют либо 2, либо 3 сына,
- нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения. Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
- сыновья упорядочены по значению максимума поддерева сына,
- все листья лежат на одной глубине,
- Высота 2-3 дерева , где — количество элементов в дереве.
Операции
Введем следующие обозначения:
- — корень 2-3 дерева.
Каждый узел дерева обладает полями:
- — родитель узла,
- — сыновья узла,
- — ключи узла,
- — количество сыновей.
Поиск
- — искомое значение,
- — текущая вершина в дереве.
Изначально . Будем просматривать ключи в узлах, пока узел не является листом. Рассмотрим два случая:
- у текущей вершины два сына. Если её значение меньше , то , иначе .
- у текущей вершины три сына. Если второе значение меньше , то . Если первое значение меньше , то , иначе .
Node search(int x):
Node t = root
while (t не является листом)
if (t.length == 2)
if (t.keys[0] < x)
t = t.sons[1]
else t = t.sons[0]
else
if (t.keys[1] < x)
t = t.sons[2]
else
if (t.keys[0] < x)
t = t.sons[1]
else t = t.sons[0]
return t
Пример поиска в 2-3 дереве, так как элемент 6 существует, то был возвращен корректный узел, так как элемента 10 нет, возвращается некорректный узел. На основе этого можно сделать метод , проверяющий наличии элемента в дереве.
Вставка элемента
- — добавляемое значение,
- — текущая вершина в дереве. Изначально .
Если корня не существует — дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:
Найдем сперва, где бы находился элемент, применив . Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент — лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало 4, то разделим родителя на два узла, и повторим разделение теперь для его родителя (перед разделением обновим ключи).
splitParent(Node t):
if (t.length > 3)
Node a;
a.sons[0] = t.sons[2]
a.sons[1] = t.sons[3]
t.sons[2].parent = a
t.sons[3].parent = a
a.keys[0] = t.keys[2]
a.length = 2
t.length = 2
t.sons[2] = null
t.sons[3] = null
if (t.parent != null)
t.parent[t.length] = a
t.length++
сортируем сыновей у t.parent
splitParent(t.parent)
else //мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем
Node t = root
root.sons[0] = t
root.sons[1] = a
t.parent = root
a.parent = root
root.length = 2
сортируем сыновей у root
Если сыновей стало 3, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:
updateKeys(Node t):
Node a = t.parent
while (a != null)
for i = 0 .. a.length - 1
a.keys[i] = max(a.sons[i]) //max — возвращает максимальное значение в поддереве.
a = a.parent //Примечание: max легко находить, если хранить максимум
//правого поддерева в каждом узле — это значение и будет max(a.sons[i])
необходимо запускать от нового узла. Добавление элемента:
insert(int x): Node n = Node(x) if (root == null) root = n return Node a = search(x) if (a.parent == null) Node t = root root.sons[0] = t root.sons[1] = n t.parent = root n.parent = root root.length = 2 сортируем сыновей у root else Node p = a.parent p.sons[p.length] = n p.length++ n.parent = p сортируем сыновей у p updateKeys(n) split(n) updateKeys(n)
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то работает за .
Примеры добавления:
Удаление элемента
- — значение удаляемого узла,
- — текущий узел.
Пусть изначально — узел, где находится x.
Если у не существует родителя, то это корень. Удалим его.
Если у существует родитель, и у него 3 сына, то просто удалим t. Обновим ключи, запустив от любого брата .
Если у родителя() 2 сына, то удалим , а его брата( перецепим к родителю соседнего листа(обозначим его за ). Вызовем и , так как у могло оказаться 4 сына. Удалим теперь и . После возврата из рекурсии обновим все ключи с помощью , запустившись от .
Следующий и предыдущий
- — поисковый параметр,
- — текущий узел.
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом: будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
Node next(int x)
Node t = search(x)
if (t.keys[0] > x) //x не было в дереве, и мы нашли следующий сразу
return t
while (t != null)
t = t.parent
if (можно свернуть направо вниз)
в t помещаем вершину, в которую свернули
while (пока t — не лист)
t = t.sons[0]
return t
return t;
Find
B+ деревья, поддерживают операцию , которая позволяет находить m следующих элементов. Так как все листья отсортированы в порядке возрастания, то просто свяжем каждый лист с соседями.
- — правый лист,
- — левый лист.
Доработаем добавление. Когда мы уже добавили элемент и обновили ключи, найдем для него следующий, и запишем на него ссылку в , найдем предыдущий и запишем на него ссылку в ,так же и его соседям укажем ссылка на него.
Доработаем удаление. При удалении элемента, мы просто связываем его соседей за .
См. также
Источники информации
- is.ifmo.ru — Визуализатор 2-3 дерева
- rain.ifmo.ru — Визуализатор 2-3 дерева
- Википедия — 2-3 дерево
- Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
