Двоичные деревья
Cтраница 2
 |
Пример регионального поиска иа ранее заданном файле. Часть ( Ь показывает узлы, фактически пройденные при поиске. [16] |
Анализ времени запроса для худшего случая намного более сложен. И не удивительно, что этот анализ был разработан Ли и Вонгом ( Lee, Wong ( 1977) ] значительно позже того, как были впервые предложены многомерные двоичные деревья. [17]
В главе 5 уже рассматривались деревья, тем не менее, полезно еще раз вспомнить терминологию. Связи могут указывать на другие двоичные деревья или на внешние ( external) узлы, которые не имеют связей. Узлы с двумя связями называются также внутренними ( internal) узлами. Для выполнения поиска каждый внутренний узел имеет также элемент со значением ключа, а связи с внешними узлами называются нулевыми ( null) связями. Значения ключей во внутренних узлах сравниваются в ключом поиска и управляют протеканием поиска. [18]
Если соответственно изменить прочие функции, то из примера 10.7 возникнет программа, понимающая выражения и держащая их в уме. С помощью процедуры выведи можно предпринять контрольную распечатку; совершенно аналогично можно построить функцию, которая рассчитывает значения выражений. Выражения, введенные в ЗУ как двоичные деревья, можно обрабатывать и иначе, в частности упрощать. [19]
Она достаточно развита, чтобы решать большинство практических задач. На ее основе всегда можно сконструировать структуры данных недостающих типов, например списки, двоичные деревья и многое другое. [20]
 |
Общие термины, используемые при описании деревьев. Диаграмма дерева имеет высоту 4 ( число уровней, момент 22 ( число узлов, вес 16 ( число листьев. [21] |
Имеется одна особая категория сбалансированных древовидных структур, в которой допускается. Такая структура называется двоичным деревом. На рис. 8.4 показано несбалансированное двоичное дерево. Очень немногие типы логических организаций данных непосредственно могут быть представлены как двоичные деревья. Родословная собаки, например, легко может быть представлена в виде двоичного дерева. [22]
В этой главе будут рассмотрены динамические структуры данных, размер которых, может увеличиваться или уменьшаться при исполнении программы. Стеки, играющие важную роль в компьютерах и операционных системах, допускают выполнение вставки и удаления только с одного конца стека - сверху. Очереди представляют собой линии ожидания; вставки производятся в конец ( иначе называемый хвостом) очереди, а удаление - в начале ( называемом еще головой) очереди. Двоичные деревья облегчают скоростной поиск и сортировку данных, эффективное устранение повторяющихся элементов данных, представление файловой структуры каталогов и компиляцию выражений в машинный язык. Каждая из этих структур данных имеет множество других интересных применений. [23]
Страницы: 1 2