143
правки
Изменения
Нет описания правки
[[Файл:23treemain.png|400px|пример Пример 2-3 дерева|thumb]]''' 2-3 дерево '''(англ. ''Heapsort'') — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]].
== Свойства ==
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
Пример поиска в 2-3 дереве, так как элемент <tex>6</tex> существует, то был возвращен корректный узел, так как элемента <tex>10</tex> нет, возвращается некорректный узел. На основе этого можно сделать метод <tex>\mathtt{exist}</tex>, проверяющий наличии элемента в дереве.
[[Файл:23treesearch.png|thumb|center|600px|поиск Поиск элемента 2]]
=== Вставка элемента ===
Примеры добавления:
[[Файл:23treeinsert.png|thumb|center|добавление Добавление элемента с ключом 6|600px]]
=== Удаление элемента ===
Если у родителя(<tex>\mathtt{t.parent}</tex>) <tex>2</tex> сына, то удалим <tex>t</tex>, а его брата(<tex>b</tex> перецепим к родителю соседнего листа(обозначим его за <tex>p</tex>). Вызовем <tex>\mathtt{updateKeys}(b)</tex> и <tex>\mathtt{splitParent}(p)</tex>, так как у <tex>p</tex> могло оказаться <tex>4</tex> сына. Удалим теперь и <tex>\mathtt{t.parent}</tex>. После возврата из рекурсии обновим все ключи с помощью <tex>\mathtt{updateKeys()}</tex>, запустившись от <tex>b</tex>.
[[Файл:23treedelete.png|thumb|center|удаление Удаление элемента с ключом 2|1150px]]
=== Следующий и предыдущий ===
[[Файл:23treenext.png|thumb|center|400px|путь Путь при поиске следующего элемента после 2]]
=== Нахождение m следующих элементов ===
[[Файл:23treefindm.png|thumb|изменение Изменение ссылок при добавлении нового элемента|thumb|center|800px]]
== См. также ==
