BST — har bir tugunining ko'pi bilan ikkita farzandi bo'lgan daraxt. Har bir tugun uchun quyidagi shartlar bajariladi:
- Chap qism daraxtida faqat tugun qiymatidan kichik qiymatlar bo'ladi
- O'ng qism daraxtida faqat tugun qiymatidan katta qiymatlar bo'ladi
Bu tartib har bir qadamda qidiruv maydonini ikkiga qisqartirish orqali samarali qidirish imkonini beradi.
Amallar:
insert: solishtirish va chapga/o'ngga o'tish — O(h)
search: solishtirish va chapga/o'ngga o'tish — O(h)
delete: tugunni topish va daraxtni qayta tuzish — O(h)
Bu yerda h = daraxt balandligi:
Muvozanatlangan daraxt: h = O(log n) — samarali!
Buzilgan daraxt: h = O(n) — bog'langan ro'yxat kabi
Qo'llanilishi: tartiblangan ma'lumotlarni saqlash, oraliq bo'yicha qidirish, ustuvor navbatlar (muvozanatlash bilan)
O'xshash algoritmlar
Ko'p beriladigan savollar
- Ikkilik qidiruv daraxti (BST) nima?
- BST — har bir tugunining ko'pi bilan ikkita farzandi bo'lgan daraxt. Har bir tugun uchun quyidagi shartlar bajariladi: - Chap qism daraxtida faqat tugun qiymatidan kichik qiymatlar bo'ladi - O'ng qism daraxtida faqat tugun qiymatidan katta qiymatlar bo'ladi
- Ikkilik qidiruv daraxti (BST) murakkabligi qanday?
- Ikkilik qidiruv daraxti (BST) bosqichma-bosqich vizualizatsiya hamda vaqt va xotira murakkabligi tahlili bilan tushuntiriladi.
- Ushbu Ikkilik qidiruv daraxti (BST) vizualizatori kimlar uchun?
- Ikkilik qidiruv daraxti (BST) vizualizatsiyasi "Ma'lumotlar tuzilmalari" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Ikkilik qidiruv daraxti (BST) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Ma'lumotlar tuzilmalari) quyidagilarni ko'rishingiz mumkin: Stack, Queue, Linked List. Har biri interaktiv vizualizatsiyaga ega.