Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 113
Текст из файла (страница 113)
15.9. Рис. 15.9 Рис. 15.5 Следующее имя Рассел. Поскольку по алфавиту имя Рассел стоит после имени Петерсон, спускаемся к правому сыну, Смиту. Имя Рассел по алфавиту расположено перед именем Смит; делаем Рассела левым сыном Смита, как показано на рис. 15.!О, Рис. 15.10 Надеемся, что теперь схема начинает проясняться. Предположим, что есть имя, которое необходимо поместить в дерево. Если в вершине дерева уже есть имя и вставляемое имя в алфавитном порядке стоит после этого имени, то следует спуститься к левому сыну, а если оно стоит до этого имени, то нужно спуститься РЯЗДБП 15.2.
Бинарные деревья поиска 633 к правому сыну. Если в вершине нет имени, то имя, которое нужно вставить, помещается в данную вершину. Используя эту процедуру, доведем до конца рассмотрение нашего списка. Следующее имя — Бауэр. По алфавиту оно стоит перед именем Петерсон, поэтому спускаемся к левому сыну, Джонсону. По алфавиту имя Бауэр стоит перед именем Джонсон, поэтому спускаемся к левому сыну, Вейлу. В алфавитном порядке имя Бауэр располагается перед именем Вейл, поэтому спускаемся к левому сыну.
Поскольку там нет имени, делаем Бауэр левым сыном, как показано на рис. 15.11. Рис. 15.11 Следующее имя, которое необходимо сохранить, — Мартин. Это имя по алфавиту стоит перед именем Петерсон, поэтому спускаемся к левому сыну, Джонсону. Но имя Мартин в алфавите следует после имени Джонсон, отсюда спускаемся к правому сыну и, поскольку там нет имени, делаем Мартина правым сыном, как показано на рис. !5.12. Рис. 15.12 Далее имя, которое необходимо сохранить, — Уилсон. Поскольку в алфавитном порядке оно стоит после имени Петерсон, спускаемся к правому сыну, Смиту.
Но имя Уилсон расположено после имени Смит, значит, спускаемся к правому сыну, Спенсеру. Поскольку имя Уилсон стоит по алфавиту после имени Спенсер, и у Спенсера нет правого сына, делаем Уилсона правым сыном Спенсера, как показано на рис.
15.13. Рис. Ы.!3 634 ГЛА8А тб. Деревья Последним по счету, но не по значению, помещаем на свое место имя Лайман. Имя Лайман по алфавиту стоит перед именем Петерсон, спускаемся к левому сыну, Джонсону. Поскольку по алфавиту имя Лайман стоит после имени Джонсон, спускаемся к его правому сыну, Мартину. Так как имя Лайман по алфавиту стоит перед имением Мартин, спускаемся к его левому сыну.
Но там имени нет, поэтому делаем Лаймана левым сыном Мартина. При достижении левого (или правого) сына, который еще не определен, вероятно, точнее было бы сказать: "Если левый (правый) сын не существует, то создаем вершину и сохраняем имя", вместо: "Если там нет имени, то сохраняем имя".
Но в данной ситуации внимание сосредотачивается, в основном, на концепции, а не на технических деталях. Теперь приведем алгоритм вставки имени в дерево поиска, который реально создает дерево поиска, за исключением размешения имени в корне дерева. Используя < и >, следует иметь в виду, что сказанное применимо для любого упорядочения. Вставка(элемент) (1) Начинаем с корня. (2) Если элемент < объекта в вершине, переходим к левому сыну. (3) Если элемент > объекта в вершине, переходим к правому сыну.
(4) Повторяем шаги 2 и 3, пока не достигнем вершины, которая не определена. (5) Если достигнутая вершина не определена, то определяем вершину и вставляем элемент. Поскольку метод создания дерева поиска описан, легко понять, как производить поиск элемента в дереве. Используется, в основном, тот же самый подход, кроме проверки, является ли данное имя больше или меньше имени в вершине, проверяется также несовпадение этого имени с именем в вершине. Если последнее выполняется, процесс поиска завершен. В противном случае повторяются предыдущие действия. Если достигается вершина, которая не определена, это означает, что данное имя не хранится в дереве.
Предположим, например, что в рассмотренном выше дереве разыскивается имя Дженкинс. Поскольку оно "меньше, чем имя Петерсон, идем к левому сыну, Джонсону. Но так как имя Дженкинс "меньше, чем имя Джонсон", идем к левому сыну, Вейлу. Поскольку данное имя "больше, чем Вейл" (на самом деле нет имени больше, чем Вейл), идем к правому сыну.
Но он не определен, поэтому данное имя отсутствует в списке. Далее приведен алгоритм поиска имени в дереве поиска. Поиск(элемент) (1) Начинаем с корня. (2) Если элемент < объекта в вершине, идем к левому сыну. (3) Если элемент > объекта в вершине, идем к правому сыну. (4) Если элемент = объекту в вершине, то имя найдено; выполняем соответствующие действия и выходим. (5) Повторяем шаги 2, 3 и 4, пока не достигнем вершины, которая не определена. РАЗДЕЛ 15.2.
Бинарные деревья поиска 635 (б) Если достигнутая вершина не определена и в дереве нет имени, то выполняем соответствующие действия и выходим. Вполне очевидно, что длина пути поиска элемента не может превышать высоту дерева. Поэтому, если дерево полное, то по теореме 15.9 в самом неблагоприятном варианте длина пути имеет порядок О(1п(п)), где и — число элементов в дереве. Следовательно, если дерево сбалансированное, самый неблагоприятный случай имеет порядок О(!п(п)). В заключение рассмотрим, как удалять вершину из дерева.
Предлагается один из методов. При изложении будут опущены все технические детали, касающиеся его фактической реализации. Метод резюмирован в приведенном ниже алгоритме. Удаление(элемент) (1) Если вершина оо не имеет сыновей, просто удаляем ее. (2) Если вершина ео имеет одного сына, удаляем оо и заменяем ее сыном. (3) Если оо имеет двух сыновей, находим правого сына е~ вершины ио, а затем находим левого сына вершины о~ (если он существует). Продолжаем выбирать левых сыновей каждой найденной вершины, пока не найдется такая вершина и, у которой не будет левого сына. Заменим оо на о и сделаем правого сына вершины о левым сыном родителя вершины о. ПРИМЕР 15.13.
Рассмотрим дерево, изображенное на рис. 15.14. Если удалить вершину х, то получится дерево, изображенное на рис. 15.15. Если же удалить вершину )с, то получится дерево, изображенное на рис. 15.16. Рис. 15.15 Рис. 15.15 Рис. 15.14 Если в исходном дереве удаляется вершина и, нужно спуститься к правому сыну р, а затем к левому сыну й.
Поскольку й не имеет левого сына, это искомый элемент для замены. Итак, меняем и на )с и делаем 1 левым сыном р. В результате получаем дерево, изображенное на рис. 15.17. Если вместо этого необходимо удалить вершину р, следует идти вправо к вершине ю, затем влево к а, затем влево к 7. Поскольку д не имеет левого сына, 636 П1АВ4 15. Деревья это искомая вершина для замены.
Поэтому заменяем р на д и делаем т левым сыном вершины з. В результате получаем дерево, изображенное на рис. 15.18. Рис. 15.П Рис. 15.15 ° УПРАЖНЕНИЯ 1. Задано дерево (рис. 15.19). а) Вставьте букву 1. б) Вставьте букву и. в) Вставьте букву т, 2. Задано дерево из предыдушего упражнения. а) Сколько требуется сравнений для определения того, что ! отсутствует? б) Сколько требуется сравнений для определения того, что и отсутствует? в) Сколько требуется сравнений для определения того, что г" отсутствует? Рис. 15.19 3. Задано дерево (рис. 15.20).
а) Вставьте букву е. РКЗЯЕЛ 15.2. Бинарные деревья поиска 637 б) Вставьте букву п. в) Вставьте букву и. Задано дерево из предыдушего упражнения. а) Сколько требуется сравнений для определения того, что и отсутствует? б) Сколько требуется сравнений для определения того, что и отсутствует? в) Сколько требуется сравнений для определения того, что Ь отсутствует? б. Опишите бинарное дерево с пятью вершинами, которое дает наихудший вариант для поиска? 6. Постройте бинарное дерево для следующих имен, хранящихся в алфавитном порядке, если данные вводились в таком порядке; Говард, Джеймс, Аарон, Спенсер, Джексон, Мэдисон, Винес, Кальхаун, Барнс, Макдав и Петерсон. 7.
Постройте бинарное дерево для имен президентов Соединенных Штатов, хранящихся в алфавитном порядке, если имена вводились в том порядке, в котором президенты находились на своем посту первый срок. 6. Постройте бинарное дерево для приведенных ниже чисел, хранящихся в обычном порядке, если они вводились в следуюшем порядке: 25, 35, 15, 25, 48, 36, 22, 44, 18, 30, 42, 11, 39, 32. 6. Постройте бинарное дерево для приведенных ниже букв, хранящихся в алфавитном порядке, если они вводились в следуюшем порядке: тп, а, г,1, д, о,1, Н, з, 1, и, 1, з, р, з. 10. Постройте бинарное дерево для приведенных ниже марок автомобилей, хра- нящихся в алфавитном порядке, если данные поступили в следующем порядке: Бансов, Крайслер, Шевроле, Додж, Мэркьюри, Нэш и Олдсмобил.
11. Постройте бинарное дерево высоты 4 для букв английского алфавита. !2. Задано дерево (рис. 15.21). а) Удалите а. б) Удалите /. в) Удалите гп. г) Удалите и. д) Удалите г. 13. Задано дерево (рис. 15.22). Рис. 15.22 638 ГЛАВА тз. Деревья а) Удалите а. б) Удалите е. в) Удалите г. г) Удалите гп. д) Удалите 1. 14. Напишите программу для алгоритма Вставка (элемент) в псевдокодах или на заданном языке. 15.
Напишите программу для алгоритма Поиск (элемент) в псевдокодах или на заданном языке. 16. Напишите программу для алгоритма Удаление (элемент) в псевдокодах или на заданном языке. 15.3. ВЗВЕШЕННЫЕ ДЕРЕВЬЯ В этом разделе рассматриваются две проблемы, имеющие одно и то же решение. В компьютере все буквы и другие символы хранятся в виде строк из единиц и нулей.
Например, если символы хранятся как АВС!1-символы, они состоят из строк длины 7 плюс восьмой символ, который используется для контроля четности. Пусть А — множество всех символов, которые необходимо сохранить. Всегда есть возможность сохранить А в виде строк некоторой фиксированной длины и, состоящих из единиц и нулей. Это дает существенное преимущество при "декодировании" строки обратно в символы из А. Первые и байтов (единиц и нулей в строке) образуют первый символ из А, вторые п байтов — второй символ и т.д. Однако, если данных достаточно много, всегда желательно провести их компактификацию, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
