Двоичное дерево поиска (BST) — это особый вид двоичного дерева, в котором выполняются два условия:
Все левые дочерние узлы имеют значение меньше, чем значение их родительского узла
Все правые дочерние узлы имеют значение больше, чем значение их родительского узла
Таким образом, для каждого узла либо отсутствует какой-либо дочерний узел, либо слева расположен меньший по значению узел, а справа — больший.
Двоичное дерево поиска с 8 узлами
Данная особенность особенно удобна при поиске элемента в двоичном дереве. Если мы ищем значение x, благодаря описанному принципу всегда понятно, в какую сторону двигаться. В приведённом примере, чтобы найти узел со значением 3, мы сначала смотрим на корень со значением 5. Поскольку 5 больше 3, переходим к левому дочернему узлу. Далее мы видим узел со значением 2, а так как 2 меньше 3, переходим к правому дочернему узлу. Затем мы видим узел со значением 4, и поскольку 4 больше 3, снова идём влево. В итоге находим узел со значением 3, который и искали.
# Предположим, что несуществующие узлы представлены как None, а не как значение 0
def search(node: Node | None, x: int):
""" Возвращает True, если x присутствует в дереве, и False в противном случае """
if node is None: # Если мы достигли конца дерева
return False # Значит, значение x не найдено
if x == node.value: # Если x равно значению узла
return True # => мы нашли нужное значение x в дереве
if x < node.value: # Если x меньше => нужно идти влево
return search(node.left) # Пытаемся найти x в левом поддереве
return search(node.right) # В противном случае пробуем найти x в правом поддереве
Такой способ поиска может быть весьма эффективным, если высота дерева невелика. На каждом шаге мы переходим либо к левому, либо к правому поддереву, поэтому максимальное число операций при поиске в таком двоичном дереве будет пропорционально высоте дерева в худшем случае.
Задача: Проверить, является ли заданное дерево BST
Имеется двоичное дерево, и нужно определить, является ли оно двоичным деревом поиска.
Ввод
Во вводе содержатся разделённые пробелами целые числа, соответствующие значениям узлов двоичного дерева. Порядок значений определяется обходом, при котором мы всегда движемся сначала в левое, затем в правое поддерево. Значение 0 означает, что узел не существует. Гарантируется, что введённое двоичное дерево корректно и что все значения уникальны.
Вывод
Программа должна вывести «Yes», если двоичное дерево является деревом поиска, и «No» в противном случае.
Примеры
Input
Output
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
No
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0
Yes
Пояснение
Пример 1: Хотя все правые дочерние узлы больше родительских, не все левые узлы меньше своих родителей.
Пример 2: Это двоичное дерево является деревом поиска, так как все левые дочерние узлы имеют значение меньше, чем у родителя, а все правые — больше.
.png?table=block&id=18a2c681-664d-8159-80ca-d93f70df50b4&cache=v2)
