Radiks stablo

U računarstvu, radiks stablo (ili kompaktno prefiks stablo) je prostorno orijentisana struktura podataka u kojoj se svaki čvor sa samo jednim detetom spojio sa svojim detetom. Rezultat je da svaki unutrašnji čvor ima najmanje dvoje dece. Za razliku od redovnih prefiksnih stabala, ivice mogu biti označene sa sekvencama elemenata, kao i pojedinačnim elementima. To ih čini mnogo efikasnijim za male skupove(posebno ako su niske duge) i za grupe niski koje imaju duže prefikse.

Kao optimizacija, oznake ivica mogu biti smeštene u stalnoj veličini(za prve i poslednje elemente).

Imajte na umu da, iako su primeri u ovom članku pokazuju niske kao sekvence karaktera, tip niski u nizu elemenata može biti proizvoljno izabran (na primer, kao bit ili bajt reprezentacije niski kada se koristi kodiranje sa karakterom od više bitova ili Unikod).

Upotreba

Kao što je pomenuto, radiks stabla su korisna za izgradnju asocijativnih nizova sa ključevima koji se mogu izraziti kao niske. Nalaze posebnu primenu u oblasti IP rutiranja, gde je mogućnost da sadrže velike opsege vrednosti, sa par izuzetaka, posebno pogodna u hijerarhijskoj organizaciji IP adresa. Oni se takođe koriste za invertovano obeležavanje tekstualnih dokumenata u preuzimanju informacija.

Operacije

Radiks stabla podržavaju umetanje, brisanje i pretraživanje operacije. Ubacivanje dodaje novu nisku u stablo dok u isto vreme pokušava da smanji količinu podataka koji su dodavani. Brisanje uklanja nisku od stabla. Pretraživanje operacije uključuje tačno pronalaženje, naći prethodnika, naći naslednika, i pronaći sve niske sa prefiksom. Sve ove operacije su O(k) gde je k maksimalna dužina svih niski u setu. Ovaj spisak ne može biti konačan.

Pronalaženje

Pronalaženje niske u radiks stablu

Operacija pronalaženja utvrđuje da li niska postoji u stablu. Većina operacija menja ovaj pristup na neki način da bi se rešili svoje specifične zadatke. Na primer, čvor gde niska prestaje može biti od značaja. Ova operacija je slična prefiks stablu osim što neke ivice konzumiraju više elemenata.

Sledeći pseudo kod pretpostavlja da ove klase postoje.

Ivica

• Čvor targetNode
• niska label

Čvor

• Niz ivica edges
• funkcija isLeaf()

function lookup(string x)
{
  // Почети у корену без пронађених елемената
  Node traverseNode := root;
  int elementsFound := 0;
  
  // Пролазити док се не нађе лист или није могуће наставити
  while (traverseNode != null && !traverseNode.isLeaf() && elementsFound < x.length)
  {
    // Узети следећу ивицу за истраживање на основу елемената који још нису пронађени у Х
    Edge nextEdge := select edge from traverseNode.edges where edge.label is a prefix of x.suffix(elementsFound)
      // x.suffix(elementsFound) враћа задњи (x.length - elementsFound) елемент од x
  
    // Да ли је пронађена ивица?
    if (nextEdge != null)
    {
      // Ставити следећи чвор да се истражује
      traverseNode := nextEdge.targetNode;
    
      // Повећавати пронађене елементе на основу ознака постављених код ивица
      elementsFound += nextEdge.label.length;
    }
    else
    {
      // Прекинути петљу
      traverseNode := null;
    }
  }
  
  // Подударност је пронађена ако стигнемо до чвора листа и искоришћено је тачно x.length елемената
  return (traverseNode != null && traverseNode.isLeaf() && elementsFound == x.length);
}

Unošenje

Da biste uneli nisku, tražimo drvo dok se ne može napraviti nikakav dalji napredak. U ovom trenutku možemo ili dodati novu odlazeću ivicu označenu sa svim preostalim elementima u ulaznu nisku, ili ako već postoji odlazeći ivica koja deli prefiks sa preostalim ulaznim stringom, možemo ih podeliti na dve ivice (prvi označen sa zajedničkim prefiksom) i nastaviti. Ovo razdvajanje osigurava da nijedan čvor nema više dece nego što ima mogućih elemenata stringa.

Nekoliko slučajeva ubacivanja su prikazani ispod, mada još postoji. Imajte na umu da r jednostavno predstavlja koren. Pretpostavlja se da ivice mogu biti označene sa praznim niskama da prekinu niske gde je to potrebno i da koren nema dolaznu ivicu.

• 
  Uneti 'water' u koren
• 
  Uneti 'slower' dok se održava 'slow'
• 
  Uneti 'test' što je prefiks od 'tester'
• 
  Uneti 'team' dok se razdvaja 'test' i kreira nova oznaka ivice 'st'
• 
  Uneti 'toast' dok se razdvaja 'te' i pomera prethodna niska na niži nivo

Brisanje

Da biste izbrisali h string sa stabla, prvo pronađite list koji predstavlja h. Zatim, pod pretpostavkom da postoji h, uklonimo odgovarajući čvor lista. Ako roditelj našeg čvora lista ima samo jedno drugo dete, onda ta dolazna oznaka deteta se dodaje roditeljskoj nadolazećoj oznaci i dete se ukloni.

Dodatne operacije

• Pronaći sve nizove sa zajedničkim prefiksom: Vraća niz niski koji počinju istim prefiksom.
• Pronaći prethodnika: locira najveću nisku manju od zadatog niza, po leksikografskom poretku.
• Pronaći naslednika: Pronalazi najmanju nisku veću od zadatog niza, po leksikografskom poretku.

Istorija

Donald R. Morison(Donald R. Morrison) prvi je opisao ono što je on nazvao "Patricia drveće" 1968-e, naziv potiče od akronima Patricia, što je skraćenica za "Praktični algoritam pretraživanja informacija kodirana alfanumerički". Gernot Gvehenberger(Gernot Gwehenberger) samostalno je izumeo i opisao strukturu podataka u otprilike isto vreme.

Poređenje sa drugim strukturama podataka

(U sledećim poređenjima, pretpostavlja se da su ključevi dužine k i struktura podataka sadrži n članova.)

Za razliku od samo-balansirajućih stabala, radiks stabla dozvoljavaju pronalaženje, umetanje, brisanje i u vremenu O(k), a ne O(log n). Ovo ne izgleda kao prednost, jer normalno k ≥ log n, ali u balansiranom stablu svako poređenje je poređenje niski koje zahteva O(k) u najgorem slučaju, od kojih su mnogi u praksi spori zbog dugih zajedničkih prefiksa (u slučaju gde poređenje počne na početku niske). U prefiks stablu, ova poređenja zahtevaju konstantno vreme, ali je potrebno m poređenja da se pronađe niz dužine m. Radiks stabla može da obavlja ove operacije sa manje poređenja, i zahteva mnogo manje čvorova.

Radiks stabla takođe dele mane prefiks stabala, ipak: kao što se oni mogu primeniti samo na nizove elemenata ili elemente sa efikasnim povratnim mapiranjem nizova, nemaju potpunu opštost izbalansiranih pretraživanja drveća, koji se odnose na bilo koji tip podataka sa ukupno naručivanja. Obrtno mapiranje za niske može da se koristi za proizvodnju potrebne totalne narudžbine za balansiranu pretragu drveća, ali ne i obrnuto. Ovo takođe može biti problematično ukoliko tip podataka samo pruža poređenje operacije, ali ne (de)serijalizaciju operacija.

Kod heš tabela se obično kaže da je očekivano O(1) puta ubacivanja i brisanja, ali to važi samo kada je u pitanju obračunavanje heš ključeva da bude konstanta vremenska operacija. Kada se hešing ključa uzima u obzir, za heš tabele se očekuje O(k) puta ubacivanja i brisanja, ali može da traje duže u najgorem slučaju u zavisnosti od toga kako se rukuje sa sudarima. Radiks stabla imaju najgori slučaj O(k) ubacivanja i brisanja. Naslednik/prethodnik operacije radiks stabala se takođe ne sprovode preko heš tabele.

Varijante

Zajednički produžetak radiks stabala koristi dve boje čvorova, "crne" i "bele“. Da biste proverili da li data niska se čuva u drvetu, pretraživanje počinje od vrha i prati ivice ulazne niske dok se napredak ne može više ostvariti. Ako se tražena niska konzumira i konačni čvor je crni čvor, pretraživanje nije uspelo, a ako je bele boje, pretraga je uspela. To nam omogućava da dodamo veliki asortiman niski sa zajedničkim prefiksom u stablo, koristeći bele čvorove, a zatim ukloniti mali skup "izuzetaka" prostorski efikasnim načinom ubacivanja pomoću crnih čvorova.

Spoljašnje veze

• Algorithms and Data Structures Research & Reference Material: PATRICIA, by Lloyd Allison, Monash University
• Patricia Tree, NIST Dictionary of Algorithms and Data Structures
• Crit-bit trees, by Daniel J. Bernstein
• Radix Tree API in the Linux Kernel, by Jonathan Corbet
• Kart (key alteration radix tree), by Paul Jarc