36
aniqlanganidan so’ng olingan ixtiyoriy daraxt binar daraxtga keltiriladi. Bunda
quyidagi tarzda ish ko’riladi. Har bir yaratuvchi bo’g’im uchun undan chiquvchi
eng chapdagisidan tashqari barcha qirralar yo’qotiladi. O’sha
darajaning barcha
«ajralib chiqqan» yaratilganlari «...ga o’xshash» ko’rsatkichlar bilan chapdagi
yaratilganga bog’lanadi. 5.8-chizma ixtiyoriy daraxtsimon tuzilmani ko’rsatkichlar
yordamida tuzilmaning yaratilgan va o’xshash elementlarida ikkilik daraxt
ko’rinishida taqdim etishni namoyish etadi.
Ikkilik daraxtda yo’nalishlarga ma’lum mantiqiy ma’nosi qarshi qo’yilishi
mumkin. Masalan, ko’pincha chap yo’nalish yaratuvchi bo’g’imdagi yozuvga
qaraganda kichikroq qiymatdagi kalitli yozuv joylashgan bo’g’imga
olib boradi
deb, o’ng yo’nalish esa kattaroq kalitga ega yozuvli bo’g’imga olib boradi deb
qabul qilinadi. Faqat yozuvlarni kalit polyalarining qiymatini ko’rsatgan holda
shunday daraxtni quramiz. Yozuvlar qayta ishlashga quyidagi ketma-ketlikda
berilsin: 21, 7, 33, 38, 19, 100, 36, 63, 180, 51, 290, 260, 286.
Birinchi yozuv
daraxt ildiziga joylashtiriladi, qolganlari qabul qilingan yo’nalishlar mantiqiga
muvofiq joylashadi. Saflanish natijasida 5.9-chizmada ifodalangan daraxt hosil
bo’ladi. Bunday daraxtda zarur qiymatdagi kalitli yozuvni
izlash quyidagi qoida
bo’yicha amalga oshiriladi: agar izlanayotgan kalit ushbu bo’g’im kalitidan
kichik
bo’lsa, bu bo’g’imdan chapga qarab harakat qilish lozim bo’ladi, agar
1.2.3.6
-chizma. Ixtiyoriy ikkilik daraxti
37
izlanayotgan kalit katta bo’lsa, harakatni o’ng yo’nalishda davom ettirish lozim
bo’ladi.
Ma’lumotlarni qayta ishlashning turli protseduralarini bajarish uchun
simmetrik daraxtlar eng qulay hisoblanadi. 5.9-chizmada olingan daraxt simmetrik
emasligi ko’rinib turibdi. Simmetrik daraxtni
qurish uchun ikki bosqichda
bajariladigan boshlang’ich ketma-ketlikni dastlabki qayta ishlash zarur bo’ladi.
Birinchi bosqichda yozuvlarning boshlang’ich ketma-ketligi kalit polyalar
qiymatlarining o’sib borishi yoki kamayib borishi bo’yicha tartibga solinadi.
Ikkinchi bosqichda daraxtni turli darajalarining bo’g’imlarida joylashtiriladigan
kalitlar aniqlanadi. Ildiz bo’g’imda tartibga solingan ketma-ketlikning markazida
joylashgan va uning ikkiga bo’ladigan kalit joylashtiriladi. Ketma-ketlikning chap
va o’ng yarimlarini ikkiga bo’ladigan kalitlar mos ravishda chap va o’ng kichik
daraxtlarni ikkinchi darajasining bo’g’imlarida joylashtiriladi. Ketma-ketlikning
yangitdan olinayotgan bo’laklarini bo’lish va tegishli darajalarning kalitlarini
topish protsedurasi daraxt to’liq qurib bo’linmagunicha davom etadi.
Yuqorida ko’rib chiqilgan yozuvlar ketma-ketligini simmetrik ikkilik daraxt
ko’rinishida taqdim etamiz, buning uchun esa uni kalit qiymatlarining o’sib borishi
bo’yicha tartibga solamiz: 7, 19, 21, 33, 36, 38, 51, 63, 100, 180, 260, 286, 290. 51
qiymatiga ega kalit daraxt ildiziga joylashtiriladi. 21 yoki 33
kalitlar chap kichik
daraxtdagi, 180 yoki 260 kalitlar esa o’ng kichik daraxtdagi ikkinchi daraja
bo’g’imi bo’lishi mumkin. Bizning misolda 33 va 180 kalitlari tanlab olingan.
Boshqa darajalarning bo’g’imlari ham xuddi shu tarzda aniqlanadi. Qurish
natijasida olingan daraxt simmetrik hisoblanadi.
Simmetrik daraxt ajoyib xususiyatga ega: daraxtdagi ildizdan ixtiyoriy
joygacha bo’lgan yo’llar bir xil uzunlikka ega.
Bu uzunlik minimaldir, sababi
daraxtning balandligi minimaldir, shuning uchun bunday daraxt bo’yicha zarur
yozuvlarni izlashda ixtiyoriy boshqa daraxtga qaraganda kamroq o’qish va
taqqoslash operatsiyalari talab etiladi.
