Dataxtlar, ikki tomonlama daraxtlar, ikkilik daraxtlarning vakilligi, ikkilik daraxtlarning o’tishi

Загружено в:

12.08.2023

Скачано:

0

Размер:

58.9853515625 KB

Скачать

2“Dataxtlar, ikki tomonlama daraxtlar, ikkilik daraxtlarning
vakilligi, ikkilik daraxtlarning o’tishi”
MUNDARIJA
Kirish ……………………………………... …………………………….……..…….3
I. NAZARIY QISM
1.1. Daraxtlar haqida ma’lumot…………………………………………..….…….4
1.2. Ikki tomonlama daraxtlar …………………………………………..…….…..14
II. AMALIY QISM
2.1. Ikkilik daraxtlarning vakili .............................................… ……………...… …21
2.2. Ikkilik daraxtlarning o’tishi ………………………………………………...….23
2.3. Ikkilik daraxtlarga misollar…………………………………………….……...29
Xulosa ……………………………………………………………………….….….32
Foydalanilgan adabiyotlar ………………….……………………………….……33

3 Kirish.
Ko'pchilik uchun "algoritm" so'zi maktab matematikasi bilan yoqimsiz aloqalarni
keltirib chiqaradi. Darhaqiqat, algoritmlar dasturlashda qo'llanila boshlanganidan
ancha oldin odamlar ulardan foydalanishni boshladilar va ularning faoliyat sohasi
faqat matematika bilan cheklanmaydi. Non pishirganda, siz retseptdan foydalanasiz
va shuning uchun algoritmga amal qilasiz.
Algoritmlar tosh davridan beri inson hayotining ajralmas qismi bo'lib kelgan.
Mualliflar kognitiv fan, matematika va iqtisod sohalaridagi fanlararo tadqiqotlar bilan
yaxshi tanish. Himoya qilishdan oldin tezis tadqiqotda ingliz tilidan, Brayan o'qigan
Kompyuter texnologiyalari va falsafani o'rgandi va har uch mutaxassislik
chorrahasida martaba qurdi. Tom Berklidagi Kaliforniya universitetida professor
bo'lishdan oldin psixologiya va statistikani o'rganish bilan ko'p yillar davomida
shug'ullangan va u erda deyarli barcha vaqtini insonning aqliy faoliyati va hisoblash
operatsiyalari o'rtasidagi munosabatlarni o'rganishga bag'ishlaydi.
Bundan tashqari, hayot uchun algoritmlarni qidirishda mualliflar so'nggi 50 yil
ichida eng mashhur algoritmlarni ishlab chiqqan odamlar bilan suhbatlashdi. Va ular
o'zlarining tadqiqotlari hayotiy muammolarni hal qilishda yondashuvlariga qanday
ta'sir qilganini so'rashdi. Zero, u aytganidek, “ilm shunchaki bilimlar majmuasidan
ko‘ra ko‘proq ma’lum fikrlash tarzidir”.
Har bir inson har kuni juda ko'p muammolarga duch keladi, eng oddiy va eng
ma'lum bo'lganidan tortib eng qiyinigacha. Ko'pgina vazifalar uchun ijrochiga ushbu
vazifani qanday hal qilishni tushuntiradigan muayyan qoidalar (ko'rsatmalar,
retseptlar) mavjud. Inson ushbu qoidalarni oldindan o'rganishi yoki muammoni hal
qilish jarayonida o'zini shakllantirishi mumkin. Muammolarni hal qilish qoidalari
qanchalik to`g`ri va aniq tasvirlangan bo`lsa, odam ularni shunchalik tez o`zlashtiradi
va qo`llashda samaraliroq bo`ladi. Inson ko'plab vazifalarning echimini texnik
qurilmalarga - avtomatik mashinalarga, robotlarga, kompyuterlarga o'tkazishi
mumkin.

41.1. Daraxtlar haqida malumot .
Algoritmlarning daraxtlar bilan ishlash samaradorligi . "Daraxtlar - rekursiv
algoritmlar" va "makon-vaqt" juftligi o'rtasida o'xshashliklarni yaratish
mumkin. Rekursiv dastur ishlayotganda funktsiya chaqiruv daraxti o'z vaqtida
kengaytiriladi va daraxt ma'lumotlar tuzilishi sifatida rekursiv algoritm bajarilishining
xotirada xaritalangan natijasiga o'xshaydi. Shuning uchun rekursiv algoritmlarning
samaradorligi to'g'risidagi xulosalar daraxtlarga taalluqlidir:
- daraxtning to'liq rekursiv o'tishi chiziqli;
- samarali ochko'zlik algoritmlari.
Daraxtga nisbatan ochko'zlik har bir tepada bitta bolani tanlashdan
iborat. Rekursiv chaqiruv davri o'rniga, barcha avlodlar uchun bitta qo'ng'iroq bo'lishi
kerak. Siz har bir qadamda tanlangan bolaga borib, rekursiv algoritmni dumaloq
algoritm bilan almashtirishingiz mumkin. Aniq uchun asosochko'z tanlov - daraxtga
ortiqcha narsalarni kiritish (tepalikdagi qo'shimcha ma'lumotlar) yoki undagi
ma'lumotlarni buyurtma qilish.
Daraxtlarning to'liq rekursiv o'tishiga asoslangan algoritmlar. Dastlab, daraxtda
ma'lumotlar qanday tashkil qilinganligidan qat'i nazar, eng oddiy algoritmlarni ko'rib
chiqamiz. Daraxtning to'liq rekursiv o'tishi daraxtning barcha tepalarini bosib o'tishni
va butun daraxt tuzilishining umumiy xususiyatlarini olishdan iborat. Siz darhol
bypass natijasini shakllantirishning texnologik usullari haqida to'xtalishingiz kerak:
- rekursiv funktsiyani aniq natijasi rekursiv funktsiyadan tushadigan zanjirning
bajarilishi paytida uning to'planishini nazarda tutadi (ya'ni, natijaning to'planishi
teskari yo'nalishda - avlodlardan ajdodgacha). Bundan tashqari , har bir tepalik,
avlodlardan olingan natijalarni o'ziga xos "malhamda uchib" qiladi, ya'ni. subtrees
natijalarini o'zi bilan birlashtiradi;
- rekursiv chaqiriqlar zanjiri bo'ylab uzatiladigan rasmiy parametr - zvenodan
foydalanish mumkin. Bunday holda, barcha rekursiv chaqiriqlar natijani to'plash

5uchun ishlatiladigan global ma'lumotlarning rolini o'ynaydigan umumiy o'zgaruvchiga
ishora qiladi.
Ro'yxatlar va massivlar bilan dastlabki taqqoslash. Daraxtdagi ma'lumotlarni
tashkil qilish tafsilotlariga kirmasdan ham , biz uchun ma'lum bo'lgan uning vakili
shakllariga asoslanib, dastlabki xulosalar chiqarishimiz mumkin. Birinchidan,
ichidaAlgoritmik ravishda daraxt taniqli so'zlarni "o'rmonga - ko'proq o'tin" ga amal
qiladi. Bu holda "o'tin" bu daraxtning "chuqurligi" o'sishi bilan sonning eksponent
o'sishi bo'lgan tepalardir. Agar bir vaqtning o'zida "ortiqcha" daraxtlarni kesishni
samarali tashkil etish imkoniyati mavjud bo'lsa, unda elementlarni qiymatlari bo'yicha
topish va ularga mantiqiy raqamlar bo'yicha kirishning samarali algoritmlariga umid
qilish mumkin. Bu erda ro'yxatlarga nisbatan aniq ustunlik mavjud, bu erda barcha
algoritmlar to'liq qidirishga asoslangan (chiziqli qidirish). Ikkinchidan, texnologik
jihatdantepaliklarning tartibini yoki daraxtlarga joylashishini o'zgartirish, ro'yxatlarda
bo'lgani kabi, alohida tepalardagi bog'lanishlarni (filiallarni) qayta tashkil etish orqali
ham amalga oshirilishi mumkin. Bu elementlarning massiv harakatini (siljishini) talab
qiladigan massivlarga nisbatan aniq ustunlikka ega. Shunday qilib, samaradorlik
nuqtai nazaridan daraxt bu ikkita haddan tashqari: qator va ro'yxat o'rtasidagi
kelishuvdir.
Muvozanat kabi xarakterli daraxtni tanishtiramiz.Balans daraxt shoxlari
uzunliklarida tarqalishini xarakterlaydi. Aniqrog'i, biz ildiz shoxidan tepalikka qadar
erkin shox bilan masofalar haqida gapiramiz. Maksimal va minimal novdalar uzunligi
1dan ko'p bo'lmagan farq qilsa , daraxt muvozanatli deb ataladi, bunday daraxt
novdaning uzunligi bilan daraxtning tepalari soni o'rtasidagi eksponent (yoki teskari,
logaritmik) bog'liqlik bilan tavsiflanadi :
N = 1 + m + m 2 + m 3 +… + m L < m L , L <log m N
Eng yomon holatda, har bir tepada bittadan bola bo'lsa, daraxt tanazzulga
uchraydi , bu holda novdalar uzunligi 1 ga teng bo'lmagan tepalar soniga teng bo'ladi.
Bundan tashqari, bir martalik o'qqa asoslangan barcha algoritmlar, to'liq rekursiv
o'tish, chiziqli murakkablikka ega bo'ladiT = N . Ularning yaxshilanishi faqatgina

6"botirish chuqurligini" cheklashdan iborat bo'lishi mumkin, agar buning uchun etarli
asoslar mavjud bo'lsa. Yana bir narsa shundaki , unga asoslangan
algoritmlardallanma. Har bir tepada ular mumkin bo'lgan bolalardan faqat bittasini
tanlaydilar. Bunday algoritmlar deyiladiochko'zlik ("8.7. Rekursiv algoritmlarning
samaradorligi" ga qarang). Siz darhol ularning murakkabligi ular tanlagan daraxt
novdasi uzunligiga teng ekanligini darhol ko'rishingiz mumkin. Balanslangan daraxt
uchun qaramlik logaritmik bo'ladi.
T = L <log m N, daraxtlar ro'yxatiga kirib borishi uchun u chiziqli. Bu erda ikkita
muammo mavjud. Birinchidan, muvozanatli daraxtni saqlash. Buning ikkita echimi
mavjud:
- odatdagidan ancha murakkab bo'lgan daraxt muvozanatini saqlaydigan
algoritmlardan foydalanish, chunki ular qo'shni daraxtlar vertikallari guruhlarining
turli xil topologik transformatsiyalaridan foydalanadilar (bundan tashqari, rekursiv);
- daraxtning davriy hizalanishi (muvozanati), ehtimol qo'shimcha ma'lumotlar
tuzilishi yordamida. Ushbu echim daraxt bilan ishlash uchun oddiy
algoritmlardan foydalanishga imkon beradi , lekin uning muvozanatini kuzatishni talab
qiladi (xuddi shu algoritmlar buni amalga oshirishi mumkinligiga e'tibor bering,
masalan, ma'lum bir qiymatni qidirishda filial uzunligini aniqlash). Balanslash
protsedurasi ancha vaqt talab qilishi mumkin , ammo bu nisbatan kamdan-kam
hollarda deyiladi.
Kundalik darajada ushbu alternativani "ideal tartib yoki davriy umumiy
tozalash " sifatida shakllantirish mumkin . Shunga o'xshash holat har qanday dinamik
resurslarni taqsimlash va ulardan foydalanish tizimida uchraydi: dinamik xotirani
ajratish tizimida (2.6), ikkilik faylni rejalashtirishda (9.2), operatsion tizimning
fayllarni boshqarish tizimida, u o'xshash echimlarga ega.
Ikkinchi muammo algoritmda har bir tepada bitta avlodni aniq tanlash uchun
asoslar yotadi (badiiy o'xshashlik - "chorrahada ritsar"). Bu erda yana ikkita
yondashuv mavjud:
- tepada qo'shimcha (ortiqcha) ma'lumotlarning mavjudligi , bu "bu erda va

7hozirda" bunday tanlovni amalga oshirishga imkon beradi ;
- daraxtda ma'lumotlarni joylashtirishning ma'lum bir tartibining mavjudligi.
Daraxtlarning minimal balandligi . Agar mening avvalgi postlarimdan birida u
muvozanatli qidiruv daraxtlarini yaratish uchun zamonaviy zamonaviy yondashuv
bo'lgan bo'lsa, unda bu yozuv AVL daraxtlarini yaratishga bag'ishlangan - ehtimol bu
1962 yilda bizning (o'sha paytdagi sovet) olimlarimiz Adelson tomonidan ixtiro
qilingan muvozanatli ikkitomonlama qidiruv daraxtlari. -Velskiy va Landis.
Tarmoqda AVL daraxtlarining ko'plab sotuvlarini topishingiz mumkin (masalan, bu
erda), lekin men ko'rgan hamma narsa juda nekbinlikka ilhom bermaydi, ayniqsa agar
siz hamma narsani noldan aniqlamoqchi bo'lsangiz.
Hamma joyda AVL daraxtlari qizil-qora daraxtlarga qaraganda sodda ekanligi
ta'kidlanmoqda, ammo unga biriktirilgan kodga qarab, siz ushbu bayonotga shubha
qila boshlaysiz. Aslida, barmoqlarda AVL daraxtlari qanday joylashtirilganligini
tushuntirish istagi ushbu xabarni yozishga turtki bo'ldi. Taqdimot C ++ kodi bilan
tasvirlangan.AVL daraxti, asosan, ikkilik qidiruv daraxti bo'lib, ularning kalitlari
standart xususiyatga mos keladi: har qanday daraxt tugunining kaliti ushbu tugunning
chap pastki qismidagi kalitlardan kam emas va ushbu tugunning pastki satridagi biron
bir kalitdan ko'p emas. Bu AVL daraxtidan kerakli kalitni qidirish uchun standart
algoritmdan foydalanishingiz mumkin degan ma'noni anglatadi. Oddiylik uchun ,
daraxtdagi barcha kalitlar butun bo'lib, takrorlanmaydi deb taxmin qilamiz.
A VL daraxtining o'ziga xos xususiyati shundaki, u quyidagi ma'noda
muvozanatlangan: har qanday daraxt tugunlari uchun uning pastki pastki balandligi
balandligi chap pastki daraxt balandligidan ko'pi bilan farq qiladi. Ushbu xususiyat
daraxtning balandligi logaritmik ravishda tugunlar soniga bog'liq bo'lishi uchun etarli
ekanligi isbotlandi: AVL daraxtining h balandligi n tugmachalari log2 (n + 1) dan
1.44 log2 (n + 2) - 0.328 oralig'ida. Ikkilamchi qidirish daraxtlarida (operatsiyalarni
bajarish, tugunlarni kiritish va yo'q qilish) asosiy operatsiyalar uning balandligiga
chiziqli bog'liq bo'lganligi sababli, biz ushbu algoritmlarning ishlash vaqtining
daraxtda saqlanadigan kalitlar soniga kafolatlangan logaritmik bog'liqligini olamiz.

8Eslatib o'tamiz, tasodifiy qidiruv daraxtlari faqat ehtimollik ma'nosida muvozanatni
ta'minlaydi: katta n uchun yuqori muvozanatsiz daraxtni olish ehtimoli , ahamiyatsiz
bo'lsa ham, nolga teng emas.
Biz AVL daraxtining tugunlarini quyidagi tuzilishga ega bo'lamiz:
struct node // structure for the presentation of the word dereva.
{
int key;
unsigned char height;
node* left; node* right;
node(int k) { key = k; left = right = 0; height = 1; }
};
Kalit maydonchasi tugun tugmachasini saqlaydi landligi, chap va o'ng maydonlar
chap va o'ng pastki qismlarga ishora qiladi. Oddiy konstruktor berilgan k tugmachasi
bilan yangi tugun (balandlik 1) hosil qiladi.
An'anaga ko'ra, AVL daraxtining tugunlari balandlikni saqlamaydi, lekin o'ng va
chap pastki daraxtlarning balandligidagi farq (balans koeffitsienti deb ataladi), ular
faqat uchta , 1, 0 va 1 qiymatlarini olishi mumkin. Shunga qaramay, ushbu farq
o'zgaruvchida saqlanib qolinadi, uning hajmi kamida bitta baytga teng (agar siz
bunday qiymatlarni "samarali" qadoqlashning ba'zi hiyla-nayrang sxemalarini o'ylab
topmasangiz). Eslatib o'tamiz, balandligi h <1.44 log2 (n + 2), bu, masalan, n = 109
(bir milliard tugmachasi, tugunlarni saqlash uchun 10 gigabaytdan ortiq xotira)
bo'lganda, daraxt balandligi h = 44 qiymatidan oshmaydi, bu muvaffaqiyatli
joylashtirilgan. muvozanat koeffitsienti bilan bir xil bayt xotirada. Shunday qilib,
balandlikni saqlash bir tomondan daraxt tugunlari uchun ajratilgan xotira hajmini
oshirmaydi, ammo boshqa tomondan ba'zi operats iyalarni bajarishni sezilarli darajada
osonlashtiradi.
Biz balandlik bilan bog'liq uchta yordamchi funktsiyani aniqlaymiz. Birinchisi -
balandlik maydonchasi uchun o'rash, u nol ko'rsatkichlar bilan (bo'sh daraxtlar bilan)
ishlashi mumkin:

9node* balance(node* p) // балансировка узла p
{
fixheight(p);
if( bfactor(p)==2 ) {
if(bfactor(p->right)< 0 ) p->right = rotateright(p->right);
return rotateleft(p);
}
if( bfactor(p)==-2 ) {
if( bfactor(p->left) > 0 ) p->left = rotateleft(p->left);
return rotateright(p);
}
return p; // балансировка не нужна
}
Kalitlarni kiritish . Yangi kalit AVL daraxti ichiga, katta-kichiklikda, oddiy
izlash daraxtlari singari kiritilgan: biz tugunni joriy tugun va solishtiriladigan kalitni
taqqoslash natijasiga qarab harakatning o'ng yoki chap yo'nalishini
tanlaymiz. Faqatgina farq shundaki , siz rekursiondan qaytganingizda (ya'ni, o'ng yoki
chap pastki qatorga kalit kiritilganidan keyin va bu daraxt muvozanatlangan bo'lsa),
hozirgi tugun muvozanatlanadi. Yo'l bo'ylab biron bir tugunga shunday kiritish
natijasida kelib chiqadigan nomutanosiblik ikkitadan oshmasligi aniq isbotlangan, bu
yuqorida tavsiflangan muvozanat funktsiyasini qo'llash to'g'ri ekanligini anglatadi.
Daraxt va unga ekvivalent tushunchalar. Siklga ega bo‘lmagan
orientirlanmagan bog'lamli graf daraxt deb ataladi.
1. Ta’rifga ko‘ra daraxt sirtmoqlar va karrali qirralarga ega emas. Siklga ega
bo‘lmagan orientirlanmagan graf o‘rmon (asiklik graf) deb ataladi.

$101- m i s о 1. 1- shaklda bogiamli komponentli soni beshga teng boigan graf tasvirlangan bo‘lib, u o‘nnondir. Bu grafdagi bog‘lamli komponentlaming har biri daraxtdir. ■ 2- uchga ega bir-biriga izomorf bo‘lmagan barcha (ular bor-yog‘i ikkita) daraxtlarning geometrik ifodalanishi tasvirlangan. ■ Beshta uchga ega bir-biriga izomorf bo‘lmagan barcha daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko‘rsatish qiyin emas. Daraxt tushunchasiga boshqacha ham ta’rif berish mumkin.Umuman olganda, G (m ,n) - graf uchun daraxtlar haqidagi asosiy teorema deb ataluvchi quyidagi teorema o ‘rinlidir. 1-teorema . Uchlari soni m va qirralari soni n bo'lgan G graf uchun quyidagi tasdiqlar ekvivalentdir: 1) G daraxtdir; 2) G asiklikdir va n = m — \; 3) G bog 'lamlidir va n = m — \ ; 4) G bog'lamlidir va undan istalgan qirrani olib tashlash amalini qo'llash natijasida bog'lamli bo lmagan graf hosil bo'ladi, y a ’ni G ning har bir qirrasi ко 'prikdir. 5) G grafninng o'zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutahtiriladi; Orientirlangan daraxt tushunchasi ham bor. www.ziyouz.com kutubxonasi 6) G asiklik bo 'lib, uning qo ‘shni bo ‘Imagan ikkita uchini qirra bilan tutashtirish amalini qo ‘Hash natijasida faqat bitta siklga ega bo ‘Igan graf hosil bo 'ladi. Isboti. Teoremaning 1) tasdig‘idan uning 2) tasdig‘i kelib chiqishini isbotlaymiz. G graf daraxt bo‘lsin. Daraxtning ta’rifiga ko'ra, u asiklik bo‘lishini ta’kidlab, m bo‘yicha matematik induksiya usulini qo‘llaymiz. Matematik induksiya usulining bazasi: agar m — 1 bo‘lsa, u holda G daraxt faqat bitta uchdan tashkil topgan bo‘ladi.$ $11Tabiiyki, agar bitta uchga ega bo‘lgan grafda sikl bo‘lmasa, u holda unda birorta ham qirra yo‘q, ya’ni n — 0 . Demak, bu holda tasdiq to‘g‘ridir. Induksion o‘tish: G daraxt uchun k > 2 va m = k bo‘lganda 2) tasdiq o ‘rinli bo‘lsin deb faraz qilamiz. Endi uchlari soni m — k + 1 va qirralari soni n bo‘lgan daraxtni qaraymiz. Bu daraxtning ixtiyoriy qirrasini (v,,v2) bilan belgilab, undan bu qirrani olib tashlasak, v, uchdan v2 uchgacha marshruti (aniqrog‘i, zanjiri) mavjud bo‘lmagan grafni hosil qilamiz, chunki agar hosil bo‘lgan grafda bunday zanjir bor bo‘lsa edi, u holda G daraxtda sikl topilar edi. Bunday bo‘lishi esa mumkin emas. Hosil bo‘lgan graf ikkita G, va G2 bog‘lamli komponentlardan iborat bo‘lib, bu komponentlarning har biri daraxtdir. Yana shuni ham e’tiborga olish kerakki, G, va G2 daraxtlaming har biridagi uchlar soni к dan oshmaydi. Matematik induksiya usuliga ko‘ra, bu daraxtlaming har birida qirralar soni uning uchlari sonidan bitta kam bo‘lishini ta’kidlaymiz, ya’ni Gi graf (mi,ni) -graf bo‘lsa, quyidagi tengliklar o‘rinlidir: n — nl + n 2 + \ , к +1 = mi + m1 va nt = mt. — 1 (/ = 1 , 2 ). Bu tengliklardan n = «j + n2 +1 = mx - 1 + m2 - 1 +1 = ( и ?, + m2) -1 = (k + 1) -1 boiishi kelib chiqadi. Demak, m = k + 1 bo‘lganda ham n - m — 1 tenglik o ‘rinlidir. Bu esa, matematik induksiya usuliga ko‘ra, kerakli tasdiqning isbotlanganligini anglatadi. Endi daraxtlar haqidagi asosiy teoremaning 2) tasdig‘idan uning 3) tasdig‘i kelib chiqishini isbotlaymiz. G graf asiklik, ya’ni u siklga ega bo‘lmagan graf va n - m — 1 bo‘lsin. G grafning bog‘lamli bo‘lishini isbotlash kerak. Agar G graf bog‘lamli bo‘lmasa, u holda uni har bir bog‘lamli komponenti siklsiz graf G; (ya’ni, daraxt) bo'lgan qandaydir к ta (£>1) к graflar diz’yunktiv birlashmasi sifatida G = ^ JG ( tenglik bilan ifodalash 1=1 mumkin. Har bir i = 1 ,k uchun G( graf daraxt bo'lgani uchun, yuqorida isbotlagan tasdiqqa ko‘ra, agar unda ta uch va ta qirra bo‘lsa, u holda к Gi asiklikdir va ni —mi —\ tenglik o ‘rinlidir. Tushunarliki, m = У ./ и ,. i=i к va n = ^ nt .$ $12Demak, /=1 к к к n = Y s ni - ^ = Y s mi ~ k = m - к , /=1 i=i i=i ya’ni G graf uchlarining umumiy soni undagi qirralar umumiy sonidan к ta ortiqdir. Bu esa, &>1 boMgani uchun, n = m — 1 tenglikka ziddir. Zarur tasdiq isbotlandi. Teoremaning 3) tasdig‘idan uning 4) tasdig‘i kelib chiqishini isbotlaymiz. G - bog‘lamli graf va n = m - 1 bo'lsin. Avvalo к ta bog'lamlilik komponentlariga ega karrali qirralari bo‘lmagan sirtmoqsiz (m,n) -graf uchun ( m - k ) ( m - k + 1) m -k < n < - ----------------------- 2 munosabat o'rinli bo‘lishini eslatamiz (ushbu bobning 4- paragrafidagi 7- teoremaga qarang). n = m - \ boMgani sababli G bogiam li grafdan istalgan qirra olib tashlansa, natijada m ta uch va (m —2)ta qirralari bo'lgan graf hosil bo'ladiki, bunday graf m - k l (i = \,m). Bundan yuqoridagi tenglik o‘rinli bo'lishi uchun p ( v }) , p ( v 2),...,p(vm) ketma-ketlikdagi hech boMmaganda ikkita son birga teng bo'lishi kelib chiqadi. ■ 2- natija . m ta uch va к ta bog'lamli komponentli o'rmondagi qirralar soni (m — k)ga tengdir. Isboti . 1 - teorema isbotining 2) tasdiqdan 3) tasdiq kelib chiqishiga bag‘ishlangan qismiga qarang. ■ 2- teorema . Istalgan daraxtning markazi uning bitta uchidan yoki ikkita qo 'shni uchlaridan iborat bo 'ladi. Isboti. Agar daraxt bitta uch yoki ikkita qo'shni uch va ularni tuashtiruvchi qirradan tashkil topgan bo'lsa, teorema tasdig‘i to‘g‘riligi oydindir. G daraxt tarkibida ikkitadan ko‘p uch bor deb faraz qilamiz. G daraxtdagi darajalari birga teng barcha uchlarni (ya’ni, daraxtning barcha chetki uchlarini) bu uchlarga insident barcha qirralar (ya’ni, daraxtning barcha chetki qirralari) bilan birgalikda G daraxtdan olib tashlaymiz. Natijada uchlari va qirralari soni berilgan G daraxtdagi uchlar va qirralar sonidan kam bo'lgan qandaydir G' daraxtni hosil qilamiz. G’ daraxtdagi har bir uch ekssentrisiteti G daraxtdagi mos uch ekssentrisitetidan bitta kam bo'lishi va bu daraxtlaming markazlari ustma-ust tushishi ravshandir. Berilgan graf chekli bo'lgani uchun, yuqoridagi bayon etilgan jarayonni yetarlicha marta takrorlash natijasida bitta uch yoki ikkita qo'shni uch va ularni turashtiruvchi qirradan tashkil topgan qandaydir daraxtni hosil qilamiz. ■$

13Uchlari soni ma’lum, o'zaro izomorf bo'lmagan va qandaydir shartlarni
qanoatlantiruvchi daraxtlar sonini aniqlash masalasi daraxtlarni o'rganishda muhim
masala hisoblanadi. Yuqorida 4, 5 va 6 ta uchlarga ega o'zaro izomorf bo'lmagan
daraxtlar mos ravishda 2, 3 va 6 ta ekanligi ta’kidlangan edi. A. Keli uglerod atomlari
soni berilgan va CnH ,n+2 m tenglik o'rinlidir. Daraxtning ta’rifiga ko'ra, u
ko‘rinishdagi kimyoviy formula bilan ifodalanuvchi to'yingan uglevodorodlar sonini
topish masalasini har bir uchining darajasi bir yoki to‘rt bo‘lgan daraxtlar sonini
topish masalasiga keltirib hal qilgan. Quyidagi teorema Keli nomi bilan yuritiladi.
3- t e o r e m a: (Keli). Uchlari soni m bo 'Igan belgilangan daraxtlarsoni m"' 2ga
teng.
Qidirish daraxti - bu "buyurtma qilingan ikkilik daraxti" deb nomlanadigan
tugunlar tartibda joylashtirilgan ikkilik daraxtlar ma'lumotlari tizimining bir turi. Bu
tugunlarga asoslangan ma'lumotlarning tuzilishi bo'lib, u ma'lumotlarni saralash, olish
va qidirishning samarali va tezkor usulini ta'minlaydi. Har bir tugun uchun chap
pastki qismning elementlari uning asosiy tugunidagi kalitdan kam yoki unga teng
bo'lishi kerak. Ikkilamchi kalitlar bo'lmasligi kerak. Oddiy qilib aytganda , bu
elementlarni xotirada samarali saqlaydigan va boshqaradigan ikkilik daraxt
ma'lumotlari tuzilmasining maxsus turi.

141.2. Ikki tomonlama daraxtlar.
Ikkilik daraxt - bu har bir tugun nolga teng , bitta yoki ko'pi bilan ikkita
boladan iborat bo'lgan ierarxik ma'lumotlar tuzilishi. Har bir tugun "chap"
ko'rsatkichni, "o'ng" ko'rsatkichni va ma'lumotlar elementini o'z ichiga oladi. "Ildiz"
ko'rsatkichi daraxtning eng yuqori tugunini anglatadi. Ma'lumotlar tarkibidagi har
bir tugun to'g'ridan-to'g'ri bolalar deb ataladigan har ikki tomonning o'zboshimchalik
bilan soniga bog'liq. Null ko'rsatkichi ikkilik daraxtni anglatadi. Ikkilik daraxtda
tugunlarni qanday tashkil qilish bo'yicha aniq tartib yo'q. Bolalar tugunlari
bo'lmagan tugunlarga barg tugunlari yoki tashqi tugunlar deyiladi.
Nima uchun ikkilik daraxtlar kerak?
Nima uchun biz ikkilik daraxtlardan foydalanamiz?
 BT yordamida biz tezda qidirish, kiritish va o'chirishni amalga oshiramiz (ba'zi bir
ustuvor tartibda berilgan ... BST kabi).
 BT yordamida biz eng yaqin narsani ham topishimiz mumkin.
 Ma'lumotlarni ierarxik tarzda saqlang (masalan, kompyuterdagi fayl tizimi).
 Har qanday harakatni amalga oshirish uchun kam vaqt talab qiladigan ko'rsatgich
yordamida BTni amalga oshiring.
 Lug'atlarni prefiks izlash bilan amalga oshiring.
 Ushbu ma'lumotlar to'plamining sobit matnida tezkor qidiruv.
Ikkilik daraxtlarning xususiyatlari. Har qanday darajadagi maksimal tugun
soni: 2 ^ L bu erda L - bir qator darajalar (0 <= L <= H).
1. BT balandlikdagi H tugunlarining minimal va maksimal soni: Minimal- H + 1 va
maksimal- 2 ^ (H + 1) - 1 bu erda 0 darajasi 0 ga teng.
2. N tugunlarga ega bo'lgan ma'lum bir BTning minimal balandligi: log2 (N + 1) -
1 bu erda 0 darajasi 0 ga teng.
3. Barg tugunlarining umumiy soni: 2 bolali tugunlarning umumiy soni + 1.
4. L bargli tugunlarga ega bo'lgan BT darajalarining minimal soni: (log2 L) +1 .

15Samaradorlik. Ikkilik qidiruv daraxtiga bitta element qo'shilishi
o'rtacha O(log n) jarayon (yilda.) katta O yozuvlari ). N ta elementni qo'shish -
bu O(n jurnal n) jarayon, daraxtlarni saralashni "tez saralash" jarayoniga aylantirish.
Balanssiz ikkilik daraxtga element qo'shishni talab qiladi O(n) eng yomon holatda
vaqt: qachon daraxt a ga o'xshaydi bog'langan ro'yxat (buzilib ketgan daraxt). Bu eng
yomon holatga olib keladi O(n²) Bu tartiblash algoritmi uchun vaqt.Bu eng yomon
holat algoritm allaqachon saralangan to'plamda yoki deyarli tartiblangan, teskari yoki
deyarli teskari o'ralgan to'plamda ishlaganda sodir bo'ladi. Kutilmoqda O(n jurnal n)
vaqtni qatorni aralashtirish orqali erishish mumkin, ammo bu teng elementlarga
yordam bermaydi.
A yordamida eng yomon xatti-harakatlarni yaxshilash mumkin o'z-o'zini
muvozanatlashtiradigan ikkilik qidiruv daraxti. Bunday daraxtdan
foydalanib, algoritmda
O(n jurnal n) eng yomon ko'rsatkich, shuning uchun a uchun
daraja maqbul bo'ladi taqqoslash. Biroq, daraxtlarni saralash algoritmlari, masalan,
joyidagi algoritmlardan farqli o'laroq, daraxt uchun alohida xotira ajratilishini talab
qiladi tezkor yoki kassa. Eng keng tarqalgan platformalarda bu shuni anglatadi uyma
xotira ishlatilishi kerak, bu bilan solishtirganda muhim ko'rsatkich tezkor va kassa. A
dan foydalanganda
daraxt daraxti ikkilik qidiruv daraxti sifatida, natijada algoritm
(deyiladi splaysort) bu qo'shimcha xususiyatga ega moslashuvchan sort, ya'ni uning
ishlash muddati nisbatan tezroq O(n jurnal n) deyarli saralangan yozuvlar uchun.
Bir qator N haqiqiy sonlar uchun, har bir raqam o'z kalitiga ega , lekin kalitlar
mutlaqo boshqacha emas. Ma'lumki, bizda turli xil kalitlar mavjud.
K = O (log N), agar u (N log (log N))) murakkabligida barqaror tartiblash algoritmini
topish kerak bo'lsa, O (N) ning qo'shimcha joyidan foydalanishim mumkinmi?
Bu umumiy maqsadlar uchun n (n log (log n)) sort algoritmini chiqarishning iloji
yo'qligini tushuntirib Steven S. Skienaning Algoritm dizaynlashuvi qo'llanmasi dan
olingan.
Biz eng yomon O (n log n) vaqtida ishlaydigan turli xil tartiblash algoritmlarini
ko'rdik, ammo ularning hech biri lineer emas. N elementlarini tartiblashtirish uchun,
albatta, ularning hammasiga qarashni talab qiladi, shuning uchun har qanday

16tartiblash algoritmi eng yomon holatda Ō (n) bo'lishi kerak. Ushbu qolgan Θ (log n)
bo'shlig'ini yopamizmi?
Agar Ō (n log n) pastki chegarasi har qanday farqlash algoritmining har bir n-
nizada ijro etilishi paytida boshqacha bo'lishi kerakligini kuzatish orqali ko'rsatilishi
mumkin! n tugmalarining permutations. Har bir juft taqqoslash natijasi har qanday
taqqoslash asosida tartiblash algoritmining ish vaqti xatti-harakatini boshqaradi. Biz
bunday nusxa bilan daraxt sifatida bunday algoritmni yuzaga keltirish mumkin
bo'lgan barcha to'plamlarni o'ylab ko'rishimiz mumkin! barglari. Minimal
balandlikdagi daraxt eng tez mumkin bo'lgan algoritmga mos keladi va lg (n!) = Θ (n
log n) bo'ladi.
Tilman Vogel ta'kidlaganidek, kirish ma'lumotlari bo'yicha muayyan cheklovlarni
joriy qilish orqali nazariy ravishda (n log (log n)) murakkabligi bilan ishlaydigan
algoritmlar mavjud. Aksariyat amaliy ilovalarda katta foyda keltirishi ehtimoldan
yiroq emas, ehtimol, nima uchun men hech qachon amalga oshirishni ko'rmaganman,
lekin agar ular sizning ishlatishingizga mos keladigan bo'lsa, men ushbu
algoritmlarning tezkorligini tezroq ko'rishni juda xohlayman.
Bu umumiy maqsadlar uchun n (n log (log n)) sort algoritmini chiqarishning iloji
yo'qligini tushuntirib Steven S. Skienaning Algoritm dizaynlashuvi qo'llanmasi dan
olingan.
Biz eng yomon O (n log n) vaqtida ishlaydigan turli xil tartiblash algoritmlarini
ko'rdik, ammo ularning hech biri lineer emas. N elementlarini tartiblashtirish uchun,
albatta, ularning hammasiga qarashni talab qiladi, shuning uchun har qanday
tartiblash algoritmi eng yomon holatda Ō (n) bo'lishi kerak. Ushbu qolgan Θ (log n)
bo'shlig'ini yopamizmi?
Agar Ō (n log n) pastki chegarasi har qanday farqlash algoritmining har bir n-
nizada ijro etilishi paytida boshqacha bo'lishi kerakligini kuzatish orqali ko'rsatilishi
mumkin! n tugmalarining permutations. Har bir juft taqqoslash natijasi har qanday
taqqoslash asosida tartiblash algoritmining ish vaqti xatti-harakatini boshqaradi. Biz
bunday nusxa bilan daraxt sifatida bunday algoritmni yuzaga keltirish mumkin
bo'lgan barcha to'plamlarni o'ylab ko'rishimiz mumkin! barglari. Minimal

17balandlikdagi daraxt eng tez mumkin bo'lgan algoritmga mos keladi va lg (n!) = Θ (n
log n) bo'ladi.
Siz an'anaviy tartiblash algoritmlarini (qabariq, birlashma, tezkor va
h.k.) tasavvur qilsangiz , u aslida BucketSort yoki RadixSort tavsifini tasvirlab bergan
asl algoritmdir. Ular ikkitomonlama taqqoslovlarni bajarmasliklari uchun , ularni
(nolni) taqiqlash ostiga qo'ymaydilar, ammo tartiblangan elementlarning soniga ko'ra
taqqoslashadi!
Men faqatgina Radixsortning bir nechtagina kalit yoki qiymatlarni sortirovka qilish
uchun kerakli murakkabligi bo'lishi mumkinligini taxmin qilishim mumkin. Ammo
100% ishonchim komil emas, chunki uni sinab ko'rmaganman va uni isbotladim.
Siz an'anaviy tartiblash algoritmlarini (qabariq, birlashma, tezkor va h.k.)
tasavvur qilsangiz, u aslida BucketSort yoki RadixSort tavsifini tasvirlab bergan asl
algoritmdir. Ular ikkitomonlama taqqoslovlarni bajarmasliklari uchun, ularni (nolni)
taqiqlash ostiga qo'ymaydilar, ammo tartiblangan elementlarning soniga ko'ra
taqqoslashadi!
Men faqatgina Radixsortning bir nechtagina kalit yoki qiymatlarni sortirovka qilish
uchun kerakli murakkabligi bo'lishi mumkinligini taxmin qilishim mumkin. Ammo
100% ishonchim komil emas, chunki uni sinab ko'rmaganman va uni isbotladim.
Biz ram modelini emas, taqqoslash modelini qo'llaymiz. Ma'lumki, n log h pastki
chegarasidan o'tolmaymiz, bu erda n kirish hajmi va h konteynerdagi elementlar.
Algoritmlarni tartiblashda biz RBT va AVL va ustuvor navbat (Cartesian daraxt turi)
kabi muvozanatli ikkilik qidiruv daraxti orqali yuqori chegaraga erishishimiz
mumkin.
Bunday holatda, tanlangan konteynerning o'lchami h = k = log n dan (kod <="" n=""
==""> universallik). Aslida, raul_zevahc bu g'oyani oladi, biz faqat kuchli
barqaror tartibida erishish uchun yechimni biroz o'zgartirishimiz kerak. Bir qatorda
elementlarning sonini hisobga oladigan hisoblashning o'rniga, biz har bir tugun
uchun
quyruq (birinchi bo'lib, birinchi chiqadi) ni saqlaymiz. Har qanday tugunni
bosib o'tganimizda, biz ushbu tugunning barcha elementlarini chiqaramiz.

18Mustahkam bo'lmagan saralash algoritmi uchun , uni har doim barqarorga
o'zgartiramiz, bu vaqtni dastlabki tartibga solish narxiga bog'liq.
Biz ram modelini emas , taqqoslash modelini qo ' llaymiz . Ma ' lumki , n log h pastki
chegarasidan o ' tolmaymiz , bu erda n kirish hajmi va h konteynerdagi elementlar .
Binar daraxtlar haqida tushuncha . Agar daraxtni tashkil etuvchi
element(tugun)lardan ko`pi bilan 2ta shox chiqsa, yani har bir tugun tuzilmaning
ko`pi bilan 2ta tuguni bilan bog`langan bo`lsa, u holda bunday daraxt binar daraxt
deyiladi.
Umumiy holda binary daraxt har bir elementi 4ta maydonga ega yozuv
hisoblanadi.
Masalan, quyidagi kalit elementardan binar daraxt quramiz:
50, 46, 61, 48, 29, 55, 79. u quyidagi ko`riishga ega bo`ladi:
Izoh. Binar daraxtda: key(left_son)<key(right_son)< b="">.
Tarif 1. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari va vazni teng
bo`lsa, u holda bunday binar daraxt ideal muvozanatlangan daraxt deyiladi
Tarif 2. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari va vazni teng
bo`lsa, u holda bunday binar daraxt ideal muvozanatlangan daraxt deyiladi
Yuqorida hosil qilingan binary daraxtimiz ideal muvozanatlangan daraxtga misol
bo`ladi.
Tarif 3. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari orasida farq 1
dan katta bo`lmasa, u holda bunday binary daraxt muvozanatlangan daraxt deyiladi;
m-o`lchamli daraxtni binar ko`rinishga keltirish :
Ko`p o`lchamli daraxtni binary ko`rinishga keltirishning noformal algoritmi:
Daraxtning har bir tugunida katta o`g`liga mos chetki chap shoxidan tashqari barcha
shoxlari kesib tashlanadi.
Bitta otaning barcha o`g`illari gorizontal chiziq bilan ulanadi.
Hosil qilingan tuzilmada har bir katta o`g`il mazkur tugun pastida turgan tugun
hisoblanadi. (agar u mavjud bo`lsa). Amallar ketma-ketligi quyida keltirilgan:

19Daraxt tugunini qidirish. Tog’ri (Yuqoridan quyiga). Ko’ruv quyidagi ketma-
ketlikda bajariladi: A-B-C;
Simmetrik (Chapdan o’ngga). Ko’ruv quyidagi ketma-ketlikda bajariladi: B-A-C.
Teskari (quyidan yuqoriga). Ko’ruv quyidagi ketma-ketlikda bajariladi: B-C-A.
Daraxtga yangi tugun qo’shish. Daraxtga biron bir tugun qo’shishdan oldin
daraxtga berilgan kalit bo’yicha qidiruvni amalga oshirish lozim bo’ladi. Agar
berilgan kalitga teng kalitli tugun mavjud bo’lsa, u xolda dastur o’z ishini yakunlaydi,
aks holda daraxtga tugun qo’yish amalga oshiriladi.
Eslatma: Daraxtda yangi tugun faqatgina ko’rsatgichlarini kamida bittasi bo’sh
bo’lgan tugundan keyin qo’yiladi.
Binar daraxtdan elementlarni o’chirish. Daraxt tuguni o’chirlayotganda 3 hil
holat bo’lishi mumkin:
Topilgan tugun terminal. Bu holatda tugun shunchaki o’chirib tashlanadi.
Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga
joylashtiriladi.
O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qism
daraxtlar zvenosini topish lozimki , uni o’chirilayotgan tugun o’rniga qo’yish mumkin
bo’lsin. Bunday zveno har doim mavjud bo’ladi.
Yoki chap qism daraxtning eng ‘ng tomondagi tuguni (ushbu zvenoga erishish
uchun keying uchiga chap shoh orqali o’tib, navbatdagi uchlariga esa murojaat NIL
bo’lmagunicha, faqatgina o’ng shohlari orqali o’tish zarur).
Yoki o’ng qisim daraxtning eng chap tuguni (ushbu zvenoga erishish uchun
keying uchta o’ng shoh orqali o’tib, navbatdagi uchlariga esa, murojaat NIL
bo’lmaguncha, faqatgina chap shohlari orqali o’tish zarur).

20Binar daraxtidan tugunni o’chirish. Mazkur prodseduraning vazifasi shundan
iboratki , u berigan kalit bo’yicha daraxt tuguni qidiruvini amalga oshiradi. Qidiruv
operatsiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar
elementlar daraxtga kalit qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u
holda daraxt bir tomonga yo’nalgan ro’yhat hosil qiladi (chiqish darajasi 1 bo’ladi,
ya’ni yagona shohga ega),
Bu holatda daraxtda qidiruv vaqti , bir tomonlama yo’naltirilgan ro’yhatdagi kabi
bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi.
Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi.
Ikkilik daraxt va ikkilik qidiruv daraxti ta'rifi - ikkilik daraxt - bu bolada nol, bitta
yoki maksimal ikkita bola tugunlari bo'lishi mumkin bo'lgan ierarxik
ma'lumotlar tuzilishi ; har bir tugun chap ko'rsatgichni, o'ng ko'rsatgichni va
ma'lumotlar elementini o'z ichiga oladi. Daraxtda tugunlarni qanday tashkil qilish
kerakligi to'g'risida alohida tartib yo'q. O'z navbatida , ikkilik qidirish daraxti - bu
tugunlarni qanday tartibga solish kerakligi haqida nisbatan buyurtma mavjud bo'lgan
buyurtma qilingan ikkilik daraxti.
Ikkilik daraxt va ikkilik qidiruv daraxtining tuzilishi - Daraxtdagi eng yuqori
tugun ikkilik daraxtdagi ildiz ko'rsatkichini, chap va o'ng tomondagi chiziqlar ikkala
tomonning kichik daraxtlarini bildiradi. Bu daraxt tuzilishidagi ma'lumotlarni aks
ettiradigan ixtisoslashgan daraxt shakli. O'z navbatida, ikkilik qidiruv daraxti - bu
chap qismdagi barcha tugunlar ildiz tugunining qiymatidan kam yoki unga teng
bo'lgan va o'ng pastki satrning qiymatidan kattaroq yoki unga teng bo'lgan ikkilik
daraxt turi. ildiz tugunidan.
Ikkilik daraxt va ikkilik qidiruv daraxti ishlashi - Ikkilamchi daraxt ikkita bolasi
va bitta ota-onasi bo'lgan har qanday narsa bo'lishi mumkin. Ikkilik daraxtda
bajarilishi mumkin bo'lgan keng tarqalgan operatsiyalar qo'shilish, o'chirish va
ayirishdir. Ikkilamchi qidirish daraxtlari - bu tezkor va samarali qidirish, kiritish va
o'chirishga imkon beradigan saralangan ikkilik daraxtlar. Ikkilik daraxtlardan farqli
o'laroq, ikkilik qidirish daraxtlari kalitlarini tartiblashtiradi .

212.1. Ikkilik daraxtlarning vakili .
To ' liq ikkilik daraxtlar . Ildiz va oraliq tugunlari 2 ta tugunchadan iborat bo'lgan
Ikkilik daraxt. Boshqacha qilib aytganda, barg tugunlaridan tashqari har bir tugunda 2
ta bola tuguni bor deyishimiz mumkin.
To'liq ikkilik daraxt . Oxirgi darajadan tashqari barcha darajalar to'liq to'ldirilgan
va barcha tugunlar chapdan o'ngga to'ldirilgan ikkilik daraxt.
Zo'r ikkitomonlama daraxt . Ichki tugunlari va ildiz tugunida 2 ta bola va
barchasi bir xil darajada bo'lgan ikkitomonlama daraxt.
Balanslangan ikkilik daraxt. Ikki daraxt, uning chap balandligi h1 va o'ng pastki
daraxt balandligi h2 | h1-h2 | <= 1.
Patologik ikkilamchi daraxt (egri chiziqli) BT / degeneratsiya BT). Barcha
ichki tugunlarida bittadan farzandi bo'lgan Ikkilik daraxt chap bolada bo'lishi mumkin
yoki u to'g'ri bola bo'lishi mumkin.
Eslatma: Patologik BT balandligi: Tugunlar soni-1 .
Psevdokoddagi quyidagi daraxtlarni saralash algoritmi a ni qabul
qiladi taqqoslanadigan narsalar to'plami va narsalarni ortib boruvchi tartibda
chiqaradi:
CONSTRUCTION BinaryTree BinaryTree:
LeftSubTree Object:
Node BinaryTree:
Add RightSubTreeTARTIBI (BinaryTree: searchTree, Object: item)
IF searchTree.Node IS NULL Then Install searchTree.
Node TO element Search other than IF element UND.

22'tumor (searchTree.LeftSubTree, element) OTHER ADDITION
(searchTree.RightSubTree, element) ORDER InOrder (BinaryTree: searchTree) IF
searchTree.
Node IS NULL Then Exit Mode OTHER InOrder (searchTree.LeftSubTode)
Search .RightSubTree) PROCEDURE TreeSort (Collection: data) BinaryTree:
searchTree INSERTED INSERT INDIVIDUAL IN INDIVIDUAL (searchTree,
individualItem) InOrder (searchTree)
Oddiy funktsional dasturlash shakl, algoritm (in.) Xaskell) shunga o'xshash bo'lar
edi:
data Tree a = Leaf |
Knot (Tree a) a (Tree a) insert :: Ord a => a -> Tree a -> Tree |
x <= y = Node (insert x t) y s |
x> y = Knot t y (insert x s) leveling :: Tree a -> [a] leveling Leaf = [] leveling
(Knot t x s) = leveling t ++ [x] ++ leveling trees :: Ord a => [a ] -> [a] trees =
leveling. folding leaf
Yuqoridagi dasturda qo'shish algoritmi ham, qidirish algoritmi ham mavjud O(n²)
eng yomon stsenariylar.
Tilman Vogel ta'kidlaganidek, kirish ma'lumotlari bo'yicha muayyan cheklovlarni
joriy qilish orqali nazariy ravishda (n log (log n)) murakkabligi bilan ishlaydigan
algoritmlar mavjud. Aksariyat amaliy ilovalarda katta foyda keltirishi ehtimoldan
yiroq emas , ehtimol, nima uchun men hech qachon amalga oshirishni ko'rmaganman,
lekin agar ular sizning ishlatishingizga mos keladigan bo'lsa, men ushbu
algoritmlarning tezkorligini tezroq ko'rishni juda xohlayman.
Ikkilik daraxt va ikkilik qidiruv daraxti turlari - "Ikkilamchi daraxt", "to'liq binar
daraxt", "mukammal binar daraxti" va "kengaytirilgan ikkitali daraxt" kabi turli xil
turlari mavjud. Ikkilamchi qidirish daraxtlarining ba'zi keng tarqalgan turlari orasida
daraxtlar, AVL daraxtlari , splay daraxtlari, tanang daraxtlari , qizil-qora daraxtlar va
boshqalar mavjud.

$232.2. Ikkilik daraxtlarning o’tishi. Ikkilik daraxtning takroriy inorder orqali o'tishi. "Ikkilik daraxtning takroriy tartibsiz o'tishi" masalasida bizga a ikkilik daraxt. Biz uni noaniq uslubda bosib o'tishimiz kerak "Takroriy", rekursiyasiz. Misolni yechish strukturasi:  Algoritm :  Izoh :  amalga oshirish :  C ++ Ikkilik daraxtning takroriy inorder o'tish dasturi  Ikkilik daraxtni takroriy inorder traversalining Java dasturi  Murakkablikni tahlil qilish  Ikkilik daraxtning takroriy inorder o'tish vaqtining murakkabligi  Ikkilik daraxtning takroriy inorder o'tishining kosmik murakkabligi Misol. 2 / \ 1 3 / \ 4 5 4 1 5 2 3 1 / \ 2 3 / \ 4 6$ $24\ 7 4 2 1 3 6 7 Algoritm. O'zgaruvchini boshlang "CurNode" ikkilik daraxtning ildizi sifatida bo'sh to'plamni ishga tushiring, tugunlarni o'z ichiga olgan ular bosib o'tgani kabi: 3. Do not curNode until the stack is empty or as follows NULL: There is no curNode in the NULL: 1. Durang curNode bone 2. Change the current node and continue to go to the leftmost curNode = curNode-> left. Endi to'plamdagi yuqori tugun joriy subtree tugmachasining eng chap tugunidir, shuning uchun biz ustundagi tugunning qiymatini stakka chiqaramiz Belgilash curNode sifatida to'plamdagi yuqori tugunning o'ng farzandi sifatida curNode = stack.top () -> o'ng Joriy tugunni o'zgartirib, eng chap bolaga borishda davom eting curNode = curNode-> chap ushbu chap tugunning o'ng pastki daraxtini qayta ishlash uchun. Dastur stek eng so'nggi qo'shilgan elementni chiqarib tashlaydi degan fikrdan foydalanadi, Yuqorida tushuntirilgan algoritmda biz shunchaki joriy tugun (dastlab daraxt ) chap bolasi bor, keyin chap bolasi qolmaguncha chap bolasini stakka itaramiz. Agar hozirgi tugunda chap bolasi bo'lmasligi kerak bo'lsa, to'plamdagi yuqori tugun "So'nggi chap tugun" qo'shildi. Shunday qilib, o'tishning qolgan tartibida birinchi o'rinda turishi kerak. Shunday qilib, biz uni buyurtma ro'yxatiga chop etishni / qo'shishni boshlaymiz va uni to'plamdan chiqaramiz. Bir marta amalga oshirilgandan so'ng, biz hozir haqiqat haqida aniqmiz Chap tomonga tugun-o'ng (inorder ketma-ketligi), chap va Node qismi bosib o'tilgan. Shunday qilib, tugunning o'ng pastki daraxti jarayonga kiradi! Intuitiv ravishda, xuddi shu jarayonni joriy tugunning o'ng pastki daraxtiga qo'llamoqchimiz, biz uni quyidagicha umumlashtirishimiz mumkin: curNode = curNode-> right.$

25C ++ Ikkilik daraxtning takroriy inorder o'tish dasturi
#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
int value;
treeNode *left , *right;
treeNode(int x)
{
value = x;
left = NULL;
right = NULL;
}
};
void iterativeInorder(treeNode* root)
{
stack <treeNode*> ;
treeNode* curNode = root;elements
while(curNode != NULL || !elements.empty())
{
while(curNode != NULL)
{
elements.push(curNode);
curNode = curNode->left;
}
cout << elements.top()->value << " ";
curNode = elements.top()->right;
elements.pop();

26}
}
int main()
{
treeNode* root = new treeNode(2);
root->left = new treeNode(1);
root->right = new treeNode(3);
root->left->left = new treeNode(4);
root->left->right = new treeNode(5);
iterativeInorder(root);
cout << endl;
return 0;
}
Ikkilik daraxtni takroriy inorder traversalining Java dasturi
import java.util.Stack;
class treeNode
{
int value;
treeNode left, right;
public treeNode(int x)
{
value= x;
left = right = null;
}
}
class Tree
{
treeNode root;
void iterativeInorder()
{

27Stack<treeNode> elements = new Stack<treeNode>();
treeNode curNode = root;
while (curNode != null || !elements.empty())
{
while (curNode != null)
{
elements.push(curNode);
curNode = curNode.left;
}
curNode = elements.peek().right;
System.out.print(elements.peek().value + " ");
elements.pop();
}
}
public static void main(String args[])
{
Tree tree = new Tree();
tree.root = new treeNode(2);
tree.root.left = new treeNode(1);
tree.root.left.left = new treeNode(4);
tree.root.left.right = new treeNode(5);
tree.root.right = new treeNode(3);
tree.iterativeInorder();
}
}
Murakkablikni tahlil qilish, v aqtning murakkabligi . Vaqtning murakkabligi O
(N), har bir tugunga aniq bir marta tashrif buyurganimizda. Bu erda, N - ikkilik
daraxtdagi tugunlar soni.

28Kosmik murakkablik . K osmik murakkablik O (N). Daraxt egri bo'lishi mumkin
bo'lgan eng yomon holatni hisobga olsak, kosmik murakkablik ikkitomonlama
daraxtdagi tugunlar soniga teng bo'ladi .
Binar daraxtlarni qurish . Binar daraxtda har bir tugun-elementdan ko’pi bilan 2
ta shox chiqadi. Daraxtlarni xotirada tasvirlashda uning ildizini ko’rsatuvchi
ko’rsatkich berilishi kerak. Daraxtlarni kompyuter xotirasida tasvirlanishiga ko’ra har
bir element (binar daraxt tuguni) to’rtta maydonga ega yozuv shaklida bo’ladi,
ya’ni kalit maydon , informatsion maydon , ushbu elementni o’ngida va chapida
joylashgan elementlarning xotiradagi adreslari saqlanadigan maydonlar.
Shuni esda tutish lozimki , daraxt hosil qilinayotganda , otaga nisbatan chap
tomondagi o’g’il qiymati kichik kalitga , o’ng tomondagi o’g’il esa katta qiymatli
kalitga ega bo’ladi. Har safar daraxtga yangi element kelib qo’shilayotganda u
avvalambor daraxt ildizi bilan solishtiriladi. Agar element ildiz kalit qiymatidan
kichik bo’lsa, uning chap shoxiga , aks holda o’ng shoxiga o’tiladi. Agar o’tib ketilgan
shoxda tugun mavjud bo’lsa, ushbu tugun bilan ham solishtirish amalga oshiriladi , aks
holda , ya’ni u shoxda tugun mavjud bo’lmasa, bu element shu tugunga joylashtiriladi.
Masalan, daraxt tugunlari quyidagi qiymatlarga ega 6, 21, 48, 49, 52, 86, 101. U
holda binar daraxt ko’rinishi quyidagi 4.1-rasmdagidek bo’ladi:
Natijada, o’ng va chap qism daraxtlari bir xil bosqichli tartiblangan binar daraxt
hosil qildik. Agar daraxtning o’ng va chap qism daraxtlari bosqichlarining farqi
birdan kichik bo’lsa, bunday daraxt ideal muvozanatlangan daraxt deyiladi. Yuqorida
hosil qilgan binar daraxtimiz ideal muvozanatlangan daraxtga misol bo’ladi. Daraxtni
muvozanatlash algoritmini sal keyinroq ko’rib chiqamiz. Undan oldin binar daraxtni
yaratish algoritmini o’rganamiz.

292.3. Ikkilik daraxtlarga misollar.
Endi G sirtmoqsiz va karrali qirralari bo‘lmagan m ta uch, n ta qirra va &ta
bog‘lamli komponentlardan tashkil topgan graf bo‘lsin. Agar yuqorida tavsiflangan
usul yordamida G grafdan qirralarni ketma-ket olib tashlash amalini qo‘llash
natijasida uning har bir komponenti bog'lamliligi buzilmasa, u holda berilgan G
grafning sinch o‘rmoni deb ataluvchi grafni hosil qilish mumkin. Berilgan G grafdan
uning sinch o‘rmonini hosil qilish maqsadida olib tashlanishi kerak bo‘lgan qirralar
soni Я = Я (G) bu qirralarni olib tashlash tartibiga bog‘liq emasligi va X = n — m + k
bo‘lishi ravshandir. Qaralayotgan G graf uchun m — k < n tengsizlik o‘rinli
bo‘lganligidan, Я ( С )>0 bo'ladi. k{G) sonni G grafning siklomatik soni (siklik rangi)
deb ataymiz. Grafning siklomatik soni tushunchasi, qandaydir ma’noda, grafning
bog'lamlilik darajasini aniqlovchi vositadir. Ravshanki, daraxt uchun Я = 0 bo‘ladi (1-
teoremaga qarang). 3- shakl Grafning o ‘rmon bo‘lishi uchun uning siklomatik soni
nolga teng bo‘lishi zarur va yetarlidir (2- natijaga qarang). Grafning yagona siklga
ega bo'lishi uchun uning siklomatik soni birga teng bo'lishi zarur va yetarlidir.
Qirralari soni uchlari sonidan kichik bo‘lmagan graf siklga egadir. Bu tasdiqlar ham
1- teoremaning natijalaridir.
3- m i sol. 3- shaklda tasvirlangan graf (6 ,9 )-graf bo‘lib, uning bog‘lamlilik
komponentlari soni birga teng. Bu grafning siklomatik sonini aniqlasak, A = 9 — 6 +
1 = 4 boiadi. Olib tashlangan qirralar 3- shaklda ingichka chiziqlar bilan ifodalangan.
Binar daraxt elementining tuzilishi . p – yangi element ko’rsatkichi
next, last – ishchi ko’rsatkichlar, ya’ni joriy elementdan keyingi va oldingi elementlar
ko’rsatkichlari:
r=rec – element haqidagi birorta ma’lumot yoziladigan maydon.
k=key – elementning unikal kalit maydoni .

30left=NULL – joriy elementning chap tomonida joylashgan element adresi.
right=NULL – joriy elementning o’ng tomonida joylashgan element adresi.
Dastlab yangi element hosil qilinayotganda bu ikkala maydonning qiymati 0 ga
teng bo’ladi.
tree – daraxt ildizi ko’rsatkichi.
n – daraxtdagi elementlar soni .
Boshida birinchi kalit qiymat va yozuv maydoni ma’lumotlari kiritiladi, element
hosil qilinadi va u daraxt ildiziga joylashadi , ya’ni tree ga o’zlashtiriladi. Har bir hosil
qilingan yangi elementning left va right maydonlari qiymati 0 ga tenglashtiriladi.
Chunki bu element daraxtga terminal tugun sifatida joylashtiriladi, hali uning farzand
tugunlari mavjud emas. Qolgan elementlar ham shu kabi hosil qilinib , kerakli joyga
joylashtiriladi. Ya’ni kalit qiymati ildiz kalit qiymatidan kichik bo’lgan elementlar
chap shoxga, katta elementlar o’ng tomonga joylashtiriladi. Bunda agar yangi element
birorta elementning u yoki bu tomoniga joylashishi kerak bo’lsa, mos ravishda left
yoki right maydonlarga yangi element adresi yozib qo’yiladi.
Binar daraxtni hosil qilishda har bir element yuqorida ko’rsatilgan toifada bo’lishi
kerak. Lekin hozir biz o’zlashtirish osonroq va tushunarli bo’lishi uchun key va rec
maydonlarni bitta qilib info maydon deb ishlatamiz.
Ushbu toifada element hosil qilish uchun oldin bu toifani yaratib olishimiz kerak.
Uni turli usullar bilan amalga oshirish mumkin. Masalan, node nomli yangi toifa
yaratamiz:
class node{
public:
int info;
node *left;
node *right;
};

31Endi yuqoridagi belgilashlarda keltirilgan ko’rsatkichlarni shu toifada yaratib
olamiz:
node *tree=NULL;
node *next=NULL;
int n,key; cout<<"n=";cin>>n;
Nechta element (n) kiritilishini aniqlab oldik va endi har bir element qiymatini
kiritib , binar daraxt tuzishni boshlaymiz.
for(int i=0;i<n;i++){
< i=""> node *p=new node;
node *last=new node;
cin>>key;
p->info=key;
p->left=NULL;
p->right=NULL;
if(i==0){ tree=p; next=tree;continue;}
next=tree;
while(1){ last=next;
if(p->infoinfo) next=next->left; else next=next->right;
if(next==NULL) break;
}
if(p->infoinfo) last->left=p; else last->right=p;
}
Bu yerda p hali aytganimizdek , kiritilgan kalitga mos hosil qilingan yangi
element ko’rsatkichi, next yangi element joylashishi kerak bo’lgan joyga olib
boradigan shox adresi ko’rsatkichi, ya’ni u har doim p dan bitta qadam oldinda
yuradi , last esa ko’rilayotgan element kimning avlodi ekanligini bildiradi , ya’ni u har
doim p dan bir qadam orqada yuradi.

32Shunday qilib binar daraxtini ham yaratib oldik. Endigi masala uni ekranda
tasvirlash kerak, ya’ni u ko’rikdan o’tkaziladi yoki vizuallashtirsa ham bo’ladi.
Xulosa.
Xulosam shundan iboratki ushbu “Daraxtlar, Ikki tomonlama daraxtlar, Ikkilik
daraxtlarning vakilligi, Ikkilik daraxtlarning o’tishi” mavzusini birmuncha kengroq
yoritilgan. Dastavval daraxtlar haqida qisqacha tushuncha yani daraxtlarning tarifi,
qachondan boshlab foydalanila boshlagan, daraxtlarning tuzilish tartibi va uning
tarkibidagi bir qancha tushunchalarni tasniflangan. Shu jumladan ikkitalik
daraxtlar ularning vakilligi va o’tishiga nazariy shu jumladan amaliy ravishda
malumot berib o’tilgan. Kurs ishi so’ngida umumiy qilib aytganda daraxtlarga doir
misollar keltirib o’tilgan. Misollarni keltirishda asosan C++ va Java dasturlash
tillaridan foydalanilgan. Istalgan daraxtning markazi uning bitta uchidan yoki ikkita
qo 'shni uchlaridan iborat bo 'ladi. Ikkilik qidiruv daraxtiga bitta element qo'shilishi
o'rtacha O(log n) jarayon. N ta elementni qo'shish - bu O(n jurnal n) jarayon,
daraxtlarni saralashni "tez saralash" jarayoniga aylantirish. Balanssiz ikkilik
daraxtga element qo'shishni talab qiladi O(n) eng yomon holatda vaqt: qachon
daraxt a ga o'xshaydi bog'langan ro'yxat (buzilib ketgan daraxt).
Agar daraxtning o`ng va chap qism daraxtlari bosqiclari orasida farq 1 dan katta
bo`lmasa, u holda bunday binary daraxt muvozanatlangan daraxt deyiladi . Agar
daraxtni tashkil etuvchi element(tugun)lardan ko`pi bilan 2ta shox chiqsa, yani har
bir tugun tuzilmaning ko`pi bilan 2ta tuguni bilan bog`langan bo`lsa, u holda bunday
daraxt binar daraxt deyiladi.

33Foydalanilgan adabiyotlar
"Meet the 'Refrigerator Ladies' Who Programmed the ENIAC". Aqliy ip. 2013-10-
13. Olingan 2016-06-16.
Lor, Stiv (2001 yil 17-dekabr). "Frensis E. Xolberton, 84 yosh, erta kompyuter
dasturchisi". NYTimes. Olingan 16 dekabr 2014.·
Demuth, Howard B. (1956). Electronic Data Sorting (Doktorlik dissertatsiyasi).
Stenford universiteti. ProQuest 301940891.·
Kormen, Tomas H.; Leyzerson, Charlz E.; Rivest, Ronald
L.; Shteyn, Klifford (2009), "8", Algoritmlarga kirish (3rd ed.), Cambridge ,
MA: The MIT Press , p. 167, ISBN 978-0-262-03293-3·
Sedgewick, Robert (1 sentyabr 1998 yil). Algorithms In C: Fundamentals , Data
Structures , Sorting, Searching , Parts 1-4 (3 nashr). Pearson ta'limi. ISBN 978-81-
317-1291-7. Olingan 27 noyabr 2012.
Sedgewick, R. (1978). "Implementing Quicksort programs". Kom. ACM. 21 (10):
847–857. doi:10.1145/359619.359631.
Foydalanilgan saytlar
 https://en.wikipedia.org/wiki/Database_System_Concepts
 http:// www.tuit.uz
 http://library.ziyonet.uz/uz/book/7107
 https://tami.uz/matnga_qarang.php?id=965
 https://uz.wikipedia.org/wiki/Davlatlar_ro%CA%BByxati


2“Dataxtlar, ikki tomonlama daraxtlar, ikkilik daraxtlarning vakilligi, ikkilik daraxtlarning o’tishi” MUNDARIJA Kirish ……………………………………... …………………………….……..…….3 I. NAZARIY QISM 1.1. Daraxtlar haqida ma’lumot…………………………………………..….…….4 1.2. Ikki tomonlama daraxtlar …………………………………………..…….…..14 II. AMALIY QISM 2.1. Ikkilik daraxtlarning vakili .............................................… ……………...… …21 2.2. Ikkilik daraxtlarning o’tishi ………………………………………………...….23 2.3. Ikkilik daraxtlarga misollar…………………………………………….……...29 Xulosa ……………………………………………………………………….….….32 Foydalanilgan adabiyotlar ………………….……………………………….……33

3 Kirish. Ko'pchilik uchun "algoritm" so'zi maktab matematikasi bilan yoqimsiz aloqalarni keltirib chiqaradi. Darhaqiqat, algoritmlar dasturlashda qo'llanila boshlanganidan ancha oldin odamlar ulardan foydalanishni boshladilar va ularning faoliyat sohasi faqat matematika bilan cheklanmaydi. Non pishirganda, siz retseptdan foydalanasiz va shuning uchun algoritmga amal qilasiz. Algoritmlar tosh davridan beri inson hayotining ajralmas qismi bo'lib kelgan. Mualliflar kognitiv fan, matematika va iqtisod sohalaridagi fanlararo tadqiqotlar bilan yaxshi tanish. Himoya qilishdan oldin tezis tadqiqotda ingliz tilidan, Brayan o'qigan Kompyuter texnologiyalari va falsafani o'rgandi va har uch mutaxassislik chorrahasida martaba qurdi. Tom Berklidagi Kaliforniya universitetida professor bo'lishdan oldin psixologiya va statistikani o'rganish bilan ko'p yillar davomida shug'ullangan va u erda deyarli barcha vaqtini insonning aqliy faoliyati va hisoblash operatsiyalari o'rtasidagi munosabatlarni o'rganishga bag'ishlaydi. Bundan tashqari, hayot uchun algoritmlarni qidirishda mualliflar so'nggi 50 yil ichida eng mashhur algoritmlarni ishlab chiqqan odamlar bilan suhbatlashdi. Va ular o'zlarining tadqiqotlari hayotiy muammolarni hal qilishda yondashuvlariga qanday ta'sir qilganini so'rashdi. Zero, u aytganidek, “ilm shunchaki bilimlar majmuasidan ko‘ra ko‘proq ma’lum fikrlash tarzidir”. Har bir inson har kuni juda ko'p muammolarga duch keladi, eng oddiy va eng ma'lum bo'lganidan tortib eng qiyinigacha. Ko'pgina vazifalar uchun ijrochiga ushbu vazifani qanday hal qilishni tushuntiradigan muayyan qoidalar (ko'rsatmalar, retseptlar) mavjud. Inson ushbu qoidalarni oldindan o'rganishi yoki muammoni hal qilish jarayonida o'zini shakllantirishi mumkin. Muammolarni hal qilish qoidalari qanchalik to`g`ri va aniq tasvirlangan bo`lsa, odam ularni shunchalik tez o`zlashtiradi va qo`llashda samaraliroq bo`ladi. Inson ko'plab vazifalarning echimini texnik qurilmalarga - avtomatik mashinalarga, robotlarga, kompyuterlarga o'tkazishi mumkin.

41.1. Daraxtlar haqida malumot . Algoritmlarning daraxtlar bilan ishlash samaradorligi . "Daraxtlar - rekursiv algoritmlar" va "makon-vaqt" juftligi o'rtasida o'xshashliklarni yaratish mumkin. Rekursiv dastur ishlayotganda funktsiya chaqiruv daraxti o'z vaqtida kengaytiriladi va daraxt ma'lumotlar tuzilishi sifatida rekursiv algoritm bajarilishining xotirada xaritalangan natijasiga o'xshaydi. Shuning uchun rekursiv algoritmlarning samaradorligi to'g'risidagi xulosalar daraxtlarga taalluqlidir: - daraxtning to'liq rekursiv o'tishi chiziqli; - samarali ochko'zlik algoritmlari. Daraxtga nisbatan ochko'zlik har bir tepada bitta bolani tanlashdan iborat. Rekursiv chaqiruv davri o'rniga, barcha avlodlar uchun bitta qo'ng'iroq bo'lishi kerak. Siz har bir qadamda tanlangan bolaga borib, rekursiv algoritmni dumaloq algoritm bilan almashtirishingiz mumkin. Aniq uchun asosochko'z tanlov - daraxtga ortiqcha narsalarni kiritish (tepalikdagi qo'shimcha ma'lumotlar) yoki undagi ma'lumotlarni buyurtma qilish. Daraxtlarning to'liq rekursiv o'tishiga asoslangan algoritmlar. Dastlab, daraxtda ma'lumotlar qanday tashkil qilinganligidan qat'i nazar, eng oddiy algoritmlarni ko'rib chiqamiz. Daraxtning to'liq rekursiv o'tishi daraxtning barcha tepalarini bosib o'tishni va butun daraxt tuzilishining umumiy xususiyatlarini olishdan iborat. Siz darhol bypass natijasini shakllantirishning texnologik usullari haqida to'xtalishingiz kerak: - rekursiv funktsiyani aniq natijasi rekursiv funktsiyadan tushadigan zanjirning bajarilishi paytida uning to'planishini nazarda tutadi (ya'ni, natijaning to'planishi teskari yo'nalishda - avlodlardan ajdodgacha). Bundan tashqari , har bir tepalik, avlodlardan olingan natijalarni o'ziga xos "malhamda uchib" qiladi, ya'ni. subtrees natijalarini o'zi bilan birlashtiradi; - rekursiv chaqiriqlar zanjiri bo'ylab uzatiladigan rasmiy parametr - zvenodan foydalanish mumkin. Bunday holda, barcha rekursiv chaqiriqlar natijani to'plash

5uchun ishlatiladigan global ma'lumotlarning rolini o'ynaydigan umumiy o'zgaruvchiga ishora qiladi. Ro'yxatlar va massivlar bilan dastlabki taqqoslash. Daraxtdagi ma'lumotlarni tashkil qilish tafsilotlariga kirmasdan ham , biz uchun ma'lum bo'lgan uning vakili shakllariga asoslanib, dastlabki xulosalar chiqarishimiz mumkin. Birinchidan, ichidaAlgoritmik ravishda daraxt taniqli so'zlarni "o'rmonga - ko'proq o'tin" ga amal qiladi. Bu holda "o'tin" bu daraxtning "chuqurligi" o'sishi bilan sonning eksponent o'sishi bo'lgan tepalardir. Agar bir vaqtning o'zida "ortiqcha" daraxtlarni kesishni samarali tashkil etish imkoniyati mavjud bo'lsa, unda elementlarni qiymatlari bo'yicha topish va ularga mantiqiy raqamlar bo'yicha kirishning samarali algoritmlariga umid qilish mumkin. Bu erda ro'yxatlarga nisbatan aniq ustunlik mavjud, bu erda barcha algoritmlar to'liq qidirishga asoslangan (chiziqli qidirish). Ikkinchidan, texnologik jihatdantepaliklarning tartibini yoki daraxtlarga joylashishini o'zgartirish, ro'yxatlarda bo'lgani kabi, alohida tepalardagi bog'lanishlarni (filiallarni) qayta tashkil etish orqali ham amalga oshirilishi mumkin. Bu elementlarning massiv harakatini (siljishini) talab qiladigan massivlarga nisbatan aniq ustunlikka ega. Shunday qilib, samaradorlik nuqtai nazaridan daraxt bu ikkita haddan tashqari: qator va ro'yxat o'rtasidagi kelishuvdir. Muvozanat kabi xarakterli daraxtni tanishtiramiz.Balans daraxt shoxlari uzunliklarida tarqalishini xarakterlaydi. Aniqrog'i, biz ildiz shoxidan tepalikka qadar erkin shox bilan masofalar haqida gapiramiz. Maksimal va minimal novdalar uzunligi 1dan ko'p bo'lmagan farq qilsa , daraxt muvozanatli deb ataladi, bunday daraxt novdaning uzunligi bilan daraxtning tepalari soni o'rtasidagi eksponent (yoki teskari, logaritmik) bog'liqlik bilan tavsiflanadi : N = 1 + m + m 2 + m 3 +… + m L < m L , L <log m N Eng yomon holatda, har bir tepada bittadan bola bo'lsa, daraxt tanazzulga uchraydi , bu holda novdalar uzunligi 1 ga teng bo'lmagan tepalar soniga teng bo'ladi. Bundan tashqari, bir martalik o'qqa asoslangan barcha algoritmlar, to'liq rekursiv o'tish, chiziqli murakkablikka ega bo'ladiT = N . Ularning yaxshilanishi faqatgina

6"botirish chuqurligini" cheklashdan iborat bo'lishi mumkin, agar buning uchun etarli asoslar mavjud bo'lsa. Yana bir narsa shundaki , unga asoslangan algoritmlardallanma. Har bir tepada ular mumkin bo'lgan bolalardan faqat bittasini tanlaydilar. Bunday algoritmlar deyiladiochko'zlik ("8.7. Rekursiv algoritmlarning samaradorligi" ga qarang). Siz darhol ularning murakkabligi ular tanlagan daraxt novdasi uzunligiga teng ekanligini darhol ko'rishingiz mumkin. Balanslangan daraxt uchun qaramlik logaritmik bo'ladi. T = L <log m N, daraxtlar ro'yxatiga kirib borishi uchun u chiziqli. Bu erda ikkita muammo mavjud. Birinchidan, muvozanatli daraxtni saqlash. Buning ikkita echimi mavjud: - odatdagidan ancha murakkab bo'lgan daraxt muvozanatini saqlaydigan algoritmlardan foydalanish, chunki ular qo'shni daraxtlar vertikallari guruhlarining turli xil topologik transformatsiyalaridan foydalanadilar (bundan tashqari, rekursiv); - daraxtning davriy hizalanishi (muvozanati), ehtimol qo'shimcha ma'lumotlar tuzilishi yordamida. Ushbu echim daraxt bilan ishlash uchun oddiy algoritmlardan foydalanishga imkon beradi , lekin uning muvozanatini kuzatishni talab qiladi (xuddi shu algoritmlar buni amalga oshirishi mumkinligiga e'tibor bering, masalan, ma'lum bir qiymatni qidirishda filial uzunligini aniqlash). Balanslash protsedurasi ancha vaqt talab qilishi mumkin , ammo bu nisbatan kamdan-kam hollarda deyiladi. Kundalik darajada ushbu alternativani "ideal tartib yoki davriy umumiy tozalash " sifatida shakllantirish mumkin . Shunga o'xshash holat har qanday dinamik resurslarni taqsimlash va ulardan foydalanish tizimida uchraydi: dinamik xotirani ajratish tizimida (2.6), ikkilik faylni rejalashtirishda (9.2), operatsion tizimning fayllarni boshqarish tizimida, u o'xshash echimlarga ega. Ikkinchi muammo algoritmda har bir tepada bitta avlodni aniq tanlash uchun asoslar yotadi (badiiy o'xshashlik - "chorrahada ritsar"). Bu erda yana ikkita yondashuv mavjud: - tepada qo'shimcha (ortiqcha) ma'lumotlarning mavjudligi , bu "bu erda va

Dataxtlar, ikki tomonlama daraxtlar, ikkilik daraxtlarning vakilligi, ikkilik daraxtlarning o’tishi

12.08.2023

0

58.9853515625 KB

Похожие