Изменения

=== Find Нахождение 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>.Добавим к узлам следующие поля:*<tex>\mathtt{right}</tex> {{---}} указывает на правый лист,*<tex>\mathtt{left}</tex> {{---}} указывает на левый лист.Доработаем добавлениеПусть <tex>t</tex> - добавленный узел. Когда Изменим <tex>\mathtt{insert}</tex> следующим образом: в самом конце, после того как мы уже добавили элемент и обновили все ключи, найдем для него следующий, <tex>\mathtt{next(t)}</tex> и запишем ссылку на него ссылку в <tex>\mathtt{t.right}</tex>. Аналогично с левым.Пусть <tex>t</tex> - удаляемый узел.Изменим <tex>\mathtt{insert}</tex> следующим образом: в самом начале, до удаления <tex>t</tex>, найдем предыдущий следующий (<tex>mathtt{next}</tex>) и запишем на него ссылку в (<tex>\mathtt{next.left}</tex>) правый лист относительно <tex>t</tex>. С левым поступим аналогично. В итоге, мы имеем двусвязный список в листьях, и чтобы нам вывести <tex>m</tex> элементов,так же нам достаточно один раз найти нужный элемент и его соседям укажем ссылка пробежаться вправо на него<tex>m</tex> элементов.