403
правки
Изменения
→find
Алгоритм поиска сам напрашивается из выше описанной структуры:
*если дерево пусто, то число не содержится в нашей структуре
*если число равно полю <tex>min</tex> или <tex>max</tex>, то число в дереве есть
*иначе ищем число <tex>low(x)</tex> в поддереве <tex>children[high(x)]</tex>
return find(T.children[high(x)], low(x));
</pre>
Заметим, что выполняя операцию <tex>find</tex>, мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, выходим из нее. В худшем случае мы спустимся от корня до какого-нибудь 1-дерева, то есть выполним операцию <tex>find</tex> столько раз, какова высота нашего дерева. На каждом уровне мы совершаем <tex>O(1)</tex> операций. Следовательно время работы <tex>O(\log k)</tex>.
== insert ==
