Стабло са вишим левим подстаблом

У рачунарству стабло са вишим левим подстаблом (енгл. Leftist tree, у даљем тексту ЛТ) је ред са приоритетом са применом варијанте бинарног хипа. Сваки чвор има с-вредност која представља удаљеност до најближег листа. У поређењу са бинарним хипом, ЛТ настоји да буде веома неуравнотежен. Поред својства хипа, ЛТ се одржавају тако да десни син сваког чвора има мању с-вредност.

ЛТ је изумео Кларк Алан Крејн. Име долази од чињенице да је лево подстабло обично више од десног подстабла.

Када се убацује нови чвор у стабло, прави се ново стабло од једног чвора и спаја се са постојећим стаблом. Да би избацили најмањи елемент, прво избацимо корен а затим спојимо лево и десно подстабло. Обе ове операције захтевају O(log n) времена. Убацивање је спорије од бинарних хипова који подржавају убацивање у амортизованом константном времену О(1) и О(log n) у најгорем случају.

ЛТ су повољна због своје способности за брзо спајање, у поређењу са бинарним хиповима којима је потребно О(n). У готово свим случајевима коси хипови имају бољи учинак, али ЛТ имају гарантовано O(log n) сложеност у најгорем случају, а не само амортизовану сложеност.

Наклоност

Уобичајена ЛТ су ЛТ са наклоношћу ка висини. Међутим, постоје друге наклоности као што је ЛТ са тежинском наклоношћу.

С-вредност

С-вредност чвора је растојање тог чвора од најближег листа од проширене бинарне представе стабла. Проширена представа попуњава стабло тако да сваки чвор има 2 сина(тако да у примеру укупно имамо 5 листова). Најмања растојања до тих листова су приказана на скици. Тако с-вредност од 4 је 2 јер је најближи лист онај из 8 – ако је 8 проширен. С-вредност од 5 је 1 јер би у проширеном приказу имао једног сина који је лист.

Спајање висински наклоњених стабала

Спајање два чвора зависи од тога да ли стабло тежи најмањој или највећој висини. За стабла наклоњена најмањој висини, поставимо чвор веће вредности као десног сина. Ако чвор мање вредности већ има десног сина, онда спојимо чвор веће вредности са подстаблом чији је корен десни син чвора мање вредности.

После спајања с-вредност чвора мање вредности мора бити ажурирана. Затим проверимо да ли чвор мање вредности има левог сина. Ако нема, померимо десног сина лево. Ако има, онда син са највећом с-вредности треба поставити лево.

Јава код за спајање ЛТ-а наклоњеног најмањој висини

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;
}

Иницијализација висински наклоњеног ЛТ-а

Иницијализација висински наклоњеног ЛТ-а се углавном ради на један од следећа два начина. Први начин је да се сви чворови појединачно споје у висински наклоњено ЛТ. Овај начин није ефикасан и захтева О(nlogn) времена. Други начин је да се користи ред за чување сваког чвора и резултујућег стабла. Прва два елемента се скидају са реда, спајају и враћају у ред. На овај начин можемо иницијализовати висински наклоњено ЛТ за О(n) времена. Приступ је приказан у датим примерима. Приказано је ЛТ наклоњено најмањој висини.

Иницијализација ЛТ-а наклоњеног најмањој висини - први део

Да би се иницијализовало ЛТ наклоњено најмањој висини поставимо све елементе који ће бити додати у стабло у ред. У првом делу примера, скуп бројева [4, 8, 10, 9, 1, 3, 5, 6, 11] је иницијализован. Свака од линија на скици представља следећи циклус алгоритма, приказујући садржај реда. Првих пет корака су једноставни за праћење. Приметимо да је новонастало стабло додато на крај реда. У петом кораку се појављује први случај чвора са с-вредношћу већом од 1. Шести корак приказује два спојена стабла са предвидљивим резултатом.

Иницијализација ЛТ-а наклоњеног најмањој висини - други део

У другом делу се дешава нешто сложеније спајање. Стабло са мањом вредношћу има десног сина, па спајање мора бити позвано поново за подстабло чији је корен десни син, и друго стабло. Након спајања резултујуће стабло се враћа у почетно. С-вредност десног сина(с=2) је сада већа од с-вредности левог сина(с=1), па се морају заменити. С-вредност корена је сада такође 2.

Иницијализација ЛТ-а наклоњеног најмањој висини - трећи део

Трећи део је најсложенији. Овде рекурзивно позивамо спајање два пута(сваки пут са подстаблом десног сина које није обележено). Користи се исти поступак као у другом делу.

Референце

Литература

Robert E. Tarjan (1983). Data Structures and Network Algorithms. SIAM. стр. 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.

Спољашње везе

Leftist Trees