Изменения

Перейти к: навигация, поиск

2-3 дерево

24 байта добавлено, 20:53, 11 мая 2015
Следующий и предыдущий
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом:
будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда влево. Таким образом, мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Случай с предыдущим симметричен.
Node nextTnext('''int xT'''x) Node t = search(x) '''if''' (t.keys[0] > x) //x не было в дереве, и мы нашли следующий сразу '''return''' t '''while''' (t != '''null''') t = t.parent if (можно свернуть направо вниз) в t помещаем вершину, в которую свернули '''while''' (пока t {{---}} не лист) t = t.sons[0]
'''return''' t
'''while''' (t != '''null''') t = t.parent if (можно свернуть направо вниз) в t помещаем вершину, в которую свернули '''while''' (пока t {{---}} не лист) t = t.sons[0] '''return''' t '''return''' t.keys[0];
Анонимный участник

Навигация