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

Ybaxeuue acex yosoa bepeaa

RTH OHé]3I1IJHII BhIHOJIHIIéTCII HO ToMy we n]3HHuiiny, CTO H H]3o-

CMOTj3 Qe]3éBlI. B 3TOM cayuae ypo6HO HCHoas3OBllTb BOCXOQII HI4
o6xop pe]3éBlI.

void del all(node*& r)

if (!r) return; del all(r->left); del all(r->right); delete r;

133
r NULL;

6. 
   Hobcuem yeaoc
   

CTO Wé CH]3lIBéQJIHBO H Qcs nopcU TU Uricaa ysnoB B Qé]3éBé (HO

ncnoussyeTcll HriCxops nil o6XO,Q pe]3éBII).

void Nnodes(node* r, int& p)

if (r == NULL) return;

Nnodes(r->left, p); Nnodes(r->right, p);

Macro ysuoB COxpaHIIéTCs B apryMeHTé . OOTBéTcTByio inn eMy QaKTHUéCKnii apryMeHT @OuWéH 6hITh o6HyueH nepep BhI3OBOM QyHKuH pns nonyueHHll n]3iIBHJIhHOro pesynsT£tTil.

3. 
   7. Onpebexeuut 8blCOmul C]9€!86l
   

To we CIIMOé CH]3£tBéQJIHBO H Hps nopcU Té Uricna ypoBHé$J. Ho- CJIé 3I1Bé]3IIIéHHIl ]3I16oTsi QyHxuHH BhICOTII Qe]3éBII COX]3IIHRéTCR B QO]3MIIJIhHOM apryMeHTé h H B COOTBéTcTByio eM IlKTHUéCKOM I1]3-

ryMeHTé.

void Height(node* r, int p, int& h) if (r == NULL) return;

if (r->left == NULL && r->right == NULL) //
b OBe Ka Hi QO CTMV eHM e Te MM HaA bH O r O /3La
if (p > h) h p;
Height(r->left, p, h); Height(r->right, p, h);

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

3. 
   Сбаланснрованные деревья
   

Максимальный эффект использования двоичного дерева по- иска достигается, если оно сбалансировано — когда все узлы, кроме терминальных, имеют непустые и правый и левый сосед- ние узлы; все поддеревья, начинающиеся с одного и того же

]ЭОВНЯ, ИМЕЮТ ОДИНІІКОВ Ю ВЫСОТ .
Сбалансированное бинарное дерево — максимально широкое и низкое. Именно такими являются деревья, показанные на ри- сунках 10.2, 10.5, 10.7 и 10.8. Фактически все эти деревья, кроме 10.5, являются идеально сбалансированными.
Менее строгое, но практически более удобное определение сбалансированности дерева — дерево является сбалансированным, если для каждого узла исходящие ветви отличаются no высоте не более, чем на одни уровень.
Обратный случай — вырожденное дерево, — выродившееся в линейный односвязный список. Такое дерево получается, если заносимые в него данные упорядочены по возрастанию (рисунок 10.9) или по убыванию.
Вырожденные деревья также получили название лево- или право-ассоциативных или «лоз», а также являются частным случаем ориентированным деревьев.
Если данные случайны, то получается дерево, в той или иной степени приближающееся к сбалансированному (рисунки 10.6, 10.11).
Для двоичного идеально сбалансированного дерева с мак- симально возможным (для идеальной сбалансированности) чис- лом узлов существуют простые соотношения между этим числом узлов N н высотой дерева (т.е. числом уровней) h:

135
(10.1)

(10.2)

Состояние сбалансированности (хотя бы в менее строгом смысле) часто оказывается настолько важным для тех областей, в которых деревья применяются, что для достижения этого состоя- ния принимают специальные меры. Такими мерами являются ли- бо та или иная операция балансировки (принудительной) дерева, в том числе включающая в себя упомянутые операции поворо- тов, либо использование специальных видов деревьев, обеспечи- вающих балансировку при каждой операции добавления или уда- ления узла. Основными видами таких деревьев являются АВИ- дерево н красно-чёрное дерево.

1.