Содержание
- 2. Преимущества и недостатки n-арных деревьев Очевидное преимущество n-арных деревьев - их меньшая высота, чем у бинарных
- 3. Деревья цифрового поиска Деревья цифрового поиска (digital search trees - DST) представляют собой n-арные деревья, ветвление
- 4. Пример 180, 195, 1867, 768, 207, 217, 2174, 21749, 27, 307, 368; Если ключи состоят из
- 5. Анализ деревьев цифрового поиска Производительность для худшего случая деревьев, построенных по методу поразрядного поиска, значительно выше
- 6. Уплотненный лес Данные деревья можно сделать еще меньше, исключив те узлы, из которых можно достичь только
- 7. Модификация цифрового дерева Если набор ключей является плотным внутри множества всех возможных ключей, то процесс поиска
- 8. Представление уплотненного леса с помощью двумерного массива (“БОРа”) 180, 195, 1867, 768, 207, 217, 2174, 21749,
- 9. Trie-деревья (нагруженные деревья) Обычно в узлах дерева поиска хранятся значения ключей, но в случае, когда ключами
- 10. Пример Trie-дерева triе-деревья представляют собой структуры данных, применение которых не уступает по эффективности методам хеширования.
- 11. Достоинства нагруженных деревьев К достоинствам нагруженных деревьев можно отнести возможность перемещения по дереву и выполнения различных
- 12. Patricia – деревья Основанный на trie-деревьях поиск обладает двумя недостатками: однонаправленное ветвление приводит к созданию дополнительных
- 13. Синтаксические деревья Схема грамматического разбора отображаемая синтаксис предложения в форме дерева называется синтаксическим деревом. С другой
- 14. Пример синтаксического дерева для арифметического выражения 9 – 5 + 2 а = 5 + 10
- 15. Преобразование упорядоченного n-арного дерева в двоичное дерево Любое дерево может быть единственным образом представлено бинарным деревом.
- 16. На первом этапе для каждого узла уничтожаются все исходящие из нее ребра, кроме самого левого ребра.
- 17. На втором этапе для каждой вершины дерева осуществляется выбор ее левого и правого сыновей по следующему
- 19. Скачать презентацию