Размер
Сравнения

Операция В среднем В худшем случае

Подробнее о структурах данных

Визуализатор структур данных

Структура данных — это способ хранить данные так, чтобы на самые частые вопросы можно было быстро ответить. Выберите одну из одиннадцати классических структур, от стека до красно-чёрного дерева, введите значение и нажмите операцию. Каждый шаг разворачивается на экране: какой узел сравнивается, какая ссылка меняется, почему дерево поворачивается или значение всплывает, с фразой, которая называет происходящее. Плитки считают работу каждой операции, а таблица даёт время её выполнения. Выберите структуру, введите значение и нажмите операцию. Каждая операция проигрывается по шагам: выделенные узлы показывают, что сравнивается, перемещается или меняется, а строка под рисунком говорит, что происходит и почему. Кнопки «Назад», «Шаг», «Воспроизвести» и «Конец» позволяют пройти шаги ещё раз. «Случайное заполнение» и «Очистить» начинают заново, а «Отменить» откатывает операцию. Плитки показывают размер, высоту деревьев, работу последней операции (сравнения, пробы или переходы к родителю) и одно число, важное для структуры; таблица даёт время работы каждой операции.

Как это работает

  1. Выберите структуру, например двоичное дерево поиска, хеш-таблицу или префиксное дерево. Она начинается со случайного содержимого; «Случайное заполнение» и «Очистить» начинают заново.
  2. Введите значение и нажмите операцию: push, в очередь, вставить, удалить, найти, обход, union или find. Шаги проигрываются сами; «Назад», «Шаг», «Воспроизвести» и «Конец» проходят их ещё раз.
  3. Читайте в строке под рисунком, что делает каждый шаг, следите в плитках за размером, высотой и работой последней операции и сравнивайте время работы в таблице.

Списки, стеки и очереди

Простейшие структуры держат элементы в ряд. Стек работает только с одного конца, поэтому последний положенный элемент выходит первым, как в стопке тарелок; очередь добавляет в конец и забирает из начала, как очередь к окошку. Очередь здесь живёт в кольцевом буфере: начало и конец ходят по кругу в фиксированном массиве и после последней ячейки возвращаются к первой, а когда буфер заполняется, элементы копируются в вдвое больший. Связный список соединяет узлы указателями, так что вставка в голову ничего не стоит, но чтобы найти хвост или индекс, приходится идти по ссылкам одна за другой.

Деревья, кучи, хеш-таблицы и множества

Двоичное дерево поиска держит меньшие значения слева, а большие справа, поэтому поиск на каждом шаге вдвое сокращает число кандидатов — пока дерево остаётся ветвистым. АВЛ- и красно-чёрные деревья следят за этим с помощью поворотов, которые можно увидеть и которые названы по своим случаям. Куча держит наверху только наименьшее или наибольшее значение, и большего очереди с приоритетом не нужно. Хеш-таблица прыгает прямо в корзину, вычисленную по ключу, и должна справляться с коллизиями; префиксное дерево делит общие начала слов; union-find почти за постоянное время отвечает, лежат ли два элемента в одном множестве.

Часто задаваемые вопросы

Какую структуру данных выбрать?

Это зависит от вопросов, которые вы задаёте чаще всего. Стек или очередь, когда элементы обрабатываются в порядке поступления или в обратном; хеш-таблицу, чтобы искать по ключу; сбалансированное дерево поиска, например АВЛ- или красно-чёрное, когда нужны ещё и ключи по порядку или ближайший ключ; кучу, когда всегда нужен только наименьший или наибольший элемент; префиксное дерево для слов и префиксов; union-find, чтобы следить за сливающимися группами.

Чем АВЛ-дерево отличается от красно-чёрного?

Оба держат двоичное дерево поиска неглубоким, поэтому каждый поиск, вставка и удаление занимают время, пропорциональное log n. АВЛ-дерево сбалансировано строже: высоты двух сторон каждого узла отличаются не больше чем на единицу, поэтому поиск немного быстрее. Красно-чёрное дерево допускает больше свободы и при изменениях требует меньше поворотов, поэтому многие стандартные библиотеки используют его для своих упорядоченных словарей и множеств.

Почему хеш-таблица может быть медленной в худшем случае?

Если много ключей попадает в одну корзину, поиску приходится проверять их по одному, как в списке. Хорошая хеш-функция распределяет ключи равномерно, а таблица растёт раньше, чем переполнится, поэтому поиск в среднем занимает постоянное время. Попробуйте таблицу размером 10 с числами, оканчивающимися на одну цифру, или слова-анаграммы — и посмотрите, как копятся коллизии.

Что означают числа рядом с узлами АВЛ-дерева?

Это показатели баланса: высота левого поддерева узла минус высота его правого поддерева. В АВЛ-дереве каждый показатель должен быть −1, 0 или +1. Когда вставка или удаление делает какой-то из них +2 или −2, дерево поворачивается в этом узле; случай (LL, RR, LR или RL) говорит, в какую сторону клонится лишняя высота, и решает, нужен один поворот или два.

Отправляется ли что-нибудь на сервер?

Нет. Каждая операция выполняется в вашем браузере, а содержимое каждой структуры сохраняется в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор