Дерево поиска — это структура данных, обычно бинарное дерево, в котором для каждого узла выполняется свойство: все элементы в левом поддереве меньше значения узла, а все элементы в правом поддереве — больше или равны.

Поиск элемента в таком дереве происходит следующим образом:

Начинаем с корня дерева.
Сравниваем искомое значение с текущим узлом.
Если значения совпали — элемент найден.
Если искомое значение меньше, переходим в левое поддерево.
Если больше — в правое поддерево.
Повторяем шаги 2–5, пока не найдём элемент или не достигнем листа (тогда элемент отсутствует).

Пример на Python:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    else:
        return search(root.right, key)

Таким образом, поиск в сбалансированном дереве происходит за O(log n) времени.

Объясните, каким образом функционирует структура данных дерево поиска и как осуществляется поиск элементов в ней.