Изменения
Нет описания правки
Данные функции принимают корень дерева, и возвращают минимальный(максимальный) элемент в дереве. Обе процедуры выполняются за время <tex>O(h)</tex>.
=== поиск следующего и предыдущего элемента ===
Tree_next(root x)
if (x.right != null)
return Tree_min(x.right)
else
Если у узла, следующий элемент которого мы хотим найти, есть правое поддерево, то следующий за ним элемент - минимальный в этом поддереве. Иначе нужно следовать вверх, пока не будет найден узел, являющийся левым потомком своего родителя.
=== вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении нулевого указателя нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма.
=== удаление ===
== Литература ==
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
