Pohon radix

Dalam ilmu komputer, pohon radix adalah struktur data yang mewakili trie yang dioptimalkan ruang di mana setiap node yang merupakan satu-satunya anak digabungkan dengan induknya. Hasilnya adalah jumlah anak dari setiap simpul internal paling banyak adalah radix r dari pohon radix, di mana r adalah bilangan bulat positif dan pangkat x dari 2, dengan x ≥ 1. Tidak seperti pohon biasa, tepi dapat diberi label dengan urutan elemen serta elemen tunggal. Ini membuat pohon radix jauh lebih efisien untuk set kecil dan untuk set string yang memiliki prefiks panjang. Tidak seperti pohon biasa, kunci pada setiap node dibandingkan potongan bit dengan potongan bit, di mana jumlah bit dalam potongan itu pada simpul itu adalah radix r dari trie radix. Ketika r adalah 2, trie radix adalah biner, yang meminimalkan ketersebaran dengan mengorbankan memaksimalkan kedalaman trie — yaitu, memaksimalkan hingga penggabungan bit-string nondiverging di kunci. Ketika r ≥ 4 adalah pangkat 2, maka radix trie adalah r -ary trie, yang mengurangi kedalaman radix trie dengan mengorbankan potensi ketersebaran.