Изменения

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

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

167 байт убрано, 16:20, 16 января 2017
Проверка того, что заданное дерево является деревом поиска
Функция принимает на вход исследуемую вершину, а также два значения: <tex>\mathtt{min}</tex> и <tex>\mathtt{max}</tex>, которые до вызова функции равнялись <tex> \infty </tex> и <tex> -\infty </tex> соответственно, где <tex> \infty </tex> — очень большое число, т.е. ни один ключ дерева не превосходит его по модулю. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно. Необходимо также помнить, в каком поддереве для более старших предков мы находимся. Например, в этом дереве вершина с номером <tex>8</tex> находится левее вершины, в которой лежит <tex>5</tex>, чего не должно быть в дереве поиска, однако после проверки функция бы вернула <tex>\mathtt{true}</tex>.
'''functionbool''' lookisBinarySearchTree(Tree[n]root: '''Node''') <font color="green">// Здесь Tree — заданное двоичное дерево.</font>
'''bool''' check(v : '''Node''', min: '''intT''', max: '''intT'''): <font color="green">// min и max — минимально и максимально допустимые значения в вершинах поддерева.</font> '''if''' v.left !== ''null'' '''return''' ''true'' '''if''' v.left.key > v.key <= min '''or''' max <= v.left.key < min '''return''' ''false'' '''else''' '''return''' check(v.left, min, v.key) '''if''' v.right != ''null'' '''if''' v.right.key < v.key '''or''' v.right.key > max '''return''' ''false'' '''else''' '''returnand''' check(v.right, v.key, max) '''return''' ''true''
'''return''' check(root, <tex> -\infty </tex>, <tex> -\infty </tex>) <font color="green">// root {{--- }} корень дерева.</font>
Время работы алгоритма {{---}} <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в дереве.

Навигация