Изменения

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

Дерево поиска, наивная реализация

149 байт добавлено, 01:26, 16 января 2017
Задачи на поиск максимального BST в заданном двоичном дереве
* Левое и правое поддерево являются деревьями поиска.
Введём <tex>\mathtt{v.min}</tex> и <tex>\mathtt{v.max}</tex>, которые будут хранить минимум в левом поддереве вершины и максимум в правом. Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины <tex>\mathtt{v}</tex> между этими значениями <tex>\mathtt{v.min}</tex> и <tex>\mathtt{v.max}</tex>. Если вершина является листом, она автоматически становится деревом поиска, а её ключ {{---}} минимумом или максимумом для её родителя (в зависимости от расположения вершины). Функция <tex>\mathtt{cnt}</tex> записывает в <tex>\mathtt{v.kol}</tex> количество вершин в дереве, если оно является деревом поиска или <tex>\mathtt{-1}</tex> в противном случае. После её выполнения функции ищем за линейное время вершину с наибольшим значением <tex>\mathtt{v.kol}</tex>.
'''int''' cnt(v: '''Node''')
'''return''' res
Время работы алгоритма {{---}} <tex>O(n^2)</tex>. Существуют также алгоритмы, позволяющие найти поддерево за линейное время.
===Восстановление дерева по результату обхода preorderTraversal===
243
правки

Навигация