Что такое бинарное дерево поиска?

Бинарное дерево поиска (Binary Search Tree, BST) — это особый вид бинарного дерева данных, в котором каждый узел содержит ключ (значение), и для каждого узла выполняется следующее свойство:

• Ключи всех узлов в левом поддереве меньше ключа данного узла.
• Ключи всех узлов в правом поддереве больше ключа данного узла.
• Левое и правое поддеревья также являются бинарными деревьями поиска.

Это свойство позволяет эффективно осуществлять операции поиска, вставки и удаления элементов. В сбалансированном бинарном дереве поиска эти операции выполняются за время O(log n), где n — количество узлов в дереве. В худшем случае (вырожденное дерево) время выполнения может достигать O(n), превращая дерево в связанный список.

Пример узла:

javascript