3. Cho'qqini qo'shish algoritmi
Rivojlanish balansi ko'rsatkichi yuqoridagi chap va o'ng pastki daraxt balandligi o'rtasidagi farq sifatida talqin qilinadi va algoritm tasvirlangan TAVLTree turiga asoslanadi. To'g'ridan-to'g'ri kiritishda (varaq) nol balansi o'zlashtiriladi. Verteksni kiritish jarayoni uch qismdan iborat:
Yo'lni topish uchun o'tish, kalit qishloqda emasligiga ishonch hosil qilmagunimizcha.
Daraxtga yangi cho'qqilarni kiritish va natijada muvozanatlash ko'rsatkichlarini aniqlash.
Muvozanatning har bir cho'qqisini qidirish va tekshirish yo'li bo'ylab "chekinish". Agar kerak bo'lsa, muvozanat.
Daraxtning balandligi oshganligini yuboradigan bayroq o'zgaruvchisi parametrini kiritish orqali oddiy protsedura parametrlari ro'yxatini kengaytiramiz. Chap yorug'lik pastki daraxtiga tepani qo'shing
h l < h r: h l = h r ni tekislaydi. Hech narsa qilish kerak emas.
h l = h r: endi chap pastki daraxt bittaga katta bo'ladi, lekin hali muvozanatlash talab qilinmaydi.
h l > h r: endi h l - h r = 2, - balanslash kerak.
Har qanday holatda, chap pastki daraxtning muvozanatini aniqlash kerak. Agar bu cho'qqining chap pastki daraxti (Tree^.left^.left) o'ngdan (Tree^.left^.right) balandroq bo'lsa, u holda katta o'ngga aylantirish talab qilinadi, aks holda o'ngga burish kam bo'ladi. Shu kabi (simmetrik) mulohazalarni o'ng pastki daraxtga kiritish uchun taqdim etish mumkin. N. Wirth tomonidan taklif qilingan kiritish tartibi
TAPL protsedurasi. InsertNode (Var daraxt: TAVLTree; const akey: TKey; const ainfo: TInfo; Var bayrog'i: Boolean);
Var
Tugun 1 , tugun 2 : TAVLTree ;
boshlanishi
agar daraxt = nol bo'lsa
boshlanishi
Yangi(daraxt);
bayroq := true ;
ctree^do
boshlanishi
kalit:= kalit;
info := info ;
chap := null ;
to'g'ri := null ;
balans:= 0;
yakun ;
inc(AVL.FNodes); _ _ end else if tree ^ . tugmasi > akey, keyin esa boshlang
InsertNode(Tree
^ . chap, kalit, ma'lumot, bayroq);
bayroq bo'lsa
Case Tree ^. balans 1: daraxt boshlanishi ^. _
balans:= 0; bayroq:= noto'g'ri; yakun ; 0: Daraxt ^. balans: = - 1; - 1 : {Balans} boshlanishi
Node1 := Daraxt ^. chap;
agar tugun1 ^ . balans = - 1 keyin
{LL}
Boshlash
daraxt ^. chap:= Node1 ^. o'ng;
Tugun 1 ^. o'ng: = Daraxt;
Daraxt ^. balans:= 0;
daraxt:=tugun1;
oxiri
boshqa
{LR}
begin
Tugun2 := Tugun1 ^. o'ng;
Tugun 1 ^. o'ng: = Tugun2 ^. chap;
Tugun 2 ^. chap: = Node1;
Daraxt ^. chap:= Tugun 2 ^. o'ng;
Tugun 2 ^. o'ng:=daraxt;
agar Node2 ^ . balans = - 1 keyin daraxt ^ . balans : = 1 boshqa daraxt ^ . balans:= 0;
agar Node2 ^ . balans = 1, keyin Node1 ^. balans: = - 1 boshqa Node1 ^. balans:= 0;
Daraxt: = Tugun2 ;
yakun ;
Daraxt ^. balans:= 0;
bayroq:= noto'g'ri
yakun
yakun
yakun
Aks holda daraxt ^ . keyin < tugmachasini bosing
boshlanishi
InsertNode ( Tree ^ .o'ng , akey , ainfo , bayroq ); agar bayroq u holda Tree ^ . balans - _
1: boshlanish daraxti ^. balans:= 0; bayroq:= noto'g'ri; yakun ;
0: Daraxt ^. balans:= 1;
1: {balans}
Boshlash
Node1 := Daraxt ^. o'ng;
agar tugun1 ^ . balans = 1 keyin
{RR}
boshlanishi
Daraxt ^ .o'ng: = Node1 ^. chap;
Tugun 1 ^. chap : = Daraxt ;
Daraxt ^. balans:= 0;
Daraxt: = Node1;
oxiri
boshqa
{RL}
Begin
Tugun2 := Tugun1 ^. chap;
Tugun 1 ^. chap : = Node2 ^ .to'g'ri ;
Tugun 2 ^. o'ng: = Node1;
Daraxt ^. o'ng: = Tugun2 ^. chap;
Tugun 2 ^. chap : = Daraxt ;
agar Node2 ^ . balans = 1, keyin daraxt ^. balans: = - 1 boshqa daraxt ^. balans:= 0;
agar Node2 ^ . balans = - 1, keyin Node1 ^. balans: = 1 boshqa Node1 ^. balans:= 0;
Daraxt: = Node2;
yakun ;
Daraxt ^. balans:= 0;
bayroq:= noto'g'ri
yakun
yakun
yakun
yakun ;
|
