На канале уже выпущены две статьи про бинарный поиск и бинарные деревья. Но что же значит «Бинарный»? Давайте разберемся.
«Бинарный» происходит от латинского binarius — «двойной». В информатике это означает «состоящий из двух частей» или «имеющий два варианта».
Ключевые идеи:
* два варианта: да/нет, 0/1, левое/правое;
* выбор между двумя возможностями на каждом шаге.
Бинарный поиск — алгоритм поиска элемента в отсортированном массиве, где на каждом шаге мы:
1. Смотрим на средний элемент массива.
2. Сравниваем его с искомым значением.
3. Отбрасываем половину массива (левую или правую) — в зависимости от результата сравнения.
4. Повторяем шаги 1–3 для оставшейся половины.
Почему «бинарный»: на каждом шаге выбор сводится к двум вариантам:
- искомое значение находится в левой половине;
- искомое значение находится в правой половине.
Бинарное дерево — структура данных, где каждый узел имеет:
- не более двух потомков (левого и правого);
- значение в узле;
- ссылки на левого и правого потомка (или null, если потомка нет).
Бинарное дерево поиска добавляет правило упорядоченности:
* значения в левом поддереве < значения в корне;
* значения в правом поддереве > значения в корне.
Почему «бинарное»: у каждого узла ровно два направления для движения:
- идти влево (если ищем меньшее значение);
- идти вправо (если ищем большее значение).
Что общего? Оба метода используют один и тот же принцип:
1. на каждом шаге выбор между двумя вариантами;
2. исключение половины возможных вариантов;
3. быстрое сужение области поиска.
Таким образом, Бинарный — значит основанный на двух элементах, вариантах или состояниях. Например, мы выбираем чай или кофе :)
1 минута
15 мая