TwiddleLab / Код / Структуры данных, которые видно

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

Урок 7 из 10 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Двоичное дерево поиска соблюдает одно правило в каждом узле: меньшие значения в левой ветке, большие в правой.
• Вставка и поиск проходят один путь от корня вниз, по одной проверке на уровень.
• Скорость решает высота (число уровней). У пышного дерева из n узлов около log2 n уровней.
• Вставь отсортированные данные, и дерево станет палкой: n уровней, так же медленно, как список.

Начать урок

Как идёт урок

1. Список контактов, где и добавлять быстро, и искать быстро. Можно получить оба?

   Это дерево чисел построено по одному правилу. Куда пойдёт 7?

2. Построй дерево своими руками.

   Каждое число стартует сверху. В каждом узле: меньшее идёт влево, большее вправо.

   Каждое сравнение отправляет число в одну ветку, а другую не трогает. Поэтому новое число всегда попадает в пустое место, где правило всё ещё выполняется.

3. Теперь поищи в нём.

   Есть ли в дереве 13? А 5? Пройди по шагам и посчитай проверки.

4. Двоичное дерево поиска.

   Двоичное дерево поиска (BST): у каждого узла не больше двух детей, и в каждом узле меньшие значения идут влево, а большие вправо.

   Вставка и поиск проходят один путь вниз от корня: не больше одной проверки на уровень.

   Число уровней это высота дерева. Высота решает, насколько оно быстрое.

5. Контакты приходят уже отсортированными: 1, 2, 3, 4, 5, 6, 7.

   Какой формы будет дерево? Нажми на ставку и смотри.

6. Пышное дерево.

   Те же 7 чисел, другой порядок. Меняй их местами, пока дерево не станет всего в 3 уровня.

7. Идеально пышное дерево хранит 1 000 000 контактов. Примерно сколько у него уровней?

   Каждый уровень вмещает вдвое больше узлов, чем уровень над ним: 1, 2, 4, 8, ...

   Полное дерево с h уровнями вмещает 2^h - 1 узлов. 2^19 - 1 = 524 287 мало, а 2^20 - 1 = 1 048 575 хватает, значит, 20 уровней. В математике это log2 1 000 000, около 19,9, округлённое вверх.

8. Побудь поиском.

   Нажимай на узлы, которые проверяет поиск 45, по порядку.

9. Гонка: палка против твоего пышного дерева.

   Какое найдёт контакт 7 за меньшее число проверок? Нажми на него, потом «Проверить».

   Поиск проходит один путь от корня, по одному узлу на уровень. У твоего дерева 3 уровня, у палки 7. С миллионом контактов это около 20 проверок против до миллиона.

Предыдущий урок: Деревья: папки в папках · Следующий урок: Кучи и очереди с приоритетом · Часть курса: Структуры данных, которые видно

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.