403
правки
Изменения
→next и prev
== next и prev ==
Алгоритм нахождения следующего элемента, как и два предыдущих, сводится к рассмотрению случая, когда дерево содержит не более одного элемента, либо к поиску в одном из его поддеревьев:
*если дерево пусто, или максимум этого дерева не превосходит <tex> x </tex>, то следующего элемента в этом дереве не существует.*если <tex> x </tex> меньше поля <tex> min </tex>, то искомый элемент и есть <tex> min </tex>.*если дерево содержит не более двух элементов, и <tex> x < max </tex>, то искомый элемент <tex> max </tex>.
*если же в дереве более двух элементов, то:
**если в дереве есть еще числа, большие <tex> x </tex>, и чьи старшие биты равны <tex> high(x) </tex>, то продолжим поиск в поддереве <tex> children[high(x)] </tex>, где будем искать число, следующее после <tex> low(x) </tex>.**иначе искомым элементом является либо минимум следующего непустого поддерева, если такое есть, либо максимум текущего дерева в противном случае.
Так как в поддеревьях хранятся не все биты исходных элементов, а только часть их, то для восстановления исходного числа, по имеющимся старшим и младшим битам, будем использовать функцию <tex> merge </tex>.
