143
правки
Изменения
→Слияние двух деревьев
[[Файл:Treedelete.png|border|1150px]]
=== Слияние двух деревьев Следующий и предыдущий ===<tex>x</tex> {{---}} поисковый параметр<tex>t</tex> {{---}} текущий узелВ силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом:Будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда налево. Таким образом мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Симметрично разбирается и случай с предыдущим. Node next('''int 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 '''return''' t; [[Файл:Treenext.png|border|325px]] [[Файл:Treeprev.png|border|300px]]
== Cсылки ==
