Двоичное дерево поиска
Двоичное дерево поиска — интерактивный эксперимент из приложения «Структуры данных», бесплатной симуляции StudyFi Lab, которая работает прямо в браузере.
В каждом узле меньшие значения идут влево, большие — вправо. Поэтому поиск и вставка проходят один путь от корня и занимают O(h), где h — высота дерева; у сбалансированного дерева h ≈ log₂ n. У удаления три случая: лист просто исчезает, узел с одним потомком заменяется этим потомком, а узел с двумя потомками берёт значение своего симметричного (in-order) преемника. Симметричный обход выдаёт значения по возрастанию; похожие деревья лежат в основе индексов баз данных.
Попробуй: Удали корень — у него два потомка, поэтому увидишь поиск преемника. Затем нажми «Вставить отсортированные значения»: дерево вырождается в список, и высота растёт до n.
Частые вопросы
Что показывает эксперимент «Двоичное дерево поиска»?
В каждом узле меньшие значения идут влево, большие — вправо. Поэтому поиск и вставка проходят один путь от корня и занимают O(h), где h — высота дерева; у сбалансированного дерева h ≈ log₂ n. У удаления три случая: лист просто исчезает, узел с одним потомком заменяется этим потомком, а узел с двумя потомками берёт значение своего симметричного (in-order) преемника. Симметричный обход выдаёт значения по возрастанию; похожие деревья лежат в основе индексов баз данных.
Как попробовать «Двоичное дерево поиска»?
Удали корень — у него два потомка, поэтому увидишь поиск преемника. Затем нажми «Вставить отсортированные значения»: дерево вырождается в список, и высота растёт до n.
Готовишься к контрольной?
Загрузи свои конспекты, и StudyFi превратит их в карточки, тесты и подкасты.