Struct Trie 

pub struct Trie { /* private fields */ }

Trie — har bir qirra bitta harf, ildizdan tugungacha bo’lgan yo’l — prefiks.

       (root)
       /    \
     o        k
     |        |
     l        i
    / \       |
   m   t      t
   |   |      |
  [a] [i]    [o]      ← [ ] = so'z shu yerda tugaydi
       |
      [n]
 → "olma", "olti", "oltin", "kito"

Amal	Murakkablik	Izoh
insert / contains	O(m)	m — so’z uzunligi, lug’at hajmiga bog’liq emas!
starts_with	O(m)	prefiks bormi
words_with_prefix	O(m + natija)	avtoto’ldirish

Qayerda ishlatiladi: qidiruv qatoridagi avtoto’ldirish, telefondagi T9, imlo tekshirgich, IP marshrutlash jadvallari, so’z o’yinlari.

HashSet dan farqi: HashSet “bu so’z bormi?” ga javob beradi, Trie esa prefiks bo’yicha ham qidira oladi va xotirada umumiy prefikslarni bir marta saqlaydi.

Misol

use rust_algorithms::tree::Trie;

let mut t = Trie::new();
for so_z in ["olma", "olti", "oltin", "kitob"] {
    t.insert(so_z);
}

assert!(t.contains("olma"));
assert!(!t.contains("ol"));        // "ol" — so'z emas, faqat prefiks
assert!(t.starts_with("ol"));

let mut topilgan = t.words_with_prefix("olt");
topilgan.sort();
assert_eq!(topilgan, vec!["olti", "oltin"]);
assert_eq!(t.len(), 4);

Implementations

impl Trie

pub fn new() -> Self

Bo’sh trie.

pub fn insert(&mut self, word: &str) -> bool

So’z qo’shadi. Yangi so’z bo’lsa true.

pub fn contains(&self, word: &str) -> bool

Aynan shu so’z lug’atda bormi?

pub fn starts_with(&self, prefix: &str) -> bool

Shu prefiks bilan boshlanadigan so’z bormi?

pub fn words_with_prefix(&self, prefix: &str) -> Vec<String>

Prefiks bilan boshlanadigan barcha so’zlar (avtoto’ldirish).

pub fn words(&self) -> Vec<String>

Lug’atdagi barcha so’zlar.

pub fn remove(&mut self, word: &str) -> bool

So’zni o’chiradi (tugunlar qoladi, faqat belgisi olib tashlanadi).

pub fn len(&self) -> usize

So’zlar soni.

pub fn is_empty(&self) -> bool

Bo’shmi?

Trait Implementations

impl Debug for Trie

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Trie

fn default() -> Trie

Returns the “default value” for a type.

impl<S: AsRef<str>> FromIterator<S> for Trie

fn from_iter<I: IntoIterator<Item = S>>(iter: I) -> Self

Creates a value from an iterator.