Изменения

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

Левосторонние красно-чёрные деревья

4 байта убрано, 15:21, 18 июня 2018
Поиск
==Поиск==
Поиск в левосторонних красно-черных деревьях эквивалентен поиску в [[Дерево поиска, наивная реализация|наивной реализации дерева поиска]].
Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом,который проходит от вершины корня до искомого элемента. Если же элемент отсутствует, цикл пройдет до листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
===Псевдокод===
'''Value''' search(key : '''Key''')
Анонимный участник

Навигация