#структура_данных 

![[Pasted image 20250115085437.png]]

> BST — это разновидность бинарного дерева, в которой все значения в левом поддереве меньше значения узла, а все значения в правом поддереве больше значения узла.


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


Более того, все числа в поддереве левого дочернего узла меньше самого узла!

![[Pasted image 20250115085537.png]]
***
Оба дерева состоят из 7 узлов, но сильно различаются по производительности

![[Pasted image 20250115085610.png]]

Высота дерева для лучшего случая равна 2. Это означает, что к любому узлу
можно перейти от корневого узла максимум за 2 шага. Высота дерева для
худшего случая равна 6. Это означает, что к любому узлу можно перейти от
корневого узла максимум за 6 шагов. 

Дерево для худшего случая имеет высоту $O(n)$, так что поиск будет выполняться за время $O(n)$

Дерево для лучшего случая имеет высоту $O(log(n))$, а поиск по нему займет время $O(log(n))$.

Если можно обеспечить высоту дерева в $O(log(n))$, то поиск по дереву будет выполняться за время $O(log(n))$


Связанные темы:
- [[Дерево (Tree)]]
- [[Бинарное дерево (Binary tree)]]
- [[Граф (Graph)]]

Источники:
- [[Адитья Бхаргава - Грокаем Алгоритмы]]