Введение в информационные системы. Брюхомицкий Ю.А. - 71 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

71
Рис. 5.20. Неоднородное дерево, отображающее график технического
обслуживания механизма
Дерево, в котором каждый узел имеет одинаковое число ветвей, назы-
вается сбалансированным. Сбалансированное n-уровневое дерево, в котором (n-
1)-й уровень заполнен полностью, называется симметричным.
Симметричное дерево обладает замечательным свойством: пути в дере-
ве от корня до любого места имеют
одинаковую длину и длина эта минимальна,
так как минимальна высота дерева. При поиске нужных записей по такому де-
реву потребуется меньшее число операций чтения и сравнения, чем при исполь-
зовании любого другого дерева.
Для характеристики степени приближения сбалансированного дерева к
симметричному используют понятие объема дерева:
N
Оn · L(n),
n=0
где N − количество уровней в дереве; L(n) − число узлов на n-м уровне.
В общем случае чем меньше объем дерева, тем оно ближе к симмет-
ричному. Симметричное сбалансированное дерево имеет минимальный объем.
При включении в симметричное дерево новых записей, оно перестраивается,
так как соответствующая ему исходная последовательность
должна быть вновь
упорядочена в соответствии со значением ключа новой записи. Эта процедура
требует дополнительных затрат машинного времени. Поэтому структуру сим-
метричного дерева удобно использовать в тех случаях, когда требуется частый
поиск в информационном массиве, но редки операции ведения.
Сбалансированное дерево, в котором каждый порождающий узел имеет
не более двух порожденных, называется двоичным или бинарным. Направления
от порождающего узла к порожденным в двоичном дереве могут быть левыми и
правыми. Все узлы, связанные с данным посредством левой привязки, образуют
левое поддерево (левую ветвь), а узлы, связанные с данным посредством правой
привязки
, образуют правое поддерево (правую ветвь).
Двоичные деревья наиболее удобны для обработки и хранения в ЭВМ.
Однако очень немногие отношения предметных областей могут быть непосред-
ственно представлены в виде двоичного дерева. Поэтому на практике сначала
Паспорт, инв. № механизма
Дата обслуживания
ФИО механика Тип неисправности

Страницы