AVL стебла

AVL стебло е балансирано бинарно стебло. За AVL стеблата важи, висините на двете потстебла секој јазол се разликуваат најмногу за 1 па затоа се вели дека е балансирано по висина. Пребарување, додавање на елемент и бришење се со комплексност O(log N) време, ова е просечно време и најлошо време истовремено, кадe N е број на јазли во стеблото пред операцијата. Додавање и бришење на елемент како операции може да вклучат ребалансирање на стеблото со една или повеќе ротации на стеблото.

AVL е многу корисно за решавање на разни типови на проблеми кај кои се бара голема ефикасност. Следува мојата имплементација (во Java) и објаснување за секоја операција поединечно. Ви препорачувам пред да го разгледате кодот да прочитате повеќе за AVL стеблата, на крај има линкови.

class Node {
Node left;
Node right;
Node parent;
int value;
int height;

Node () {
 left = null;
 right = null;
 parent = null;
 height = 1;
}

Node (int value) {
 left = null;
 right = null;
 this.value = value;
 height = 1;
}

}

Јазелот е посебна класа која се состои од покажувачи кон левото и десното дете, покажувач кон родителот, вредноста што ја чува јазелот т.е. клучната информација според која се сортираат податоците (во овој случај е број) и висина на стеблото.

int getHeight(Node mom) {
if (mom == null) return 0;
return mom.height;
}

int ballanceFactor(Node mom) {
if (mom == null) return 0;
int lh = getHeight(mom.left);
int rh = getHeight(mom.right);
return rh-lh;
}

getHeight ја имплементирав посебно, иако во секој јазел постои променлива height. Ова е со цел да се избегне разгледување на специјален случај кога нема лево или (и) десно дете. Втората функција го дава факторот на балансираност на левото и десното потстебло, доколку вредноста што се враќа е позитивна, тоа значи дека десното потсетбло има поголема висина од левото.

Следува објаснувањето за "најкомплицираниот" дел, ротацијата. На сликата се објаснети четирите случаи (кои воглавно се сведуваат на два симетрични).

Node rightRightCase(Node mom) {
if (mom == null) return null;

Node R = mom.right;
Node T2 = R.left;

if (mom.parent.left == mom) {
 mom.parent.left = R;
} else {
 mom.parent.right = R;
}

R.parent = mom.parent;

R.left = mom;
mom.parent = R;

mom.right = T2;
if (T2 != null) T2.parent = mom;

mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;
R.height = Math.max(getHeight(R.left), getHeight(R.right))+1;

return R;
}

Оваа функција како аргумент прима некој јазел кој е корен на стебло. После ротацијата како резултат функцијата го враќа новиот корен на ова потстебло, т.е. десното дете. Напомена, за да работи оваа функција, јазелот кој се испраќа како аргумент треба да има десно дете (во спротивно нема логика да се прави ваква ротација и стеблото не може да има фактор на балансираност -1 кој пак е основен предуслов за некоја друга функција да го повика овој метод).

R е десното дете, а Т2 е левото дете на јазелот mom. Она што во овој код го правиме е известување до родителот на mom дека дете веќе нема да му биде mom туку R. Потоа ги менуваме местата на mom и R, ротираме на лево. Потстеблото Т2 станува десно потстебло на Т2. Правиме ажурирање на висините на mom и R и како резултат функцијата враќа покажувач кон R, за да знае повикувачот на овој метод кој е јазелот кој си го сменил местото со mom.

Node rightLeftCase(Node mom) {
leftLeftCase(mom.right);
return rightRightCase(mom);
}

Овој случај е двојна ротација. Прво го ротираме на десно стеблото чиј корен е mom.right, па потоа вршиме ротација на лево со референтен јазел во mom.

Напомена: rightRightCase е аналогно со ротација на лево, а leftLeftCase е аналогно со ротација на десно.

Node leftLeftCase(Node mom) {
if (mom == null) return null;
Node L = mom.left;
Node T2 = L.right;

if (mom.parent.left == mom) {
 mom.parent.left = L;
} else {
 mom.parent.right = L;
}

L.parent = mom.parent;

L.right = mom;
mom.parent = L;

mom.left = T2;
if (T2 != null) T2.parent = mom;

mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;
L.height = Math.max(getHeight(L.left), getHeight(L.right))+1;

return L;
}

Node leftRightCase(Node mom) {
rightRightCase(mom.left);
return leftLeftCase(mom);
}

Овие два случаи се симетрични со rightRightCase(Node mom) и rightLeftCase(Node mom) и затоа нема повторно да ги објаснувам.

void ballanceTreeInsertion(Node root, Node mom) {
int a, p;

while (mom != root) {
 p = ballanceFactor(mom);
 if (p == 2) {
  // right subtree outweighs the left subtree
  // If the balance factor of R is +1, a left rotation is needed with P as the root.
  // If the balance factor of R is -1, a double left rotation is needed
 
  a = ballanceFactor(mom.right);
 
  if (a == 1) {
   mom = rightRightCase(mom);
  } else {
   if (a == -1) {
    mom = rightLeftCase(mom);
   }
  }
 
 } else {
  if (p == -2) {
   a = ballanceFactor(mom.left);
  
   if (a == -1) {
    mom = leftLeftCase(mom);
   } else {
    if (a == 1) {
     mom = leftRightCase(mom);
    }
   }
  }
 }

 mom = mom.parent;

 // we update the height of mom
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

}

}

Во мојата имплементација, секое балансирано стебло има единствен корен root. Вистинскиот корен е во левото дете на root. Ова е со цел за да може да се претстави стебло со 0 елементи (root.left ќе биде null во тој случај). Исто така, ваква динамична структура често се менува внатрешно и root.left во различни моменти од времето може да има различни јазли, што е тешко да се претстави доколку не постои некој "поврховен" јазел како коренот со кој единствено се претставува и еднозначно се карактеризира секое стебло.

Оваа функција е клучна за добивање на балансираност на стеблото при додавање на нов елемент. Како аргумент се праќа корен на дрвото и јазелот од кој почнуваме да го балансираме дрвото. Го балансираме јазелот mom и потоа се качуваме нагоре по стеблото се додека не стигнеме до коренот. Алгоритмот за балансирање е следен: во p го сместуваме факторот на балансираност на јазелот кој го обработуваме. ДОколку овој број е 2 или -2, тоа значи дека стеблото во тој јазел е небалансирано (понатаму накратко ќе го употребувам поимот балансираност во јазел, наместо балансираност на стеблото чиј корен е конкретниот јазел). Во зависност од тоа дали десното (левото) дете има фактор на балансираност 1 или -1 се одвива единечна или двојна ротација. Пред да се качиме нагоре по хиерархијата ја ажурираме висината на јазелот кој моментално го обработуваме.

void ballanceTreeDeletion(Node root, Node mom) {
int a, p;

while (mom != root) {
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

 p = ballanceFactor(mom);
 if (p == 2) {
  // right subtree outweighs the left subtree
  // If the balance factor of R is +1, a left rotation is needed with P as the root.
  // If the balance factor of R is -1, a double left rotation is needed
 
  a = ballanceFactor(mom.right);
 
  if ((a == 1)||(a == 0)) {
   mom = rightRightCase(mom);
  } else {
   if (a == -1) {
    mom = rightLeftCase(mom);
   }
  }
 
 } else {
  if (p == -2) {
   a = ballanceFactor(mom.left);
  
   if ((a == -1)||(a == 0)) {
    mom = leftLeftCase(mom);
   } else {
    if (a == 1) {
     mom = leftRightCase(mom);
    }
   }
  }
 }

 mom = mom.parent;

 // we update the height of mom
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

}

}

Оваа функција е скоро идентична на претходната, со таа разлика што овде се применува ротација на лево доколку p = 2 и (а = 1 или а = 0), и ротација на десно доколку p = 2 и (а = -1 или а = 0). Првата функција ќе ја употребуваме за балансирање при додавање на елемент, втората при бришење на елемент. Доколку ве интересира зошто е ваква имплементацијата можете да прочитате повеќе во разни книги кои се занимаваат со тематика од областа на алгоритмите и структурите на податоци.

void addNode(Node root, int value) {
Node mom = root.left;
Node newnode = new Node(value);
Node prev = root;

while (mom != null) {
 if (value <= mom.value) {
  prev = mom;
  mom = mom.left;
 } else {
  prev = mom;
  mom = mom.right;
 }
}

newnode.parent = prev;

if (value <= prev.value) {
 prev.left = newnode;
} else {
 prev.right = newnode;
}

// now we need to balance the tree
mom = newnode;

ballanceTreeInsertion(root, mom);

}

addNode прима како аргумент корен и вредност која што сакаме да се смести во стеблото. Се изминува стеблото надоле додека не се дојде до некој "null елемент" и на негово место се сместува новиот. Овде важи правилото, сите лементи во левото потстебло на даден јазел се помали или еднакви на вредноста на тој јазел, а сите елементи во десното потстебло на јазелот се поголеми од неговата вредност. Откако ќе го внесеме јазелот, го балансираме новиот јазел т.е. ја повикуваме функцијата ballanceTreeInsertion која врши верижно балансирање на стеблото нагоре се до коренот.

void deleteNode(Node root, int value) {
Node mom = root.left;
Node prev = root;
Node T;
boolean found = false;

while (mom != null) {
 if (mom.value == value) {
  found = true;
  break;
 }
 if (value <= mom.value) {
  prev = mom;
  mom = mom.left;
 } else {
  prev = mom;
  mom = mom.right;
 }
}

if (found == false) {
 //System.out.println("The element was not found");
 return;
}

Node orig = mom;

if ((orig.left == null)&&(orig.right == null)) {
 // we remove the node
 mom = orig.parent;
 if (mom.left == orig) {
  mom.left = null;
 } else {
  mom.right = null;
 }
 orig = null;

 // we should be sure that the subtree with mom with it's main root element
 // has correct heights and as parametar we give valid element
 mom.height = 1;
 ballanceTreeDeletion(root, mom);
 return;
}

if ((orig.left == null)^(orig.right == null) == true) {
 // if there is exactly one subtree
 mom = orig.parent;
 if (orig.left != null) {
  T = orig.left;
  if (mom.left == orig) {
   mom.left = orig.left;
   orig.left.parent = mom;
  } else {
   mom.right = orig.left;
   orig.left.parent = mom;
  }
 } else {
  T = orig.right;
  if (mom.left == orig) {
   mom.left = orig.right;
   orig.right.parent = mom;
  } else {
   mom.right = orig.right;
   orig.right.parent = mom;
  }
 }
 orig = null;
 ballanceTreeDeletion(root, T);
 return;
}

// the node has 2 subtrees, we need to find the smallest element of the right subtree of mom
mom = orig.right;

if (mom.left == null) {
 // special case, it is more complicated to change the relations
 if (orig.parent.left == orig) {
  orig.parent.left = mom;
 } else {
  orig.parent.right = mom;
 }

 orig.left.parent = mom;
 mom.left = orig.left;
 mom.parent = orig.parent;
 orig = null;
 ballanceTreeDeletion(root, mom);
 return;
}

prev = mom;

while (mom != null) {
 prev = mom;
 mom = mom.left;
}

mom = prev;
prev = mom.parent;

// we are changing the relations instead of just changing the value

if (mom.right != null) {
 mom.right.parent = mom.parent;
}

T = mom.parent;
mom.parent.left = mom.right;

mom.parent = orig.parent;
mom.left = orig.left;
mom.right = orig.right;

if (orig.parent.left == orig) {
 orig.parent.left = mom;
} else {
 orig.parent.right = mom;
}

orig.left.parent = mom;
orig.right.parent = mom;

// now we need to balance the tree
T.height = Math.max(getHeight(T.left), getHeight(T.right))+1;
ballanceTreeDeletion(root, T);

}

Бришењето на јазел од стеблото е малку покомплицирано. Оваа функција како аргумент прима референца кон коренот и клучната вредност на јазелот што сакаме да биде избришан. Прво го пронаоѓаме јазелот во стеблото. Потоа разгледуваме неколку специјални случаи.

Доколку јазелот е лист, т.е. нема лево и десно потстебло, тогаш јазелот едноставно го бришеме, така што ги отстрануваме врските на неговиот родител кон него, и потоа ги балансираме сите јазли додека не стигнеме нагоре до коренот на стеблото.

Доколку јазелот Т има само едно потстебло, тогаш јазелот Т го отстрануваме, а притоа дете на неговиот родител ќе стане детето на Т.

Доколку јазелот Т има две потстебла, тогаш го бараме најмалиот елемент од неговото десно потстебло т.е. го бараме јазелот L (ја употребувам оваа ознака за да објаснам поубаво, во кодот е имплеменирано со променливи со друго име) кој се наоѓа "најлево" во неговото десно потстебло. Ја отстрануваме врската од неговиот родител кон L и овој јазел го ставаме на местото на Т. Т го отстрануваме. Разбирливо, потоа вршиме балансирање на стеблото од јазелот кој претходно беше родител на L. Овде разгледав специјален случај кога L e дете на T. Малку е покомплицирано да се менуваат врските доколку јазлите се директно поврзани. На крај се одвива балансираност која започнува од претходниот родител на L.

void inorder(Node mom) {
if (mom == null) return;

inorder(mom.left);
System.out.println(mom.value);
inorder(mom.right);
}

void inorderRoot(Node root) {
inorder(root.left);
}

Со повикувањето на inorderRoot(Node root) се врши inorder изминување на стеблото, а тоа значи дека ќе бидат отпечатени вредностите што ги содржи стеблото и тие ќе бидат сортирани во неопаѓачки редослед.

Се надевам дека сега некои работи ќе бидат појасни за AVL стеблата и ќе пробате самите да искодирате AVL стебло. За некои од можните примени на овие интересни и многу ефикасни структури во некоја следна прилика.

Овој код може и да содржи некои bug-ови, па се надевам дека доколку забележете некоја ќе ме информирате, а и јас ќе сменам нешто доколку мислам дека е грешно. На тестирањата кои ги вршев стеблото си ја вршеше добро својата функција.

Доколку сакате повеќе да прочитате за AVL стеблата ви препорачувам:

Introduction to Algorightms
Algorithms in C
http://en.wikipedia.org/wiki/AVL_tree

и уште многу ресурси кои можете да ги најдете пребарувајќи на google
http://www.google.com/search?hl=en&source=hp&q=avl+tree&aq=f&oq=&aqi=g7g-s1g2

Кодот заедно со некои тестови кои ги правев можете да го симнете овде:

http://www.mediafire.com/?2vnjyn2nguj

Збор два за O(logN) и стеблата

Структурите секогаш одат заедно со алгоритмите. Ефикасна имплементација е збир од ефикасни податочни структури и ефикасен алгоритам. Некогаш треба и да се прави компромис. Кај многу решенија големата комплексност може да се намали со користење на добри податочни структури. На пример, кај сортирањето, комплексноста од O(N*N) значи дека за N = 1000000 програмата нема во разумно време да даде решение.

Проблемот на сортирање е добро проучен и познати се алгоритми кои даваат решение во време O(N*logN). Овде ќе ги спомнам merge sort и мојот омилен heap sort. Другите сортирања имаат комлексност од O(N*N) во најлош случај. Но, другите сортирања освен оригиналната низа не користат друга меморија и некои релативно комплицирани структури (со исклучок на некои променливи како бројачи и променливи во кои привремено се чуваат податоци).

Кај merge sort и heap sort приказната е поинаква. Merge sort користи две низи, значи оригиналната низа и уште една низа со иста мемориска големина (едно од следните мои пишувања ќе го посветам целосно на сортирања). Heap sort пак користи само една низа, но таа низа е организирана на друг начин кој овозможува сите операции како вметнување на елемент во структурата, бришење, наоѓање на максимум или минимум да се извршуваат во O(1) или O(logN), овие неколку операции индиректно придонесуваат во она што се бара, сортирање на низата.

Стеблото е структура или поим кој се поврзува со посакуваната комплексност O(logN). Значи директно или индиректно, доколку некој проблем бара решение кое е од ред O(logN), тогаш ние ќе треба да се занимаваме со стебло, иако понекогаш стеблото не е очигледно на прв поглед, овде мислам општо, на стебло како структура и стебло како поим, како логичка организација која во својата суштина го има гранењетo.