İkili axtarış ağacı - qovşaqları, digər qovşaqlara iki keçidi, sağ və soldan ibarət strukturlaşdırılmış verilənlər bazası. Qovşaqlar sinifin verilənlərə malik obyektidir və NULL ağacın sonunu göstərən işarədir.
Ona çox vaxt xüsusi xassə olan BST deyilir: kökdən daha böyük qovşaqlar onun sağında, kiçikləri isə solunda yerləşir.
Ümumi nəzəriyyə və terminologiya
İkili axtarış ağacında kök istisna olmaqla hər bir qovşaq bir qovşaqdan digərinə yönəldilmiş kənar ilə bağlanır ki, bu da ana adlanır. Onların hər biri uşaq adlanan ixtiyari sayda qovşaqlara qoşula bilər. "Uşaqları" olmayan qovşaqlara yarpaqlar (xarici düyünlər) deyilir. Yarpaq olmayan elementlərə daxili deyilir. Eyni valideyni olan qovşaqlar bacı-qardaşdır. Ən yuxarı node kök adlanır. BST-də hər bir qovşaq üçün element təyin edin və onlar üçün xüsusi xassə təyin olunduğundan əmin olun.
Ağac terminologiyası:
- Düyün dərinliyi kökdən ona qədər müəyyən edilmiş kənarların sayıdır.
- Düyün hündürlüyü ondan ən dərin yarpağa qədər müəyyən edilmiş kənarların sayıdır.
- Ağacın hündürlüyü kökün hündürlüyünə görə müəyyən edilir.
- İkili axtarış ağacı xüsusi dizayndır, o, hündürlüyün və qovşaqların sayının ən yaxşı nisbətini təmin edir.
- Hündürlük h ən çox N qovşaq ilə O (log N).
Bunu kökdən başlayaraq hər səviyyədə qovşaqları saymaqla, onların ən çoxunu ehtiva etdiyini fərz etməklə asanlıqla sübut edə bilərsiniz: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Bunu h üçün həll etmək h=O (log n) verir.
Ağacın faydaları:
- Verilənlərin struktur əlaqələrini əks etdirin.
- İyerarxiyaları təmsil etmək üçün istifadə olunur.
- Effektiv quraşdırma və axtarışı təmin edin.
- Ağaclar çox çevik məlumatlardır və sizə minimum səylə alt ağacları köçürməyə imkan verir.
Axtarış metodu
Ümumiyyətlə, dəyərin BST-də olub-olmadığını müəyyən etmək üçün onun kökündə ikili axtarış ağacına başlayın və onun tələblərə cavab verib-vermədiyini müəyyənləşdirin:
- kökdə ol;
- kökün sol alt ağacında olun;
- kökün sağ alt ağacında.
Əgər heç bir əsas registr təmin edilmirsə, müvafiq alt ağacda rekursiv axtarış aparılır. Əslində iki əsas seçim var:
- Ağac boşdur - yalanı qaytarın.
- Dəyər kök nodedədir - doğrunu qaytarın.
Qeyd etmək lazımdır ki, işlənmiş sxemə malik ikili axtarış ağacı həmişə kökdən yarpağa gedən yolda axtarışa başlayır. Ən pis halda, yarpağa qədər gedir. Buna görə də, ən pis vaxt ağacın hündürlüyü olan kökdən yarpağa qədər ən uzun yolun uzunluğu ilə mütənasibdir. Ümumiyyətlə, bu, ağacda saxlanılan dəyərlərin sayından asılı olaraq axtarmaq üçün nə qədər vaxt lazım olduğunu bilməlisiniz.
Başqa sözlə, BST-də düyünlərin sayı ilə ağacın hündürlüyü arasında onun "formasından" asılı olaraq əlaqə var. Ən pis halda, qovşaqların yalnız bir uşağı var və balanslaşdırılmış ikili axtarış ağacı mahiyyətcə əlaqəli siyahıdır. Məsələn:
50
/
10
15
30
/
20
Bu ağacın 5 qovşağı var və hündürlüyü=5. 16-19 və 21-29 diapazonunda dəyərləri tapmaq kökdən yarpağa (20 dəyərini ehtiva edən qovşaq) aşağıdakı yolu tələb edəcək, yəni., qovşaqların sayına mütənasib vaxt tələb olunacaq. Ən yaxşı halda onların hamısının 2 uşağı var və yarpaqlar eyni dərinlikdə yerləşir.
Bu ikili axtarış ağacının 7 qovşağı var və hündürlüyü=3. Ümumiyyətlə, bu kimi ağacın (tam ağac) hündürlüyü təxminən log 2 (N) olacaq, burada N ağacdakı qovşaqların sayıdır. Log 2 (N) dəyəri sıfıra çatana qədər N-nin bölünə biləcəyi (2) sayıdır.
Xülasə: BST-də axtarış üçün lazım olan ən pis vaxt O (ağac hündürlüyü). Ən pis halda "xətti" ağac O(N)-dir, burada N ağacdakı qovşaqların sayıdır. Ən yaxşı halda, "tam" ağac O(log N)-dir.
BST ikili əlavə
Maraqlıdır, harada olmalıdıryeni node BST-də yerləşir, məntiqi başa düşmək lazımdır, o, istifadəçinin tapdığı yerdə yerləşdirilməlidir. Bundan əlavə, qaydaları yadda saxlamalısınız:
- Dublikatlara icazə verilmir, dublikat dəyər daxil etməyə cəhd istisna yaradacaq.
- İctimai daxiletmə metodu faktiki daxil etmək üçün köməkçi rekursiv "köməkçi" metodundan istifadə edir.
- Yeni dəyərdən ibarət qovşaq həmişə BST-də yarpaq kimi daxil edilir.
- İctimai daxiletmə metodu etibarsızlığı qaytarır, lakin köməkçi metod BSTnode qaytarır. O, bunu ona ötürülən node null olduğu halı idarə etmək üçün edir.
Ümumiyyətlə, köməkçi metod onu göstərir ki, orijinal ikili axtarış ağacı boşdursa, nəticə bir qovşağı olan ağacdır. Əks halda, nəticə arqument kimi ötürülən eyni node üçün göstərici olacaq.
İkili alqoritmdə silinmə
Gözlədiyiniz kimi, elementin silinməsi silinəcək dəyəri ehtiva edən qovşağın tapılmasını nəzərdə tutur. Bu kodda bir neçə şey var:
- BST köməkçi, həddən artıq yüklənmiş silmə metodundan istifadə edir. Əgər axtardığınız element ağacda deyilsə, o zaman köməkçi metod sonda n==null ilə çağırılacaq. Bu səhv hesab edilmir, ağac bu halda sadəcə dəyişmir. Silmə köməkçisi metodu dəyər qaytarır - yenilənmiş ağaca göstərici.
- Yarpaq çıxarıldıqda, ikili axtarış ağacından çıxarılması onun valideyninin müvafiq uşaq göstəricisini sıfıra, kökü isə sıfıra təyin edir.qovşaq kökdür və uşağı yoxdur.
- Qeyd edək ki, silmə çağırışı aşağıdakılardan biri olmalıdır: root=sil (kök, açar), n.setLeft (sil (n.getLeft (), açar)), n.setRight (sil (n. getRight(), açar)). Beləliklə, hər üç halda silmə metodunun sadəcə null qaytarması düzgündür.
- Silinəcək dəyəri ehtiva edən qovşağın axtarışı uğurla başa çatdıqda, üç seçim var: silinəcək qovşaq yarpaqdır (uşaqları yoxdur), silinəcək qovşaqda bir uşaq var, onun iki uşağı var. uşaqlar.
- Silinən node bir uşaq olduqda, siz sadəcə olaraq onu uşaqla əvəz edə bilərsiniz və göstəricini uşağa qaytara bilərsiniz.
- Silinəcək qovşağın sıfır və ya 1 uşağı varsa, silmə metodu kökdən həmin qovşaq üçün "yolu izləyəcək". Beləliklə, həm axtarış, həm də daxiletmə üçün ən pis vaxt ağacın hündürlüyünə mütənasibdir.
Silinəcək düyünün iki uşağı varsa, aşağıdakı addımlar atılır:
- Silinəcək qovşağı tapın, kökdən ona gedən yolu izləyin.
- Yarpağa gedən yolda davam edərək, sağ alt ağacda v-nin ən kiçik dəyərini tapın.
- Rekursiv olaraq v dəyərini silin, 2-ci addımda olduğu kimi eyni yolu izləyin.
- Beləliklə, ən pis halda, kökdən yarpağa gedən yol iki dəfə yerinə yetirilir.
Transferlərin sırası
Traversal ağacdakı bütün qovşaqları ziyarət edən prosesdir. C binar axtarış ağacı qeyri-xətti məlumat strukturu olduğundan, unikal keçid yoxdur. Məsələn, bəzən bir neçə keçid alqoritmiaşağıdakı iki növə qruplaşdırılıb:
- keçid dərinliyi;
- ilk keçid.
Yalnız bir növ eni kəsişmə var - səviyyəni keçmək. Bu keçid aşağı və sola, yuxarı və sağa səviyyəli qovşaqları ziyarət edir.
Üç müxtəlif növ dərinlik keçidi var:
- Ön Sifariş Keçilir - əvvəlcə valideynə, sonra isə sol və sağ uşağı ziyarət edin.
- Sifarişdən keçmək - sol uşağı, sonra valideyni və sağ uşağı ziyarət etmək.
- Sifarişdən Keçdi - sol uşağa, sonra sağ uşağa, sonra valideynə baş çəkmək.
İkili axtarış ağacının dörd keçidi üçün nümunə:
- Öncədən Sifariş - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- Sifarişlə - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- Sifarişdən Sonra - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- Səviyyə Sifarişi - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Şəkil qovşaqların ziyarət olunma ardıcıllığını göstərir. 1 rəqəmi xüsusi keçiddə ilk qovşaq, 7 isə son qovşaqdır.
Hər bir node üç dəfə ziyarət edildiyini fərz etsək, bu ümumi keçidlər tək alqoritm kimi təqdim edilə bilər. Euler turu ikili ağacın ətrafında gəzintidir, burada hər bir kənar istifadəçinin keçə bilmədiyi bir divar kimi qəbul edilir. Bu gedişdə hər bir node ya solda, ya aşağıda, ya da sağda ziyarət ediləcək. Soldakı qovşaqları ziyarət edən Euler turu, ön sözün yan keçməsinə səbəb olur. Aşağıdakı qovşaqlar ziyarət edildikdə, onlar ardıcıllıqla keçilir. Və sağdakı qovşaqlar ziyarət edildikdə - alınaddım-addım yan keçid.
Naviqasiya və Sazlama
Ağacda naviqasiyanı asanlaşdırmaq üçün əvvəlcə onların sol və ya sağ uşaq olduğunu yoxlayan funksiyalar yaradın. Bir qovşağın mövqeyini dəyişdirmək üçün əsas qovşaqda göstəriciyə asan giriş olmalıdır. Ağacın düzgün şəkildə həyata keçirilməsi çox çətindir, ona görə də ayıklama proseslərini bilmək və tətbiq etmək lazımdır. Tətbiqi olan ikili axtarış ağacında çox vaxt səyahət istiqamətini göstərməyən göstəricilər olur.
Bütün bunları anlamaq üçün ağacın düzgün olub-olmadığını yoxlayan və bir çox səhvləri tapmağa kömək edən funksiya istifadə olunur. Məsələn, ana qovşağın uşaq node olub olmadığını yoxlayır. assert(is_wellformed(root)) ilə bir çox səhvlər vaxtından əvvəl tutula bilər. Bu funksiya daxilində verilmiş bir neçə kəsilmə nöqtəsindən istifadə etməklə siz həmçinin hansı göstəricinin səhv olduğunu dəqiq müəyyən edə bilərsiniz.
Funksiya Konsolenausgabe
Bu funksiya bütün ağacı konsola göndərir və buna görə də çox faydalıdır. Ağac çıxış məqsədinin yerinə yetirilmə sırası belədir:
- Bunu etmək üçün əvvəlcə qovşaq vasitəsilə hansı məlumatın çıxacağını müəyyən etməlisiniz.
- Və siz həmçinin ağacın nə qədər geniş və hündür olduğunu bilməlisiniz ki, nə qədər yer buraxasınız.
- Aşağıdakı funksiyalar ağac və hər bir alt ağac üçün bu məlumatı hesablayır. Konsola yalnız sətir-sətir yaza bildiyiniz üçün ağacı sətir-sətir çap etməli olacaqsınız.
- İndi geri çəkilmək üçün başqa yola ehtiyacımız varbütün ağac, yalnız sətir-sətir deyil.
- Dump funksiyasının köməyi ilə siz ağacı oxuya və sürətə gəldikdə çıxış alqoritmini əhəmiyyətli dərəcədə təkmilləşdirə bilərsiniz.
Lakin bu funksiyanı böyük ağaclarda istifadə etmək çətin olacaq.
Konstruktoru və destruktoru kopyalayın
Ağac əhəmiyyətsiz verilənlər strukturu olmadığı üçün surət konstruktorunu, dağıdıcını və təyinat operatorunu həyata keçirmək daha yaxşıdır. Destruktoru rekursiv şəkildə həyata keçirmək asandır. Çox böyük ağaclar üçün "yığın daşması" nı idarə edə bilər. Bu vəziyyətdə, iterativ şəkildə tərtib edilir. İdeya, bütün yarpaqların ən kiçik dəyərini təmsil edən yarpağı çıxarmaqdır, ona görə də ağacın sol tərəfindədir. İlk yarpaqların kəsilməsi yeni yarpaqların yaranmasına səbəb olur və ağac nəhayət mövcudluğunu dayandırana qədər kiçilir.
Kopyalama konstruktoru rekursiv şəkildə də həyata keçirilə bilər, lakin istisna atıldıqda diqqətli olun. Əks təqdirdə, ağac tez bir zamanda çaşqın və səhvlərə meylli olur. Buna görə təkrarlanan versiyaya üstünlük verilir. İdeya, dağıdıcıda olduğu kimi köhnə ağacdan və yeni ağacdan keçmək, köhnə ağacda olan, lakin yeniləri olmayan bütün qovşaqları klonlaşdırmaqdır.
Bu üsulla binar axtarış ağacının tətbiqi həmişə sağlam vəziyyətdədir və hətta natamam vəziyyətdə də dağıdıcı tərəfindən silinə bilər. İstisna baş verərsə, sizə lazım olan tək şey dağıdıcıya yarı bitmiş ağacı silmək barədə göstəriş verməkdir. təyin operatoruKopyalama və Mübadilə ilə asanlıqla həyata keçirilə bilər.
İkili axtarış ağacı yaradılır
Optimal ikili axtarış ağacları düzgün idarə edildikdə inanılmaz dərəcədə səmərəlidir. İkili axtarış ağacları üçün bəzi qaydalar:
- Valideyn node ən çox 2 uşaq qovşağına malikdir.
- Sol uşaq qovşağı həmişə ana qovşaqdan kiçikdir.
- Etibarlı uşaq qovşağı həmişə ana qovşaqdan böyük və ya ona bərabərdir.
İkili axtarış ağacını yaratmaq üçün istifadə olunacaq massiv:
- Artılmamış qaydada yeddi dəyərdən ibarət əsas tam ədəd massivi.
- Massivdəki ilk dəyər 10-dur, ona görə də ağacın qurulmasında ilk addım burada göstərildiyi kimi 10 kök node yaratmaqdır.
- Bir sıra kök qovşaqları ilə bütün digər dəyərlər bu qovşağın uşaqları olacaq. Qaydalara istinad edərək, ağaca 7 əlavə etmək üçün atılacaq ilk addım onu kök node ilə müqayisə etməkdir.
- Əgər 7 dəyəri 10-dan azdırsa, o, sol alt qovşaq olacaq.
- Əgər 7 dəyəri 10-dan böyük və ya ona bərabərdirsə, sağa doğru hərəkət edəcək. 7-nin 10-dan kiçik olduğu bilindiyi üçün o, sol uşaq qovşağı kimi təyin edilmişdir.
- Hər element üçün rekursiv müqayisə aparın.
- Eyni nümunəyə uyğun olaraq massivdəki 14-cü dəyərlə eyni müqayisəni həyata keçirin.
- 14-ün düzgün uşaq olduğunu bilməklə 14 dəyərini kök node 10 ilə müqayisə edirik.
- Massivdə gəzərkən,20-yə gəlin.
- Massivi 10 ilə müqayisə etməklə başlayın, hansı daha böyükdür. Ona görə də sağa keçin və onu 14 ilə müqayisə edin, onun yaşı 14-dən yuxarıdır və sağda uşağı yoxdur.
- İndi 1 dəyəri var. Digər dəyərlərlə eyni nümunəyə uyğun olaraq, sola keçərək 7 ilə və nəhayət 7-ci qovşaqın 1 sol uşağı ilə müqayisə edərək, 1 ilə 10 arasında müqayisə edin.
- Əgər dəyər 5-dirsə, onu 10 ilə müqayisə edin. 5 10-dan kiçik olduğu üçün sola keçin və 7 ilə müqayisə edin.
- 5-in 7-dən kiçik olduğunu bilərək, ağacdan aşağıya doğru davam edin və 5-i 1 dəyərlə müqayisə edin.
- 1-in uşağı yoxdursa və 5-in 1-dən böyükdürsə, 5 1 node üçün etibarlı uşaqdır.
- Son olaraq 8 dəyərini ağaca daxil edin.
- 8 10-dan kiçik olduqda, onu sola köçürün və 7 ilə müqayisə edin, 8, 7-dən böyükdür, ona görə də onu sağa köçürün və ağacı tamamlayın, 8-i 7-nin düzgün uşağı edin.
Optimal ikili axtarış ağaclarının sadə zərifliyini əldə etmək və qiymətləndirmək. Proqramlaşdırmada bir çox mövzular kimi, ikili axtarış ağaclarının gücü də verilənləri kiçik, əlaqəli komponentlərə həll etmək qabiliyyətindən irəli gəlir. Bundan sonra siz tam verilənlər bazası ilə mütəşəkkil şəkildə işləyə bilərsiniz.
Potensial İkili Axtarış Problemləri
İkili axtarış ağacları əladır, lakin yadda saxlamaq üçün bir neçə xəbərdarlıq var. Onlar adətən yalnız balanslaşdırılmış olduqda təsirli olurlar. Balanslı bir ağac, içində olduğu bir ağacdırağacdakı hər hansı qovşağın alt ağaclarının hündürlükləri arasındakı fərq ən çoxu birdir. Qaydaları aydınlaşdırmağa kömək edə biləcək bir nümunəyə baxaq. Təsəvvür edək ki, massiv çeşidlənən kimi başlayır.
Bu ağacda ikili axtarış ağacı alqoritmini işlətməyə cəhd etsəniz, o, istədiyiniz dəyər tapılana qədər sadəcə massivdə təkrarlanan kimi işləyəcək. İkili axtarışın gücü arzuolunmaz dəyərləri tez bir zamanda filtrləmək qabiliyyətindədir. Ağac balanslaşdırılmış olmadıqda, o, balanslaşdırılmış ağac kimi eyni faydaları təmin etməyəcək.
İstifadəçinin ikili axtarış ağacı yaradarkən işlədiyi məlumatları yoxlamaq çox vacibdir. Siz balanslaşdırmaq üçün tam ədədlər üçün ikili axtarış ağacını tətbiq etməzdən əvvəl massivlərin təsadüfiləşdirilməsi kimi rutinləri birləşdirə bilərsiniz.
İkili axtarış hesablama nümunələri
Aşağıdakı ikili axtarış ağacına 25 daxil edilərsə, hansı ağacın nəticələnəcəyini müəyyən etməliyik:
10
/
/
5 15
/ /
/ /
2 12 20
Tərkibində hələ x olmayan T ağacına x-i daxil edərkən, x açarı həmişə yeni yarpaqda yerləşdirilir. Bununla əlaqədar olaraq, yeni ağac belə görünəcək:
10
/
/
5 15
/ /
/ /
2 12 20
25
Aşağıdakı ikili axtarış ağacına 7 əlavə etsəniz, hansı ağacı əldə edərdiniz?
10
/
/
5 15
/ /
/ /
2 12 20
Cavab:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
İkili axtarış ağacından istənilən obyekti saxlamaq üçün istifadə edilə bilər. Əlaqəli siyahı əvəzinə ikili axtarış ağacından istifadə etməyin üstünlüyü ondan ibarətdir ki, əgər ağac ağlabatan balanslaşdırılmışdırsa və "xətti" ağacdan daha çox "dolu" ağaca bənzəyirsə, daxiletmə, axtarış və bütün silmə əməliyyatları burada işləmək üçün həyata keçirilə bilər. O(log N) vaxtı.
