Vaqt murakkabligi
Eng yaxshi: O(1)
Trie — umumiy prefikslardan foydalanib, satrlarni saqlaydigan ma'lumotlar tuzilmasi. Har bir qirra bitta belgini ifodalaydi, ildizdan tugungacha bo'lgan yo'l esa prefiksni hosil qiladi. Qidiruv O(L) vaqt oladi, bu yerda L — so'z uzunligi. Bu murakkablik saqlangan so'zlar soniga bog'liq emas.
Qanday ishlaydi:
1. Har bir tugun farzand tugunlar xaritasini (belgi → tugun) va isEnd bayrog'ini saqlaydi
2. So'zni qo'shishda belgilar ketma-ket ko'rib chiqiladi va faqat mavjud bo'lmagan tugunlar yaratiladi
3. isEnd haqiqiy so'z qayerda tugashini belgilaydi. Shu sababli "ca" daraxtdagi yo'l bo'lishi mumkin, lekin alohida so'z bo'lmasligi ham mumkin
Nima uchun hash jadvali emas:
Hash jadvali ham aniq kalitni O(L) vaqtda qidiradi,
ammo barcha kalitlarni tekshirmasdan
"ca bilan boshlanadigan so'zlar qaysilar?" degan savolga
javob bera olmaydi. Trie atigi 2 ta tugun pastga yuradi
va butun quyi daraxt kerakli natijani beradi.
Vaqt murakkabligi:
Eng yaxshi: O(1), agar birinchi belgi mos kelmasa
O'rtacha: insert, search va startsWith uchun O(L)
Eng yomon: O(L) — so'zlar soniga hech qachon bog'liq emas
Xotira murakkabligi: O(n × L) — uning asosiy kamchiligi. Radix daraxtlari bitta farzandli tugunlar zanjirini siqish orqali xotira sarfini kamaytiradi.
Qo'llanilishi: avtomatik to'ldirish, imlo tekshirgichlari, IP marshrutlash jadvallari (eng uzun mos prefiksni topish), T9 klaviaturalari, so'z o'yinlari, kod muharrirlarida belgilarni avtomatik to'ldirish
O'xshash algoritmlar
Ko'p beriladigan savollar
- Trie (Prefikslar daraxti) nima?
- Trie — umumiy prefikslardan foydalanib, satrlarni saqlaydigan ma'lumotlar tuzilmasi. Har bir qirra bitta belgini ifodalaydi, ildizdan tugungacha bo'lgan yo'l esa prefiksni hosil qiladi. Qidiruv O(L) vaqt oladi, bu yerda L — so'z uzunligi. Bu murakkablik saqlangan so'zlar soniga bog'liq emas.
- Trie (Prefikslar daraxti) murakkabligi qanday?
- Vaqt (o'rtacha): insert, search va startsWith uchun O(L) · Xotira: O(n × L)
- Ushbu Trie (Prefikslar daraxti) vizualizatori kimlar uchun?
- Trie (Prefikslar daraxti) vizualizatsiyasi "Ma'lumotlar tuzilmalari" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Trie (Prefikslar daraxti) ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Ma'lumotlar tuzilmalari) quyidagilarni ko'rishingiz mumkin: Stack, Queue, Linked List. Har biri interaktiv vizualizatsiyaga ega.