Алгоритмы trainee
Что такое бинарное дерево поиска (BST)?
Ответ
Дерево, где для каждого узла: все элементы в левом поддереве меньше, в правом — больше. Поиск, вставка, удаление — O(log n) в сбалансированном дереве. В несбалансированном — деградирует до O(n) (как связный список).
Разбор: В BST для каждого узла все элементы левого поддерева меньше, а правого — больше, что и даёт логарифмический поиск в сбалансированном случае. Главная ловушка: обычное BST само по себе не балансируется (балансировка — это AVL/красно-чёрные деревья), поэтому в худшем случае оно вырождается в список с O(n). Вариант про «больше слева» путает порядок, а про «больше потомков» описывает кучу, где нет упорядоченности для бинарного поиска.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.