Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

4) Ağacvari nizamlama (tree sort).

Şək. 5.1. 1,3,4,6,7,8,10,13,14 ədədlərini nizamlamaq üçün binar ağaclar
Əvvəlcə bir anlayışı daxil edək. Binar axtarış ağacı dedikdə elə ikili ağac başa düşülür ki, bunun düyünlərində ədədlərin yerləşdirilməsi qanunauyğunluğu belədir: hər dyündən sol alt ağacda yerləşən ədədlərin hər biri baxılan düyündəki ədəddən kiçikdir, bundan sağ alt ağacda yerləşən ədədlərin hər biri isə bundan ya böyükdür, ya da buna bərabərdir. Şəkil 5.1.-də belə ağacların qurulmasına aid iki nümunə təsvir edilib, bunların hər birində eyni ədədlərdən istifadə olunub. Əgər hər bir düyün üçün alt ağacların hündürlükləri fərqi birdən böyük deyisə, belə ağac balanslaşmış adlanır. Balanslaşmış ağacları bəzən bunları kəşf edən şəxslərin şərəfinə AVL-ağac adlandırırlar (Q.M.Adelson-Velskiy, E.M. Landis). Şəkil 5.1. а)-da balanslaşmış ağac, 5.1. b)-də balanslaşmamış ağac təsvir edilib. Şəkillərdən göründüyü kimi, ağacların “yarpaq”larından başlayaraq onun kökünə doğru konkatenasiya əməliyyatını yerinə yetirsək, ədədlərin artma sırasında nizamlanması alınar. Ağacvari nizamlamanı yerinə yetirmək üçün verilmiş ədədlər massivi əsasında əvvəlcə ağac modelini qurmalıyıq, sonra ağacın ətəyindən başlayaraq nizamlamanı yerinə yetirməliyik. Binar ağac rekursiv və ya qeyri-rekursiv qaydada qurula bilər. Əgər ağac balanslaşmış olarsa, nizamlama üçün istifadə olunan əməliyyatların sayı O(n log₂ n) düsturu ilə qiymətləndirilir, əksinə ağac maksimum qeyri-balanslaşmış olarsa, onda nizamlama üçün istifadə olunan əməliyyatların sayı O( n²) düsturu ilə qiymətttləndirilir.

5.2. Rekursiv nizamlama üsulları

1) Sürətli nizamlama üsulu (Xoar üsulu). Bu üsul rekursiv hesablamalara əsaslanır. Üsulun mahiyyəti belədir: biz əvvəlcə verilmiş ardıcıllığının birinci elementini, yəni x₁-i götürüb bunu yeni siyahıya yazırıq, bu siyahını S ilə işarə edək. x₁-dən sonrakı elementləri bir-bir oxuyub x₁ ilə müqayisə edirik: əgər element bundan kiçikdirsə, onu x₁-dən sol tərəfə, böyükdürsə, sağ tərəfə yazırıq. Soldakı siyahını S₁, sağdakını S₂ ilə işarə edək. Bu proseduru S₁-ə, sonra S₂-yə tətbiq edirik. Nəhayət, proses o məqama qədər davam edir ki, qurulan siyahıların hər biri yalnız bir elementdən ibarətdir, bundan sonra siyahıların aşağıdan yuxarı birləşdirilməsi (konkatenasiya) əməliyyatı yerinə yetirilir və nəticədə nizamlanmış siyahı alınır. Konkatenasiya əməliyyatının mühüm cəhətlərindən biri bundan ibarətdir ki, bu əməliyyat zamanı birləşdirilən siyahıların elementləri bir-biri ilə müqayisə olunmur, bu səbəbdən birləşdirmə əməliyyatı sürətlə yerinə yetirilir.
Misal: 10,18,5,20,4,16,12,8,19,6,15,14,9 ardıcıllığını sürətli nizamlama üsulu ilə nizamlayaq.
5 ,4,8,6,9, 10, 18,20,16,12,19,15,14

4 ,5, 8,6,9 16,12,15,14, 18, 20,19

6, 8, 9 12,15,14, 16, Ø, 19,20, Ø,


Ø, 12, 15,14

14,15, Ø

Nəticədə binar ağac qurulur. Qurulan ağac əsasında ardıcıllıqların aşağıdan yuxarıya konkatenasiyası əməliyyatını yerinə yetirək:
1) S₁₃ U15 US₁₄ = 14,15;
2) S₁₁U12 U14,15=12, 14,15;
3) 12, 14,15 U16 U S₈= 12, 14,15,16;
4) S₉ U 20 U S₁₀ = 19,20;
5) 12, 14,15,16 U 18U 19,20=12, 14,15,16 , 18,19,20;
6) S₅U8 US₆=6,8,9;
7) S₁U5 U 6,8,9=4,5,6,8,9;
8) 4,5,6,8,9 U10U 12, 14,15,16,18,19,20=4,5,6,8,9,10,12, 14,15,16 , 18,19,20;
Yuxarıdakı hesablamalarda U və Ø işarələri müvafiq surətdə konkatenasiya əməliyyatını və boş çoxluğu göstərir. Sürətli nizamlama alqoritminin prosedurunu SN(i,j) ilə işarə edək.
SN(1,n) proseduru:
l:=1, r:=n;
l r olarsa yerinə yetir:
m:=l qəbul et və (a_l, a_l+1,...,a_r) siyahısını S₁ və S₂
hissələrinə böl; S₁=( a_l, a_l+1,...,a_j ) və S₂=(a_j+1,...,a_r), burada S₁= { a_i: a_i a_l, i l}, S₂={ a_i: a_i a_l };
SN(1,j), a_m və SN(j+1, r) hissələrini konkatenasiya et;
Prosedurun sonu.