Деревья двоичного поиска

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Деревья двоичного поиска широко распространены в программировании.

Значение содержимого каждой вершины дерева двоичного поиска:

1) больше или равно, чем содержимое любой из вершин его левого поддерева;

2) меньше, чем содержимое любой из вершин его правого поддерева.

Распространенность деревьев двоичного поиска в программировании является следствием эффективности методов поиска в этих деревьях.

Для линейных структур сложность алгоритма последовательного поиска равна O (n), где n – это количество элементов структуры.

Для законченного бинарного дерева сложность алгоритма поиска равна

Например, в списке из 10 000 элементов максимальное число сравнений при последовательном поиске равно 10 000.

Поиск на законченном дереве потребовал бы не более 14-ти сравнений.

Алгоритм вставки элемента в дерево двоичного поиска (просмотр дерева всегда начинается с его корня):

1. Значение, помещаемое в дерево, сравнивается со значением текущего узла.

2. Если значение, помещаемое в дерево, меньше значения текущего узла, то проверяется следующее:

a. если у текущего узла слева нет наследников, то прикрепляем узел со значением в качестве левого наследника;

b. иначе спускаемся по левой ветви дерева на уровень ниже

3. Если значение, помещаемое в дерево, больше или равно значению текущего узла, то проверяется следующее:

a. если у текущего узла справа нет наследников, то прикрепляем узел со значением в качестве правого наследника;

b. иначе спускаемся по правой ветви дерева на уровень ниже.