Ma’lumotlar tuzilmasi va algoritmlar 13-ma’ruza: Daraxtsimon ma’lumotlar tuzilmasi

Binar daraxt tushunchasi

Binar daraxt – har bir tugunga ikkitadan ko’p bo’lmagan tugunlar bog’langan tartiblangan daraxt.

• ::= ( ) |
• ::=
• ::=

Binar daraxt tushunchasi

Umumiy holda binar daraxtning har bir elementi (tuguni) to’rtta maydonga ega yozuvdan tashkil topgan bo’ladi.

Binar daraxt tushunchasi

• Shuni esda tutish lozimki, binar daraxt hosil qilinayotganda, otaga nisbatan chap tomondagi o’g’il qiymati kichik, o’ng tomondagi o’g’il qiymati katta bo’lishi lozim.

Masalan, quyidagi kalitli elementlardan binar daraxt quramiz:

{50, 46, 61, 48, 29, 55, 79}. U quyidagi ko’rinishga ega bo’ladi:

Muvozanatlashgan binar daraxt

• Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari va tugunlari soni teng bo’lsa, u holda bunday binar daraxt ideal muvozanatlashgan daraxt deyiladi.
• Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari orasidagi farq birdan katta bo’lmasa, u holda bunday binar daraxt muvozanatlashgan daraxt deyiladi. Masalan,

Daraxtni binar daraxt ko’rinishida tasvirlash

Ko’p o’lchamli daraxtni binar ko’rinishga keltirishning noformal algoritmi:

• Daraxtning xar bir tugunida katta o’g’ilga mos chetki chap shoxidan tashqari barcha shoxlari kesib tashlanadi.
• Bitta otaga barcha o’g’illari gorizontal chiziq bilan ulanadi.
• Hosil qilingan tuzilmaning har bir tugunida katta o’g’il mazkur tugun pastida turgan tugun xisoblanadi (agar u mavjud bo’lsa).

Daraxtni binar daraxt ko’rinishida tasvirlash

Bu algoritm amallar ketma-ketligi quyida keltirilgan

Daraxtlar ustida bajariladigan amallar

• daraxtni aylanib o’tish (daraxtda o’tish) (bunda, asosan, tugunlarni chop etish tushuniladi);
• daraxtga yangi tugun qo’yish;
• daraxt tugunini o’chirish;
• daraxt tugunini qidirish.