Pohon radix


Contoh pohon radix

Dalam ilmu komputer, pohon radix (juga radix trie atau pohon awalan kompak atau trie terkompresi) adalah struktur data yang mewakili trie (pohon awalan) 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 (terutama jika stringnya panjang) dan untuk set string yang memiliki prefiks panjang.

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. 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 . Ketika r ≥ 4 adalah pangkat 2, maka radix trie adalah r -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,[1][2][3] di mana kemampuan untuk memuat rentang nilai yang besar dengan beberapa pengecualian sangat cocok untuk organisasi hierarki alamat IP.[4] Mereka juga digunakan untuk indeks terbalik dari dokumen teks dalam pencarian informasi.

Referensi

  1. ^ "rtfree(9)". www.freebsd.org. Diakses tanggal 2016-10-23.
  2. ^ The Regents of the University of California (1993). "/sys/net/radix.c". BSD Cross Reference. NetBSD. Diakses tanggal 2019-07-25. Routines to build and maintain radix trees for routing lookups.
  3. ^ "Lockless, atomic and generic Radix/Patricia trees". NetBSD. 2011.
  4. ^ Knizhnik, Konstantin. "Patricia Tries: A Better Index For Prefix Searches", Dr. Dobb's Journal, June, 2008.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.