Один интерфейс множеств и три представления
Сравнение неупорядоченных списков, упорядоченных списков и деревьев поиска отделяет принадлежность и добавление от обхода представления.
Какие операции становятся менее затратными, когда представление множества гарантирует порядок или форму дерева поиска?
- Реализация проверки принадлежности и добавления для множества на неупорядоченном списке
- Использование порядка возрастания для ранней остановки проверки принадлежности и вставки на нужное место
- Переход по одной ветви при каждом сравнении в бинарном дереве поиска
- Преобразование множества в виде дерева в упорядоченную последовательность без изменения смысла принадлежности
- Сравнение сбалансированности и стоимости поиска для различных форм деревьев
Множество на основе неупорядоченного списка может поместить новый элемент в начало после проверки на дубликаты. Множество на основе упорядоченного списка учитывает порядок возрастания: если текущий элемент уже больше искомого, проверка принадлежности может остановиться, а добавление выполнит вставку перед ним. Абстрактные вопросы остаются теми же, но инвариант представления меняет процесс.
Бинарное дерево поиска хранит меньшие элементы слева, а большие элементы справа. Каждое сравнение выбирает одну ветвь вместо сканирования каждого элемента. tree->list выполняет центрированный обход и восстанавливает упорядоченную последовательность. Сбалансированное построенное вручную дерево демонстрирует правило поиска, тогда как несбалансированное дерево показывает линейный путь.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Программа со списками множеств возвращает ((1 3 5) (4 1 3 5) #f (1 3 4 5 7)). Программа с деревьями возвращает (#t #f (1 3 4 5 7 8 9)).
Сравните просмотр неупорядоченного списка с ранней остановкой упорядоченного списка перед 5. В ordered-adjoin найдите единственную точку вставки. В дереве зафиксируйте, выбирает ли каждое сравнение левую или правую ветвь, а затем сопоставьте этот путь с полным центрированным обходом в tree->list.
Измените программу и сравните результат.
Реализуйте adjoin-tree и вставьте 6 в пример дерева. Подтвердите принадлежность и упорядоченный результат tree->list, затем создайте намеренно несбалансированное дерево и сравните его линейный путь поиска с логарифмическим путем сбалансированного дерева.
Показать подсказку
Используйте те же три варианта сравнения, что и в tree-member?, перестраивая только ту ветвь, которая получает новое значение.