143
правки
Изменения
→Поиск
'''else''' t = t.sons[0]
'''return''' t
Пример поиска в 2-3 дереве, так как элемент 6 существует, то был возвращен корректный узел, так как элемента 10 нет, возвращается некорректный узел. На основе этого можно сделать метод <tex>\mathtt{exist}</tex>, проверяющий наличии элемента в дереве.
[[Файл:23treesearch.png|border]]
Найдем сперва, где бы находился элемент, применив search(x). Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало 4, то разделим родителя на два узла, и повторим разделение теперь для его родителя(перед разделением обновим ключи).
splitParent('''Node''' t):
*<tex>\mathtt{left}</tex> - левый лист.
Доработаем добавление. Когда мы уже добавили элемент и обновили ключи, найдем для него следующий, и запишем на него ссылку в <tex>\mathtt{right}</tex>, найдем предыдущий и запишем на него ссылку в <tex>\mathtt{left}</tex>,так же и его соседям укажем ссылка на него.
Доработаем удаление. При удалении элемента, мы просто связываем его соседей за <tex>O(1)</tex>.
