143
правки
Изменения
→Нахождение m следующих элементов
=== Нахождение m следующих элементов ===
B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Наивная реализация выглядит следующим образом, : будем вызывать <tex>m</tex> раз поиск следующего элемента, такое решение работает за <tex>O(m * \log{n})</tex>. Но 2-3 деревья, позволяют находить m следующих элементов за <tex>O(m + \log{n})</tex>, что значительно ускоряет поиск при больших <tex>m</tex>.
По построению, все листья у нас отсортированы в порядке возрастания, воспользуемся этим для нахождения m элементов. Нам необходимо связать листья, для этого модифицируем
<tex>\mathtt{insert}</tex> и <tex>\mathtt{delete}</tex>. Добавим к узлам следующие поля:
