Ternary search tries

Binary search tree

Ternary search tries (TST, uchlamchi qidiruv trie) R-way tries’dagi kamchilikka yechim o’laroq tavsiya etiladi. TSTda belgilar indeks ko’rinishida emas, node ichida saqlanadi (R-way tries’da belgilar indeks nomer sifatida saqlanardi). Shuningdek har bir node uch child’ga ega: kichikroq (chap), teng (o’rtada), kattaroq (o’ngda).

R-way tries

Binary search tree

Ushbu mavzu string key’lar qidiruvi uchun mo’ljallangan ma’lumotlar tuzilmasi – tries (trays) haqida bo’ladi. Shu vaqtgacha ko’rib o’tgan ma’lumotlar tuzilmalaridan qidiruv uchun eng yaxshisi red-black tree – key’ni qidirish / qo’shish / o’chirish uchun O(log N) vaqtni kafolatlardi.