Тема: Структуры данных: деревья, бинарное дерево

Mavzu: Daraxtsimon ma’lumotlar tuzilmalari. Binar va ko’ptarmoqli daraxtlar.

• Reja:
• Binar daraxt to’g’risida tushuncha.
• Binar qidiruv daraxti tushunchasi.
• Binar daraxtlarni qurish.
• Binar daraxtlar ustuda amallar.

Ikkilik (binar) daraxt

• Ta’rif 1. Ko'pi bilan ikkita tugundan iborat bo'lgan ierarxik ma'lumotlar tuzilmasiga binar (yoki ikkilik) daraxt deb ataladi.
• Har bir tugun "chap" ko'rsatkichga, "o'ng" ko'rsatkichga va ma'lumotlar elementlarini o'z ichiga oladi.
• "Ildiz" ko'rsatkichi daraxtning eng yuqori tugunini anglatadi.

Ikkilik daraxt — har bir tuguni ikkitadan ko’p tugunega bo’lmagan iyerarxik ma’lumotlar tuzilmasidir. Odatda har bir asosiy tugunlar chap va o’ng yoki aloxida tugunlardan tashkil topadi va vorislar deb yuritiladi.

• Ikkilik daraxt — har bir tuguni ikkitadan ko’p tugunega bo’lmagan iyerarxik ma’lumotlar tuzilmasidir. Odatda har bir asosiy tugunlar chap va o’ng yoki aloxida tugunlardan tashkil topadi va vorislar deb yuritiladi.
• Binar daraxt— Bu iyerarxik ma’lumotlar tuzilmasi bo’lib, bunda har bir tugun o’z qiymatiga va ikkita (chap va o’ng) ko’rsatgichiga yani vorisga ega bo’ladi.
• Eng yuqori o’rinda joylashgan tugunga daraxt ildizi (yoki asosi) deb yuritiladi.
• Vorisga ega bo’lmagan tugunlarga daraxt barglari deb yuritiladi.

Рис. 1 Бинарное дерево

Binar qidiruv daraxti.

Binar qidiruv daraxti.

Binar qidiruv daraxti deb qo’shimcha hususiyatlarga ega bo’lgan daraxtga aytiladi.

Bu hususiyatlar quyidagicha:

• Chap vorisning qiymati shu “ota” qiymatidan kichik,
• O’ng vorisning qiymati shu “ota” qiymatidan katta.

Aniq qilib aytadigan bo’lsak binary qidiruv daraxt tuzilmasi qatiiy tartiblangan shaklda saqlanadi.