3622
правки
Изменения
м
→Следующий и предыдущий
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом:
будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
'''T''' next('''T''' x):
Node t = search(x)
'''if''' (t.keys[0] > x) <font color=green> //x не было в дереве, и мы нашли следующий сразу</font>
