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

Области применения деревьев: для хранения информации, как таковой; в процедурах поиска и сортировки; для описания хранения файлов на дисковых носителях; при построении эффек- тивных кодов для сжатия информации (коды Шеннона—Фано и Хаффмена).
Преимущество двоичных деревьев поиска: в случае, если дерево отсортировано (а это дерево именно такое), то операция поиска выполняется быстро, с эффективностью, близкой к эф- фективности двоичного поиска.

2. 
   Операции с деревьями
   

Для деревьев имеются те же основные операции, что и для списков — добавление элемента, удаление, прохождение (про- смотр) и поиск элементов. Кроме них можно использовать опера- ции принудительной балансировки, подсчёта числа узлов в дере- ве, измерения высоты дерева, поиска ближайшего общего корня (ближайшего общего предка Nearest Common Ancestor (пса)) для двух элементов (в многопутевых деревьях — для более чем двух элементов). При балансировке деревьев используются опе- рации поворотов ( вращений), простых и двойных, левых и пра-

ВЫХ.
Поскольку дерево рекурсивная структура данных, то наи- более эффективными при работе с деревьями оказываются рекур- сивные процедуры. Хотя возможно применение и нерекурсивных (итеративных) процедур. Рассмотрим разные варианты построе- ния этих процедур.

1. 
   Добавление узла в дерево
   

Рассмотрим принцип построения двоичного дерева поиска при занесении в него информации. Пусть последовательно вво- дятся записи с ключами 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86, 82.

117

1. 
   70 — корень (первый узел);
   
2. 
   60 70, следовательно новый узел будет расположен сле- ва от 70;
   
3. 
   85 70, следовательно новый узел будет расположен справа от 70;
   
4. 
   87 70, следовательно 87 будет находиться в правой вет- ви; 87 > 85, следовательно 87 будет расположен справа от 85. И т. д. (рисунок 10.6).
   

70
пil	пil

70
	nil

2. 70





4. 70

60
70

60 85

45 82 87

30 86

20 88

Рис. 10.6 — Процесс построения двоичного дерева поиска

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

BXOQsi+ias sanncs 6ypeT ]3l13Méi1(éHI1 CJIéBI1 HJIH CH]3I1BI1 OT HéFO H
CTlIHéT HOBhIM Té]3MHHIIJII›HsIM ysnoM.
PeKypcriBHIIII npouepypa po6I1BJIéHiis ysua B pepeBo HH R3hIKé
IlCKdJlh.

procedure addnode r(r, prev: ptr; newkey: in— teger; newdata: info);

begin
if r = nil then begin
new(r);
r’.left := nil; r’.right := nil; r’.key := newkey; r’.data := newdata; if tree = nil then
tree := r; (* HepemH ysex *) else
begin
if newkey
then
prev’.left := r
else
prev’.right := r
end;
exit
end;
if newkey < r’.key then addnode r(r’.left,r,newkey)
else
addnode_r(r’.right, r,newkey)
end;

Hpouepypa po6i1BJIIIéT HH$O]3M£tIJHIO B @BOHUHOé Qé]3éBO, OT- cneWHBas yKas£tTéJlri Ha ysnsl H BhI6H]3iIs JIéBhIé HJIH H]3IIBhIé BéTBH, B 3IIBHCHMOGTH OT Khiona, HOKI1 He 6ypeT HH QéHO GOOTBéTcTByio tee M CTO B H ]3iI]3XHH Q ]3 B t.

ApryMeHThI H]3ouenypsI:

• 
  yxasiITéJII› HH Ko]3éHI› Qé]3éBI1 HJIH BéTBH, B KOTO]3OM HIIJéTCII
  

MéCTO QJIII HOBoro ysna;

• 
  yKastlTéJlh Ha npeasIpy Hii ysen;
  

119

• 
  СОХ]Э£tНЯёМЬІё ,Q£tHHbIë илН yKaзtlTëЛЬ Htl НИХ.
  

П]ЭН Пё]ЭВОМ ВЬІЗОВё ВТО]Эой apгyMeHT МОЖёТ бЬІТЬ ]ЭtlBeH п i 1.
tlКТИЧёСКИ ЭТОТ П]Эouecc cOpTHpyeT КЛЮч, прежде ЧёМ Qo6a- ВиТь узел В nepeBo. ЭТо BapHaHT алгорНТМІl СО]ЗТН]ЭОВКН MëTO,QOM H]3CIGTbIX BCTIIBOK. При поGТ]ЭОёНИИ HOBOFo пе]ЗёВІ1 НлН обслужгіВІl- Нии уже упорядоЧёННОГо де]ЭёВlІ ]ЭёКОМеНдуеТсЯ Qo6tlBЛЯTЬ HOBЬIë узльІ HMëHHO TIlKOй проііедурой.
PllcGMoTpeHHaя процедура используеТ paHee опрерёЈlёННЬІЙ
yKaзlITëJIЬ НІ1 ,Qe]3ëBo L г ее, KOTOpoMy НеобХО,QИМО приСВОИТЬ ЗНІІ— UëHHë Гli 1 перед пё]ЗВЬІМ ВЫЗОВОМ ЭТОй проиепурьІ (НоскольКу ОНО Н)ЗОВё]ЗЯёТGІІ В СТ]ЭОКё і f L г ее = п i 1 . . .). П]ЭИВё@ М
Н]ЗНме]З IlHIlJIoгHЧHOй QуНкцИИ НІ1 R3bIKë би++, у коТО]ЗСІЄ TI1KO$J же yKaзllTëJlh ЯВЛRёТСя apryMeHTOM (ЭТО HO3BOJIflëT H36ëWIITb HCHOJIh- ЗОВ£tННЯ FJIo6dJIbHbIX cTpyKTyp aaHHЬIX).

void add node(node*& tree, node*& r, node*& prev, node& buf)

if (r == NULL)

r = new node;

r->left = NULL;
r->right = NULL;
r->key = buf.key;
r->data = buf. data;
if (tree != r)
if (buf.key < prev->key) prev->left = r;
else
prev->right = r;
return;

if (buf.key < r->key)

add node(tree, r->left, r, buf); else
add node(tree, r->right, r, buf);

120
Аргументы этой функции:

L ree указатель на всё дерево;
г — указатель на некоторый текущий узел;
prev — указатель на узел, «родительский» для г;
lou f буферная структура данных типа пode, содержащая вводимые данные.
Перед первым вызовом указатель L ree должен быть обну— лён, а сам вызов может быть следующим:

tree = NULL; пode buf;

but . k ey =. . . // Ввод данных в буферную область памяти

be f . data

add пode(tree, tree, tree, buf);

2.