In computer science, a radix tree (also radix trie or compact prefix tree or compressed trie) is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.
Dalam ilmu komputer, pohon radix (juga radix trie atau pohon awalan kompak atau trie terkompresi) adalah struktur data yang mewakili trie (pohon awalan)
The number of children of every internal node is at most the radix r of the radix tree, where r2x for some integer x ≥ 1.
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.
Unlike regular trees, edges can be labeled with sequences of elements as well as single elements.
Tidak seperti pohon biasa, tepi dapat diberi label dengan urutan elemen serta elemen tunggal.
This makes radix trees much more efficient for small sets (especially if the strings are long) and for sets of strings that share long prefixes.
Ini membuat pohon radix jauh lebih efisien untuk set kecil (terutama jika stringnya panjang) dan untuk set string yang memiliki prefiks panjang.
Unlike regular trees (where whole keys are compared en masse from their beginning up to the point of inequality), the key at each node is compared chunk-of-bits by chunk-of-bits, where the quantity of bits in that chunk at that node is the radix r of the radix trie.
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 r dari trie radix.
When r is 2, the radix trie is binary (i.e., compare that node's 1-bit portion of the key), which minimizes sparseness at the expense of maximizing trie depth—i.e., maximizing up to conflation of nondiverging bit-strings in the key.
Ketika r 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 .
When r ≥ 4 is a power of 2, then the radix trie is an r-ary trie, which lessens the depth of the radix trie at the expense of potential sparseness.
Ketika r ≥ 4 adalah pangkat 2, maka radix trie adalah r -ary trie, yang mengurangi kedalaman radix trie dengan mengorbankan potensi ketersebaran.
Radix trees are useful for constructing associative arrays with keys that can be expressed as strings.
Pohon radix berguna untuk membangun array asosiatif dengan kunci yang dapat dinyatakan sebagai string.
They find particular application in the area of IP routing, where the ability to contain large ranges of values with a few exceptions is particularly suited to the hierarchical organization of IP addresses.
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.
They are also used for inverted indexes of text documents in information retrieval.
Mereka juga digunakan untuk indeks terbalik dari dokumen teks dalam pencarian informasi.