Изменения

Алгоритм нахождения следующего элемента, как и два предыдущих, сводится к рассмотрению случая, когда дерево содержит не более одного элемента, либо к поиску в одном из его поддеревьев:*если дерево пусто, или максимум этого дерева не превосходит <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>. <pre>next(T, x) if empty(T) or T.max <= x return none; // следующего элемента нет if T.min > x return T.min if empty(T.aux) return T.max // в дереве не более двух элементов else if not empty(T.children[high(x)]) and T.childen[high(x)].max > low(x) return merge(high(x), next(T.children[high(x)])); // случай, когда следующее число начинается с high(x) else // иначе найдем следующее непустое поддерево nextHigh = next(T.aux, high(x)); if nextHigh == null return T.max // если такого нет, вернем максимум else return merge(high(x), T.children[nextHigh].min); // если есть, вернем минимум найденного поддерева</pre> Время работы, как и всех предыдущих функций, оценивается так же, и равно <tex>O(\log k)</tex>. Функция <tex> prev </tex> реализуется аналогично.