Pohon radix

Tidak seperti pohon biasa (di mana seluruh kunci dibandingkan secara massal dari awal hingga titik ketidaksetaraan), kunci pada setiap node dibandingkan potongan bit dengan potongan bit, di mana jumlah bit dalam potongan itu pada simpul itu adalah radix  dari trie radix. Ketika  adalah 2, trie radix adalah biner (yaitu, bandingkan bagian kunci 1-bit node itu), yang meminimalkan ketersebaran dengan mengorbankan memaksimalkan kedalaman trie — yaitu, memaksimalkan hingga penggabungan bit-string nondiverging di kunci . Ketika  ≥ 4 adalah pangkat 2, maka radix trie adalah  -ary trie, yang mengurangi kedalaman radix trie dengan mengorbankan potensi ketersebaran.

 Aplikasi 
Pohon radix berguna untuk membangun array asosiatif dengan kunci yang dapat dinyatakan sebagai string. Mereka menemukan aplikasi khusus di bidang perutean IP, di mana kemampuan untuk memuat rentang nilai yang besar dengan beberapa pengecualian sangat cocok untuk organisasi hierarki alamat IP.Knizhnik, Konstantin. "Patricia Tries: A Better Index For Prefix Searches", Dr. Dobb's Journal, June, 2008. Mereka juga digunakan untuk indeks terbalik dari dokumen teks dalam pencarian informasi.

 Referensi 

Kategori:Pohon (struktur data)