Ikkilik qidiruv daraxti - oʻng va chapda tugunlar, boshqa tugunlarga ikkita havolani oʻz ichiga olgan tuzilgan maʼlumotlar bazasi. Tugunlar sinfning ma'lumotlarga ega ob'ekti va NULL - daraxtning oxirini belgilovchi belgi.
Koʻpincha maxsus xususiyatga ega boʻlgan BST deb ataladi: ildizdan kattaroq tugunlar uning oʻng tomonida, kichikroqlari esa chap tomonda joylashgan.
Umumiy nazariya va terminologiya
Ikkilik qidiruv daraxtida ildizdan tashqari har bir tugun bir tugundan ikkinchisiga yoʻn altirilgan chekka orqali ulanadi, bu esa ota-ona deb ataladi. Ularning har biri bolalar deb ataladigan ixtiyoriy sonli tugunlarga ulanishi mumkin. "Bolalar" bo'lmagan tugunlar barglar (tashqi tugunlar) deb ataladi. Barg bo'lmagan elementlar ichki deyiladi. Xuddi shu ota-onaga ega tugunlar birodarlardir. Eng yuqori tugun ildiz deb ataladi. BST da har bir tugunga element tayinlang va ular uchun maxsus xususiyat oʻrnatilganligiga ishonch hosil qiling.
Daraxt terminologiyasi:
- Tugun chuqurligi - ildizdan unga qadar aniqlangan qirralarning soni.
- Tugun balandligi - undan chuqur barggacha aniqlangan qirralarning soni.
- Daraxtning balandligi ildizning balandligi bilan belgilanadi.
- Ikkilik qidiruv daraxti maxsus dizayn boʻlib, u balandlik va tugunlar sonining eng yaxshi nisbatini taʼminlaydi.
- Balandligi h, koʻpi bilan N tugunli O (log N).
Buni har bir darajadagi tugunlarni ildizdan boshlab sanash orqali osonlik bilan isbotlashingiz mumkin, u ularning eng koʻp sonini oʻz ichiga oladi: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Buni h uchun yechish, h=O (log n) ni hosil qiladi.
Yog'ochning afzalliklari:
- Ma'lumotlarning strukturaviy aloqalarini aks ettiring.
- Ierarxiyalarni ifodalash uchun ishlatiladi.
- Samarali oʻrnatish va qidirishni taʼminlang.
- Daraxtlar juda moslashuvchan ma'lumotlar bo'lib, kichik kuch bilan pastki daraxtlarni ko'chirishga imkon beradi.
Qidiruv usuli
Umuman olganda, qiymat BSTda yoki yoʻqligini aniqlash uchun uning ildizida ikkilik qidiruv daraxtini boshlang va uning talablarga javob berishini aniqlang:
- ildizda bo'ling;
- ildizning chap pastki daraxtida bo'ling;
- ildizning oʻng pastki daraxtida.
Agar hech qanday tayanch registr qoniqtirilmasa, tegishli pastki daraxtda rekursiv qidiruv amalga oshiriladi. Aslida ikkita asosiy variant mavjud:
- Daraxt bo'sh - "false"ni qaytaring.
- Qiymat ildiz tugunida - rostni qaytaring.
Shuni ta'kidlash kerakki, ishlab chiqilgan sxemaga ega ikkilik qidiruv daraxti har doim ildizdan barggacha bo'lgan yo'l bo'ylab qidirishni boshlaydi. Eng yomon holatda, u barggacha boradi. Shuning uchun, eng yomon vaqt, daraxtning balandligi bo'lgan ildizdan barggacha bo'lgan eng uzun yo'lning uzunligi bilan mutanosibdir. Umuman olganda, daraxtda saqlangan qiymatlar soniga qarab qidirish uchun qancha vaqt ketishini bilishingiz kerak.
Boshqacha aytganda, BSTdagi tugunlar soni va daraxt balandligi oʻrtasida uning “shakli”ga qarab bogʻliqlik mavjud. Eng yomon holatda, tugunlarda faqat bitta bola bor va muvozanatli ikkilik qidiruv daraxti asosan bog'langan ro'yxatdir. Masalan:
50
/
10
15
30
/
20
Bu daraxtda 5 ta tugun bor va balandligi=5. 16-19 va 21-29 oralig'idagi qiymatlarni topish uchun ildizdan bargga (20 qiymatini o'z ichiga olgan tugun) quyidagi yo'l kerak bo'ladi, ya'ni., tugunlar soniga proportsional vaqt kerak bo'ladi. Eng yaxshi holatda ularning barchasida 2 ta farzand bor va barglari bir xil chuqurlikda joylashgan.
Ushbu ikkilik qidiruv daraxti 7 ta tugunga ega va balandligi=3. Umuman olganda, bunday daraxt (toʻliq daraxt) taxminan log 2 (N) balandlikka ega boʻladi, bu erda N – daraxtdagi tugunlar soni. Jurnal 2 (N) qiymati nolga yetguncha N ni necha marta (2) boʻlish mumkinligidir.
Xulosa: BSTda qidirish uchun zarur boʻlgan eng yomon vaqt O (daraxt balandligi). Eng yomon holatda "chiziqli" daraxt O(N), bu erda N - daraxtdagi tugunlar soni. Eng yaxshi holatda, “toʻliq” daraxt O(log N).
BST ikkilik insert
Qaerda boʻlishimga hayronmanyangi tugun BSTda joylashgan, siz mantiqni tushunishingiz kerak, u foydalanuvchi topadigan joyga joylashtirilishi kerak. Bundan tashqari, siz qoidalarni yodda tutishingiz kerak:
- Dublikatlarga ruxsat berilmaydi, takroriy qiymat kiritishga urinish istisnoga olib keladi.
- Ommaviy kiritish usuli haqiqatda kiritish uchun yordamchi rekursiv "yordamchi" usulidan foydalanadi.
- Yangi qiymatga ega tugun har doim BSTga barg sifatida kiritiladi.
- Ommaviy qo'shish usuli bekor qiladi, ammo yordamchi usul BSTnodeni qaytaradi. U buni oʻziga oʻtgan tugun null boʻlgan holatlarni boshqarish uchun qiladi.
Umuman olganda, yordamchi usul shuni ko'rsatadiki, agar dastlabki ikkilik qidiruv daraxti bo'sh bo'lsa, natija bitta tugunli daraxt bo'ladi. Aks holda, natija argument sifatida uzatilgan bir xil tugunga ko‘rsatgich bo‘ladi.
Binar algoritmda oʻchirish
Siz kutganingizdek, elementni oʻchirish oʻchiriladigan qiymatni oʻz ichiga olgan tugunni topishni oʻz ichiga oladi. Bu kodda bir nechta narsa bor:
- BST yordamchi, ortiqcha yuklangan oʻchirish usulidan foydalanadi. Agar siz izlayotgan element daraxtda bo'lmasa, yordamchi usul oxir-oqibat n==null bilan chaqiriladi. Bu xato hisoblanmaydi, bu holda daraxt oddiygina o'zgarmaydi. Yo'q qilish yordamchi usuli qiymatni qaytaradi - yangilangan daraxtga ko'rsatgich.
- Yaproq olib tashlanganda, ikkilik qidiruv daraxtidan olib tashlash uning ota-onasining mos keladigan pastki koʻrsatkichini nullga, agar olib tashlangan boʻlsa, ildizni nullga oʻrnatadi.tugun ildiz boʻlib, uning farzandlari yoʻq.
- Oʻchirish chaqiruvi quyidagilardan biri boʻlishi kerakligini unutmang: root=oʻchirish (root, kalit), n.setLeft (oʻchirish (n.getLeft (), kalit)), n.setRight (oʻchirish(n. getRight(), kalit)). Shunday qilib, uchta holatda ham o'chirish usuli shunchaki null qiymatini qaytarishi to'g'ri.
- Oʻchiriladigan qiymatni oʻz ichiga olgan tugunni izlash muvaffaqiyatli boʻlganda, uchta variant mavjud: oʻchiriladigan tugun barg (bolalari yoʻq), oʻchiriladigan tugunning bitta bolasi, ikkitasi bor. bolalar.
- Oʻchirilayotgan tugun bitta bolaga ega boʻlsa, bolaga koʻrsatgichni qaytargan holda uni bolaga almashtirishingiz mumkin.
- Agar oʻchiriladigan tugun nol yoki 1 ta bolaga ega boʻlsa, oʻchirish usuli ildizdan oʻsha tugungacha boʻlgan “yoʻldan boradi”. Demak, qidirish va kiritish uchun eng yomon vaqt daraxt balandligiga mutanosib.
Agar olib tashlanadigan tugunning ikkita bolasi boʻlsa, quyidagi amallar bajariladi:
- Oʻchiriladigan tugunni ildizdan unga boradigan yoʻl boʻylab toping.
- V ning eng kichik qiymatini oʻng pastki daraxtda toping, barg boʻylab davom eting.
- V qiymatini rekursiv ravishda olib tashlang, 2-qadamdagi kabi yoʻldan boring.
- Shunday qilib, eng yomon holatda, ildizdan barggacha boʻlgan yoʻl ikki marta bajariladi.
O'tish tartibi
Traversal - bu daraxtdagi barcha tugunlarga tashrif buyuradigan jarayon. C ikkilik qidiruv daraxti chiziqli bo'lmagan ma'lumotlar tuzilmasi bo'lganligi sababli, noyob o'tish yo'q. Masalan, ba'zan bir nechta o'tish algoritmlariquyidagi ikki turga guruhlangan:
- oʻtish chuqurligi;
- birinchi oʻtish.
Enlik kesishishning faqat bitta turi mavjud - darajani chetlab o'tish. Bu oʻtish orqali pastga va chapga, yuqoriga va oʻngga tekislikdagi tugunlarga tashrif buyuriladi.
Uch xil turdagi chuqurlikdagi kesishmalar mavjud:
- Oldindan buyurtma berish - avval ota-onaga, keyin chap va oʻng farzandga tashrif buyuring.
- Tartibga oʻtish - chap bolaga, keyin ota-onaga va oʻng farzandga tashrif buyurish.
- PostOrderdan oʻtgan - chap bolaga, keyin oʻngga, keyin ota-onaga tashrif buyurish.
Ikkilik qidiruv daraxtining toʻrtta oʻtishiga misol:
- Oldindan buyurtma - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- Buyurtmadan keyin - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Rasmda tugunlarga tashrif buyurish tartibi koʻrsatilgan. 1 raqami ma'lum bir o'tishdagi birinchi tugun, 7 esa oxirgi tugundir.
Bu umumiy oʻtishlarni bitta algoritm sifatida koʻrsatish mumkin, agar har bir tugunga uch marta tashrif buyurilgan boʻlsa. Eyler sayohati ikkilik daraxt atrofida sayr qilish bo'lib, unda har bir chekka foydalanuvchi kesib o'tolmaydigan devor sifatida qaraladi. Ushbu yurishda har bir tugunga chapda, pastda yoki o'ngda tashrif buyuriladi. Chapdagi tugunlarga tashrif buyuradigan Eyler turi predlogni chetlab o'tishga olib keladi. Quyidagi tugunlarga tashrif buyurilganda, ular tartibda o'tadi. Va o'ngdagi tugunlarga tashrif buyurilganda - olingbosqichma-bosqich chetlab o'tish.
Navigatsiya va nosozliklarni tuzatish
Daraxt boʻylab harakat qilishni osonlashtirish uchun avval ular chap yoki oʻng bola ekanligini tekshiradigan funksiyalarni yarating. Tugun o'rnini o'zgartirish uchun asosiy tugundagi ko'rsatgichga oson kirish imkoniyati bo'lishi kerak. Daraxtni to'g'ri amalga oshirish juda qiyin, shuning uchun siz disk raskadrovka jarayonlarini bilishingiz va qo'llashingiz kerak. Amalga oshirishga ega ikkilik qidiruv daraxtida koʻpincha sayohat yoʻnalishini koʻrsatmaydigan koʻrsatkichlar mavjud.
Bularning barchasini aniqlash uchun daraxtning toʻgʻri yoki yoʻqligini tekshiradigan va koʻplab xatolarni topishga yordam beruvchi funksiyadan foydalaniladi. Misol uchun, u ota-ona tugunining pastki tugun ekanligini tekshiradi. assert(is_wellformed(root)) bilan ko'p xatolarni muddatidan oldin aniqlash mumkin. Bu funksiya doirasidagi bir nechta berilgan toʻxtash nuqtalaridan foydalanib, qaysi koʻrsatgich notoʻgʻri ekanligini ham aniqlashingiz mumkin.
Funktsiya Konsolenausgabe
Bu funksiya butun daraxtni konsolga oʻtkazadi va shuning uchun juda foydali. Daraxt chiqishi maqsadini bajarish tartibi:
- Buni amalga oshirish uchun avval tugun orqali qanday ma'lumotlar chiqishini aniqlashingiz kerak.
- Shuningdek, qancha joy qoldirish kerakligini hisobga olish uchun daraxtning kengligi va balandligini ham bilishingiz kerak.
- Quyidagi funktsiyalar daraxt va har bir pastki daraxt uchun bu ma'lumotni hisoblab chiqadi. Konsolga faqat satr-satr yozishingiz mumkinligi sababli, daraxtni satr-satr chop etishingiz kerak bo'ladi.
- Endi pulni qaytarib olishning boshqa usuli kerakbutun daraxt, faqat satr satr emas.
- Dump funksiyasi yordamida siz daraxtni oʻqib chiqishingiz va tezlik boʻyicha chiqish algoritmini sezilarli darajada yaxshilashingiz mumkin.
Biroq, bu funksiyadan katta daraxtlarda foydalanish qiyin boʻladi.
Konstruktor va destruktorni nusxalash
Daraxt arzimas ma'lumotlar strukturasi bo'lmagani uchun nusxa ko'chirish konstruktori, destruktor va tayinlash operatorini amalga oshirish yaxshiroqdir. Destruktorni rekursiv tarzda amalga oshirish oson. Juda katta daraxtlar uchun u "uyning to'lib ketishi" bilan shug'ullanishi mumkin. Bunday holda, u iterativ tarzda shakllantiriladi. G'oya barcha barglarning eng kichik qiymatini ifodalovchi bargni olib tashlashdir, shuning uchun u daraxtning chap tomonida joylashgan. Birinchi barglar kesilsa, yangi barglar paydo bo'ladi va daraxt butunlay yo'qolguncha qisqaradi.
Nusxalash konstruktori rekursiv tarzda ham amalga oshirilishi mumkin, ammo istisno qilingan taqdirda ehtiyot bo'ling. Aks holda, daraxt tezda chalkash va xatoga moyil bo'ladi. Shuning uchun iterativ versiyaga afzallik beriladi. Bu g‘oya, xuddi destruktorda bo‘lgani kabi, eski daraxt va yangi daraxtdan o‘tib, eski daraxtdagi barcha tugunlarni klonlash, lekin yangilarini emas.
Ushbu usul yordamida ikkilik qidiruv daraxtini amalga oshirish har doim sog'lom holatda bo'ladi va hatto to'liq bo'lmagan holatda ham destruktor tomonidan olib tashlanishi mumkin. Agar istisno ro'y bersa, siz qilishingiz kerak bo'lgan yagona narsa destruktorga yarim tayyor daraxtni o'chirishni buyurishdir. tayinlash operatoriNusxalash va almashtirish yordamida osongina amalga oshirilishi mumkin.
Ikkilik qidiruv daraxti yaratilmoqda
Toʻgʻri boshqarilsa, optimal ikkilik qidiruv daraxtlari nihoyatda samarali boʻladi. Ikkilik qidiruv daraxtlari uchun ba'zi qoidalar:
- Ota tugunda koʻpi bilan 2 ta tugun mavjud.
- Chap tugun har doim asosiy tugundan kichik.
- Yaroqli yordamchi tugun har doim asosiy tugundan katta yoki unga teng.
Ikkilik qidiruv daraxtini yaratish uchun foydalaniladigan massiv:
- Saralanmagan tartibda ettita qiymatdan iborat asosiy butun son massivi.
- Masivdagi birinchi qiymat 10 ga teng, shuning uchun daraxtni yaratishda birinchi qadam bu yerda koʻrsatilganidek, 10 ta ildiz tugunini yaratishdir.
- Ildiz tugunlari toʻplami bilan boshqa barcha qiymatlar ushbu tugunning bolalari boʻladi. Qoidalarga murojaat qilib, daraxtga 7 qo‘shish uchun birinchi qadam uni ildiz tuguniga solishtirishdir.
- Agar 7 qiymati 10 dan kichik boʻlsa, u chap tugunga aylanadi.
- Agar 7 qiymati 10 dan katta yoki unga teng boʻlsa, u oʻngga siljiydi. 7 soni 10 dan kichik ekanligi maʼlum boʻlgani uchun u chap tugun sifatida belgilangan.
- Har bir element uchun rekursiv taqqoslash.
- Bir xil sxema boʻyicha massivdagi 14-qiymat bilan bir xil taqqoslashni bajaring.
- 14-qiymatni 10-tugun bilan solishtirish, 14-toʻgʻri bola ekanligini bilish.
- Masiv boʻylab yurish,20 ga keling.
- Qaysi kattaroq boʻlsa, massivni 10 bilan solishtirishdan boshlang. Shuning uchun o‘ngga siljiting va uni 14 yoshga solishtiring, u 14 yoshdan oshgan va o‘ng tomonda farzandi yo‘q.
- Endi 1 qiymati mavjud. Boshqa qiymatlar bilan bir xil sxema boʻyicha 1 ni 10 ga solishtiring, chapga siljiting va 7 ni va nihoyat 7-tugunning 1 chap bolasini solishtiring.
- Agar qiymat 5 boʻlsa, uni 10 bilan solishtiring. 5 10 dan kichik boʻlgani uchun chapga oʻtkazing va uni 7 bilan solishtiring.
- 5 7 dan kichik ekanligini bilib, daraxt boʻylab pastga qarab davom eting va 5 ni 1 qiymat bilan solishtiring.
- Agar 1 ta farzand boʻlmasa va 5 ta 1 dan katta boʻlsa, 5 ta 1 ta tugunning yaroqli farzandi hisoblanadi.
- Nihoyat daraxtga 8 qiymatini kiriting.
- 8 10 dan kichik bo'lsa, uni chapga siljiting va uni 7 bilan solishtiring, 8 7 dan katta, shuning uchun uni o'ngga suring va daraxtni yakunlang, 8 ni 7 ning to'g'ri bolasi qiling.
Optimal ikkilik qidiruv daraxtlarining oddiy nafisligini olish va baholash. Dasturlashning ko'plab mavzulari singari, ikkilik qidiruv daraxtlarining kuchi ularning ma'lumotlarni kichik, o'zaro bog'liq komponentlarga ajratish qobiliyatidan kelib chiqadi. Endi siz toʻliq maʼlumotlar toʻplami bilan tartibli tarzda ishlashingiz mumkin.
Potentsial ikkilik qidiruv muammolari
Ikkilik qidiruv daraxtlari juda yaxshi, lekin bir nechta ogohlantirishlarni yodda tutish kerak. Ular odatda faqat muvozanatli bo'lsa samarali bo'ladi. Muvozanatli daraxt - bu daraxtdaraxtdagi har qanday tugunning pastki daraxtlari balandliklari orasidagi farq ko'pi bilan bitta. Keling, qoidalarni aniqlashtirishga yordam beradigan misolni ko'rib chiqaylik. Tasavvur qilaylik, massiv tartiblanuvchi sifatida boshlanadi.
Agar siz bu daraxtda ikkilik qidiruv daraxti algoritmini ishga tushirmoqchi boʻlsangiz, u xuddi kerakli qiymat topilmaguncha massiv boʻylab takrorlanayotgandek ishlaydi. Ikkilik qidiruvning kuchi kiruvchi qiymatlarni tezda filtrlash qobiliyatidadir. Agar daraxt muvozanatli bo'lmasa, u muvozanatli daraxt kabi foyda keltirmaydi.
Ikkilik qidiruv daraxtini yaratishda foydalanuvchi ishlayotgan ma'lumotlarni tekshirish juda muhim. Butun sonlar uchun ikkilik qidiruv daraxtini qo‘llashdan oldin uni muvozanatlash uchun massivni tasodifiylashtirish kabi tartiblarni birlashtirishingiz mumkin.
Ikkilik qidiruv hisoblash misollari
Quyidagi ikkilik qidiruv daraxtiga 25 kiritilsa, qanday daraxt paydo boʻlishini aniqlashimiz kerak:
10
/
/
5 15
/ /
/ /
2 12 20
X ni hali x ni oʻz ichiga olmagan T daraxtiga kiritishda x kaliti har doim yangi bargga joylashtiriladi. Shu munosabat bilan yangi daraxt quyidagicha ko'rinadi:
10
/
/
5 15
/ /
/ /
2 12 20
25
Quyidagi ikkilik qidiruv daraxtiga 7 qoʻshsangiz qanday daraxtga ega boʻlardingiz?
10
/
/
5 15
/ /
/ /
2 12 20
Javob:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Ikkilik qidiruv daraxti istalgan obyektni saqlash uchun ishlatilishi mumkin. Bog'langan ro'yxat o'rniga ikkilik qidiruv daraxtidan foydalanishning afzalligi shundaki, agar daraxt mos ravishda muvozanatlangan bo'lsa va "chiziqli" daraxtdan ko'ra "to'liq" daraxtga o'xshasa, qo'shish, qidirish va barcha o'chirish operatsiyalarini ishga tushirish uchun amalga oshirish mumkin. O(log N) vaqti.
