Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Введите кличку животного:

Бенни Ха-ха

Введите вид животного:

попугай

Программа членства в клубе Nerfville Pet Club Введите букву, соответствующую вашему выбору: а) добавление животного 1) вывод списка животных n) количество животных f) поиск животных d) удаление животного q) выход а

Введите кличку животного:

Дон Бавилио

Введите вид животного:

домашний кот

Программа членства в клубе Nerfville Pet Club Введите букву, соответствующую вашему выбору: а) добавление животного 1) вывод списка животных

n) количество животных f) поиск животных

d) удаление животного q) выход

n

3 животных в клубе

Программа членства в клубе Nerfville Pet Club Введите букву, соответствующую вашему выбору: а) добавление животного 1) вывод списка животных

n) количество животных f) поиск животных

d) удаление животного q) выход 1

Животное: БЕННИ ХА-ХА Животное: ДОН БАЗИЛИО Животное: КУИНСИ

Программа членства в клубе Nerfville Pet Club Введите букву, соответствующую вашему выбору: а) добавление животного 1) вывод списка животных n) количество животных f) поиск животных

d) удаление животного q) выход

q

Программа завершена.

786 глава 17

Соображения по поводу дерева

Двоичное дерево поиска обладает рядом недостатков. Например, двоичное дерево поиска эффективно, только если оно полностью заполнено, или сбалансирована Предположим, что вы сохраняете слова, которые вводятся в произвольном порядке. Есть шансы, что результирующее дерево будет иметь довольно небольшую глубину, как на рис. 17.12. Но представим, что вводятся данные в алфавитном порядке. Тогда каждый новый узел будет добавляться справа, и дерево может приобрести вид, показанный на рис. 17.16. Дерево на рис. 17.12 называют сбалансированным, а на рис. 17.16 — несбалансированным. Поиск в несбалансированном дереве не является более эффективным, чем последовательный поиск в связном списке.

Один из способов избежать получения вытянутых деревьев — применять более тщательный подход к их построению. Если дерево или поддерево начинает становиться слишком перекошенным в одну из сторон, необходимо реорганизовать узлы для улучшения сбалансированности дерева. Аналогично реорганизация дерева может требоваться после удаления узлов. Математики Г.М. Адельсон-Вельский и Е.М. Ландис разработали для этого алгоритм. Деревья, построенные их методом, называют АВД-деревьями (от начальных букв их фамилий). Построение сбалансированного дерева занимает больше времени, т.к. должны предприниматься дополнительные действия по реструктуризации, но тем самым обеспечивается максимальная или близкая к максимальной эффективность поиска.

Иногда может требоваться двоичное дерево поиска, которое допускает наличие дублированных элементов. Для примера предположим, что нужно проанализировать какой-то текст, отслеживая количество появлений в нем каждого слова. Один из возможных подходов к решению этой задачи предусматривает определение Item как структуры, которая содержит одно слово и его количество. Когда слово встречается в тексте первый раз, оно добавляется в дерево, а количество устанавливается в 1. При следующем появлении этого же слова программа находит содержащий его узел и инкрементирует количество. Преобразование базового двоичного дерева поиска, чтобы оно работало в подобной манере, не займет много времени.

Для ознакомления с еще одним возможным вариантом дерева, мы снова обратимся к примеру с клубом Nelville Pet Club. В этом примере сортировка дерева осуществлялась как по кличкам, так и по видам животных. Поэтому оно могло бы содержать кота Сэма в одном узле, собаку Сэма — во втором и хомяка Сэма — в третьем. Тем не менее, в дереве не могло быть двух котов с кличкой Сэм. Еще один возможный под-

Расширенное представление данных 787

ход заключается в упорядочении дерева только по кличкам животных. Само по себе это изменение разрешило бы существование только одного Сэма, независимо от вида, но затем можно было бы определить Item как список структур, а не как одиночную структуру. Тогда при первом появлении животного с кличкой Салли программа создала бы новый узел, затем новый список, после чего добавила бы Салли и ее вид в этот список. Следующее животное Салли было бы направлено в этот же узел и добавлено в список.

Дополнительные библиотеки