Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

поиска» не следует, что оно применяется только для поиска.
Отдельные типы деревьев применяются для решения специ- альных задач, например основные деревья на графах (каркас ы графов, Spanning Tree) нпн РАТRlСlА-деревья (Practical Algo- rithm То Retrieve Information Coded in Alphanumeric), исполь- зуемые для поиска данных на основе их поразрядного двоичного представления.
Несколько несвязанных между собой деревьев образуют структуру данных, которая называется «лес» (иногда её называют
«6op» ).

2. 
   Двоичные деревья поиска
   

Ещё раз дадим определение дерева как структуры данных. Дерево — динамическая нелинейная структура данных, каж-

дый элемент которой содержит собственно информацию (или ссылку на то место в памяти ЭВМ, где хранится информация) и ссылки на несколько (не менее двух) других таких же элементов. Для двоичного (бинарного) дерева таких ссылок две: на правый соседний и левый соседний элементы.
В общем случае данные, хранящиеся в дереве, не обязаны быть упорядочены каким-либо образом. Но часто требуется co- блюдение упорядоченности по некоторому принципу. Именно по такому принципу и отличаются «пирамиды» и « Ьереввл»:
— пирамида («кучп») — древовидная структура данных, в ко- торой значения всех узлов, размещённых на одном уровне, боль- ше (или меньше) значений узлов, размещённых на выше лежа- щем уровне (см. рисунок 10.1);



10 12 13 14

Рис. 10.1 Двоичная пирамида

дерево древовидная структура данных, в которой значе- ния всех узлов, размещённых правее некоторого узла, больше значений узлов, размещённых левее, причём это справедливо как для всего дерева, так и для любой его части (см. рисунок). Здесь необходимо сделать одно существенное уточнение: по указанно- му принципу строится дерево, получившее название «двоичного дерева поиска» (Binary Search Tree, BST), т.е. дерево, в котором очень удобно искать данные, причём с высокой эффективностью этого поиска. В дальнейшем под двоичными деревьями будут подразумеваться именно двоичные деревья поиска.



12

10 14

11 15

Рис. 10.2 — Двоичное дерево поиска

Как видно из сравнения рисунков 10.1 и 10.2, структура у пирамиды и дерева практически одинакова, отличаются они только характером размещения данных.

Также на этих рисунках видны и связи между элементами деревьев (узл‹zмп), похожие на связи между звеньями списка. Чем же отличается двоичное дерево от двусвязного списка? Иногда ничем, не только от двусвязного, но и от односвязного списка. Основное отличие — у списка соседними являются предшест- вующий и последующий элементы, и структура линейна; а у дво- ичного дерева поиска соседними являются элементы с меньшим и большим ключом, и структура, в общем случае ветвящаяся — в виде дерева, откуда она и получила свое название. Кроме того, любая часть дерева по своей структуре повторяет всё дерево в целом, т.е. дерево (любое, не только двоичное) это рекурсивная структура данных (фактически дерево можно считать фракталь- ной структурой).
114

Рис. 10.3 — Фрактальные деревья

Нужно помнить, что дерево — это только метод логической организации информации в памяти, а память — линейна.

В случае, если информация хранится в произвольном (и не- известном программисту) месте памяти, а ключ и информация разные понятия (иногда они могут и совпадать), структура узла дерева может быть представлена следующим образом:

key
’data
left	right

Рис. 10.4 — Обобщённая структура узла дерева

Этой структуре соответствует набор типов на языке Пac-

type
info = (* тип хранимых данных *); ptr = ’node;

115
node = record key: Integer;

left, right: ptr; data: ’info
end;

var
tree: ptr;

struct node

int key; //kMюЧ, MOKOTOpoMy TpOИTCP дe eBO float data; / OM ë5HLeĄäHHbe o6orOTИШâ пode *left, *right; //YKaзdTeЛHHdCoeqHнeyзлы

ДBOHЧHOë дe]3ëBO, o6pasOBilHHOë TiIKHMИ 3JIëMëHTiIMH, HOK£tЗiI-
HO HИWö.

0

7

0 0

ЙЛëMëHT Дë]3ëBII пoлyчил HIlЗBiIHHë t‹yзeл» (node). EДИHCTBëH- HЬIЙ HtlUtlJIЬHЬIЙ 3JIëMëHT (oTKyдa дepeBo ]3I13BИBIłëTCIl) HOpëH ö (root). ФparMeHT (UIłCTЬ) ne]3ëBIł — HOØQë]3ëBO HЛH 8ëM 8b. 3ëH , OT KOTO]ЭOГO He OTXOДЯT BëTBH — KOHëЧHЬIЙ HЛH mepминaльньıй yзeл,

116
иногда его называют лпсші›ж. Как видно на рисунках, узлы pac- полагаются по уровням. Количество уровней — высота дерева (иногда вместо высоты используют термин « глубина» ). Посколь- ку дерево рекурсивная структура данных, то любой его узел может считаться корнем какой-либо ветви, в том числе пустой.