Asosiy farq – Ikkilik daraxt va Ikkilik qidiruv daraxti
Ma'lumotlar strukturasi ma'lumotlardan unumli foydalanish uchun ularni tartibga solishning tizimli usulidir. Ma'lumotlar strukturasi yordamida ma'lumotlarni tartibga solish ish vaqtini yoki bajarish vaqtini qisqartirishi kerak. Bundan tashqari, ma'lumotlar strukturasi minimal xotira hajmini talab qilishi kerak. Ba'zan ma'lumotlar daraxt tuzilishida tartibga solinishi mumkin. Daraxt qirralar bilan bog'langan tugunni ifodalaydi. Eng yuqori tugun ildiz hisoblanadi. Har bir tugun maksimal ikkita tugunga ega bo'lishi mumkin. Ular bola tugunlari sifatida tanilgan. Asosiy tugunning chap tomonidagi tugun chap tugun, o'ngdagi tugun esa o'ng tugundir. Ikkilik daraxt va Ikkilik qidiruv daraxti ikkita daraxt ma'lumotlar tuzilmasi. Ikkilik daraxt - bu har bir ota-ona tugunida ko'pi bilan ikkita tugun bo'lishi mumkin bo'lgan ma'lumotlar strukturasi turi. Ikkilik qidiruv daraxti bu ikkilik daraxt boʻlib, chap qismda faqat asosiy tugundan kichik yoki unga teng qiymatlarga ega tugunlar, oʻngdagi esa faqat asosiy tugundan kattaroq qiymatlarga ega tugunlarni oʻz ichiga oladi. Bu asosiy farq. Massivlar kabi maʼlumotlar tuzilmalaridan farqli oʻlaroq, ikkilik daraxt va ikkilik qidiruv daraxti maʼlumotlarni saqlash uchun yuqori chegaraga ega emas.
Binary Tree nima?
Ma'lumotni daraxt strukturasida tartibga solishda daraxtning yuqori qismidagi tugun ildiz tugun deb nomlanadi. Butun daraxt uchun faqat bitta ildiz bo'lishi mumkin. Ildiz tugunidan tashqari har qanday tugunning bir chekkasi yuqoriga qarab tugungacha bo'ladi. U ota-ona tugun deb ataladi. Ota-kod ostidagi tugun uning tuguni deb ataladi. Har bir ota-ona tugunida maksimal ikkita tugun bo'lishi mumkin. Ular chap tugun va o'ng tugun deb ataladi. Hech qanday tugunsiz tugun barg tugun deb ataladi. Ikkilik daraxtda ma'lumotlarni tartibga solishning o'ziga xos usuli yo'q. Ildiz tugunidan har bir tugungacha yoʻl bor.
01-rasm: Ikkilik daraxtga misol
Yuqorida ikkilik daraxtga misol keltirilgan. Daraxt tepasida joylashgan 2-element ildiz hisoblanadi. Har bir tugun maksimal ikkita tugunga ega. Agar daraxtda halqalar bo'lsa yoki bitta tugun ikkitadan ortiq tugunni o'z ichiga olsa, uni ikkilik daraxt deb tasniflash mumkin emas. Bir tugundan ikkinchisiga o'tish uchun har doim bitta yo'l bor. 2-ildiz tugunining bola tugunlari 7 va 5 dir. Bundan tashqari, tugunning tugunlari bo'lmasligi ham mumkin. Lekin har qanday tugunda ikkitadan ortiq tugun bo'lishi mumkin emas. Ildizning o'ng elementi 5. Bu 5-element 9-tugun uchun asosiy tugundir. 4 va 11-tugunlarda hech qanday yordamchi elementlar yo'q. Shuning uchun ular barg tugunlaridir.
Iklik daraxti ma'lumotlarni ierarxik tartibda saqlash uchun ishlatiladi. Bu kompyuterning fayl tuzilishiga o'xshaydi. Massiv kabi ma'lumotlar strukturasi ma'lum miqdordagi ma'lumotlarni saqlashi mumkin. Ammo binar daraxtda tugunlar sonining yuqori chegarasi yo'q.
Ikkilik qidiruv daraxti nima?
Ikkilik qidiruv daraxti ikkilik daraxt ma'lumotlar strukturasidir. Ikkilik daraxtga o'xshab, ikkilik qidiruv daraxti ham ikkita tugunga ega bo'lishi mumkin. Ildiz tugunidan tashqari har qanday tugunning bir chekkasi yuqoriga qarab tugungacha bo'ladi. U ota-ona tugun deb ataladi. Berilganning ostidagi qirrasi bilan pastga bog'langan tugun uning tuguni deb ataladi. Hech qanday tugunsiz tugun barg tugun deb ataladi. Har bir ota-tugun maksimal ikkita tugunga ega bo'lishi mumkin. Chap tugun va o'ng tugunga ishora qiluvchi bola tugunlari mavjud. Eng yuqori element ildiz tugun deb ataladi. Chap bola faqat asosiy tugundan kichik yoki teng qiymatlarga ega tugunlarni o'z ichiga oladi. Toʻgʻri boʻgʻinda faqat asosiy tugundan kattaroq yoki unga teng boʻlgan tugunlar mavjud.
02-rasm: Ikkilik qidiruv daraxti namunasi
8-element eng yuqori element hisoblanadi. Shuning uchun u ildiz tugunidir. Agar 3 asosiy tugun bo'lsa, u holda 1 va 6 tugunlardir. 1 - chap tugun, 6 - o'ng tugun. Chap bola asosiy tugundan kichik yoki unga teng qiymatlarni o'z ichiga oladi. 3 asosiy tugun bo'lsa, chap tomonda 3 dan kichik yoki teng bo'lgan element bo'lishi kerak. Bu misolda u 1 ga teng. O'ng tugun faqat asosiy tugundan kattaroq qiymatlarga ega tugunlarni o'z ichiga oladi. Agar 3 asosiy tugun bo'lsa, o'ngdagi tugun 3 dan yuqori qiymatga ega bo'lishi kerak. Bu misolda u 6 ga teng. Xuddi shunday, har bir ma'lumot elementini ikkilik qidiruv daraxtini tartibga solishning ma'lum tartibi mavjud. Bu maʼlumotlar tuzilmasi maʼlumotlarni saralash, olish va qidirishning samarali usulini taʼminlaydi.
Binar daraxt va ikkilik qidiruv daraxti oʻrtasidagi oʻxshashliklar qanday?
- Ikkilik va Ikkilik qidiruv daraxti ham ierarxik ma'lumotlar tuzilmalari.
- Ikkilik daraxt va ikkilik qidiruv daraxti ham ildizga ega.
- Ikkilik daraxtda ham, ikkilik qidiruv daraxtida ham koʻpi bilan ikkita tugun boʻlishi mumkin.
Binar daraxt va ikkilik qidiruv daraxti oʻrtasidagi farq nima?
Binary Tree vs Binary Search Tree |
|
| Iklik daraxti ma'lumotlar strukturasi turi bo'lib, har bir ota-tugunda ko'pi bilan ikkita tugun bo'lishi mumkin. | Ikkilik qidiruv daraxti ikkilik daraxt boʻlib, uning chap tomonida faqat asosiy tugundan kichik yoki teng qiymatlarga ega tugunlar, oʻng tomonda esa faqat asosiy tugundan kattaroq tugunlar mavjud. |
| Ma'lumotlar Buyurtmani tartibga solish | |
| Binar daraxtda ma'lumotlar elementlarini tartibga solish uchun maxsus tartib yo'q. | Ikkilik qidiruv daraxti ma'lumotlar elementlarini tartibga solish uchun o'ziga xos tartibga ega. |
| Foydalanish | |
| Daraxt tuzilmasidagi ma'lumotlar va ma'lumotlarni samarali qidirish uchun binar daraxtdan foydalaniladi. | Ikkilik qidiruv daraxti maʼlumotlarni kiritish, oʻchirish va qidirish uchun ishlatiladi. |
Xulosa – Ikkilik va Ikkilik qidiruv daraxti
Ma'lumotlar strukturasi ma'lumotlarni tartibga solish usulidir. Ba'zan ma'lumotlar daraxt tuzilishida tartibga solinishi mumkin. Ulardan ikkitasi binar daraxt va ikkilik qidiruv daraxti. Ushbu maqola ikkilik daraxt va ikkilik qidiruv daraxti o'rtasidagi farqni muhokama qildi. Ikkilik daraxt - bu har bir ota-ona tugunida ko'pi bilan ikkita tugun bo'lishi mumkin bo'lgan ma'lumotlar strukturasi turi. Ikkilik qidiruv daraxti ikkilik daraxt boʻlib, chap qismda faqat asosiy tugundan kichik yoki unga teng qiymatlarga ega tugunlar, oʻng tomonda esa faqat asosiy tugundan kattaroq tugunlar mavjud.
Binary Tree va Binary Search Tree PDF formatini yuklab oling
Siz ushbu maqolaning PDF-versiyasini yuklab olishingiz va iqtibos keltirgan holda oflayn maqsadlarda foydalanishingiz mumkin. Iltimos, PDF versiyasini bu yerdan yuklab oling: Ikkilik va ikkilik qidiruv daraxti o'rtasidagi farq
