Stablo sa višim levim podstablom

U računarstvu stablo sa višim levim podstablom (engl. Leftist tree, u daljem tekstu LT) je red sa prioritetom sa primenom varijante binarnog hipa. Svaki čvor ima s-vrednost koja predstavlja udaljenost do najbližeg lista. U poređenju sa binarnim hipom, LT nastoji da bude veoma neuravnotežen. Pored svojstva hipa, LT se održavaju tako da desni sin svakog čvora ima manju s-vrednost.

LT je izumeo Klark Alan Krejn. Ime dolazi od činjenice da je levo podstablo obično više od desnog podstabla.

Kada se ubacuje novi čvor u stablo, pravi se novo stablo od jednog čvora i spaja se sa postojećim stablom. Da bi izbacili najmanji element, prvo izbacimo koren a zatim spojimo levo i desno podstablo. Obe ove operacije zahtevaju O(log n) vremena. Ubacivanje je sporije od binarnih hipova koji podržavaju ubacivanje u amortizovanom konstantnom vremenu O(1) i O(log n) u najgorem slučaju.

LT su povoljna zbog svoje sposobnosti za brzo spajanje, u poređenju sa binarnim hipovima kojima je potrebno O(n). U gotovo svim slučajevima kosi hipovi imaju bolji učinak, ali LT imaju garantovano O(log n) složenost u najgorem slučaju, a ne samo amortizovanu složenost.

Naklonost

Uobičajena LT su LT sa naklonošću ka visini. Međutim, postoje druge naklonosti kao što je LT sa težinskom naklonošću.

S-vrednost

S-vrednost čvora je rastojanje tog čvora od najbližeg lista od proširene binarne predstave stabla. Proširena predstava popunjava stablo tako da svaki čvor ima 2 sina(tako da u primeru ukupno imamo 5 listova). Najmanja rastojanja do tih listova su prikazana na skici. Tako s-vrednost od 4 je 2 jer je najbliži list onaj iz 8 – ako je 8 proširen. S-vrednost od 5 je 1 jer bi u proširenom prikazu imao jednog sina koji je list.

S-vrednost

Spajanje visinski naklonjenih stabala

Spajanje dva čvora zavisi od toga da li stablo teži najmanjoj ili najvećoj visini. Za stabla naklonjena najmanjoj visini, postavimo čvor veće vrednosti kao desnog sina. Ako čvor manje vrednosti već ima desnog sina, onda spojimo čvor veće vrednosti sa podstablom čiji je koren desni sin čvora manje vrednosti.

Posle spajanja s-vrednost čvora manje vrednosti mora biti ažurirana. Zatim proverimo da li čvor manje vrednosti ima levog sina. Ako nema, pomerimo desnog sina levo. Ako ima, onda sin sa najvećom s-vrednosti treba postaviti levo.

Java kod za spajanje LT-a naklonjenog najmanjoj visini

public Cvor spoji(Cvor x, Cvor y) {
  if(x == null)
    return y;
  if(y == null) 
    return x;
 
  // da je u pitanju stablo naklonjeno najvecoj visini, onda bi 
  // sledeca linija bila: if(x.element < y.element)
  if(x.element.compareTo(y.element) > 0) {  
    // x.element > y.element
    Cvor temp = x;
    x = y;
    y = temp;
  }
 
  x.desni = spoji(x.desni, y);
 
  if(x.levi == null) {
    // levi sin ne postoji, pa pomeramo desnog sina na levu stranu
    x.levi = x.desni;
    x.desni = null;
 
  } else {
    // levi sin postoji, pa poredimo s-vrednosti
    if(x.levi.s < x.desni.s) {
      Cvor temp = x.levi;
      x.levi = x.desni;
      x.desni = temp;
    }
    // posto znamo da desni sin ima manju s-vrednost, mozemo samo
    // dodati jedan na njegovu s-vrednost
    x.s = x.desni.s + 1;
  }
  return x;
}

Inicijalizacija visinski naklonjenog LT-a

Inicijalizacija visinski naklonjenog LT-a se uglavnom radi na jedan od sledeća dva načina. Prvi način je da se svi čvorovi pojedinačno spoje u visinski naklonjeno LT. Ovaj način nije efikasan i zahteva O(nlogn) vremena. Drugi način je da se koristi red za čuvanje svakog čvora i rezultujućeg stabla. Prva dva elementa se skidaju sa reda, spajaju i vraćaju u red. Na ovaj način možemo inicijalizovati visinski naklonjeno LT za O(n) vremena. Pristup je prikazan u datim primerima. Prikazano je LT naklonjeno najmanjoj visini.

Inicijalizacija LT-a naklonjenog najmanjoj visini - prvi deo

Da bi se inicijalizovalo LT naklonjeno najmanjoj visini postavimo sve elemente koji će biti dodati u stablo u red. U prvom delu primera, skup brojeva [4, 8, 10, 9, 1, 3, 5, 6, 11] je inicijalizovan. Svaka od linija na skici predstavlja sledeći ciklus algoritma, prikazujući sadržaj reda. Prvih pet koraka su jednostavni za praćenje. Primetimo da je novonastalo stablo dodato na kraj reda. U petom koraku se pojavljuje prvi slučaj čvora sa s-vrednošću većom od 1. Šesti korak prikazuje dva spojena stabla sa predvidljivim rezultatom.

Inicijalizacija LT-a naklonjenog najmanjoj visini - drugi deo

U drugom delu se dešava nešto složenije spajanje. Stablo sa manjom vrednošću ima desnog sina, pa spajanje mora biti pozvano ponovo za podstablo čiji je koren desni sin, i drugo stablo. Nakon spajanja rezultujuće stablo se vraća u početno. S-vrednost desnog sina(s=2) je sada veća od s-vrednosti levog sina(s=1), pa se moraju zameniti. S-vrednost korena je sada takođe 2.

Inicijalizacija LT-a naklonjenog najmanjoj visini - treći deo

Treći deo je najsloženiji. Ovde rekurzivno pozivamo spajanje dva puta(svaki put sa podstablom desnog sina koje nije obeleženo). Koristi se isti postupak kao u drugom delu.

Literatura

• Robert E. Tarjan (1983). Data Structures and Network Algorithms. SIAM. str. 38—42. ISBN 978-0-89871-187-5. 
• Dinesh P. Mehta; Sartaj Sahni (28. 10. 2004). „Chapter 5: Leftist trees”. Handbook of Data Structures and Applications. CRC Press. ISBN 978-1-4200-3517-9. 

Spoljašnje veze

• Leftist Trees