Binarno stablo pretrage
<s>U informatici, binarno stablo pretrage (BSP), poznato i kao sortirano binarno stablo, je binarno stablo zasnovano na čvorovima, gde svaki čvor ima uporedljivi ključ (sa dodeljenom vrednošću) i zadovoljava uslov da je vrednost svakog čvora veća od vrednosti svakog čvora u njegovom levom podstablu i manja od vrednosti svakog čvora u njegovom desnom podstablu.</s><s>Svaki čvor ima najviše dva deteta.</s><s>Svako dete mora da bude ili list (nema nijedno dete) ili koren još jednog binarnog stabla pretrage.</s><s>BSP je dinamička struktura podataka, i veličina BSP-a je ograničena samo količinom slobodne memorije u operativnom sistemu.</s><s>Najveća prednost binarnog stabla pretrage je da ostaje uređeno, što omogućava brže vreme pretrage nego večina drugih struktura.</s><s>Osnovna svojstva binarnog stabla pretrage:
 Levo podstablo čvora sadrži samo čvorove koje imaju manju vrednost od njega.</s><s>Desno podstablo čvora sadrži samo čvorove koje imaju veću vrednost od njega.</s><s>Levo i desno podstablo moraju takođe biti binarna stabla pretrage.</s><s>Svaki čvor može imati najviše 2 deteta.</s><s>Ne smeju postojati duplikati čvorova.</s><s>Postoji jedinstven put od korena do svakog čvora.</s>

<s>Najveća prednost binarnog stabla pretrage u odnosu na ostale strukture podataka je da algoritmi sortiranja i algoritmi pretrage kao npr. pretraga u dubinu (in-order) mogu biti veoma efikasni.</s><s>Ostale prednosti su:
 Binarno stablo pretrage ima brzo ubacivanje i brisanje elemenata kada je balansirano.</s><s>Kod je jednostavniji nego kod ostalih struktura podataka.</s><s>Čuva ključeve u čvorovima na takav način da se pretraga, ubacivanje i brisanje elemenata može uraditi efikasno.</s><s>Veoma jednostavna implementacija.</s><s>Čvorovi u stablu su dinamički po prirodi.</s><s>Binarno stablo pretrage je fundamentalna struktura podataka pomoću koje se konstruišu apstraktnije strukture podataka kao npr. skupovi, multiskupovi i asocijativni nizovi.</s><s>Neki od nedostataka su:</s>

<s>Oblik binarnog stabla pretrage zavisi samo od reda ubacivanja elemenata, i može biti degenerisano.</s><s>Kada ubacujemo ili tražimo element u binarnom stablu pretrage, ključ svakog posećenog čvora mora da se uporedi sa ključem elementa kog ubacujemo ili tražimo.</s><s>Ključevi u binarnom stablu pretrage mogu biti dugački, što može uticati na vremensku složenost.</s>

<s>Provera da li je stablo BSP ili nije</s>

<s>Ponekad imamo binarno stablo, i potrebno je odrediti da li je ono BSP.</s><s>Ovo je zanimljiv problem koji ima jednostavno rekurzivno rešenje.</s>

<s>BSP svojstvo--svaki čvor u desnom podstablu mora da bude veći od trenutnog čvora i svaki čvor u levom podstablu mora da bude manji (ili jednak) od trenutnog čvora--je ključna stvar pomoću koje određujemo da li je stablo BSP ili nije.</s><s>Na prvi pogled, izgleda kao da je dovoljno samo da obiđemo stablo, proverimo da li svaki čvor sadrži vrednost koja je veća od vrednosti njegovog levog deteta i manja od vrednosti njegovog desnog deteta, i ako ovo tvrđenje važi za svaki čvor u stablu, onda je to BSP.</s><s>Ovo je takozvani "Pohlepni pristup".</s><s>Ali, očigledno je da ovaj pristup neće raditi za sledeće stablo:</s>

<s>20
     /  \
   10    30
        /  \
       5    40</s>

<s>I navedenom stablu, svaki čvor zadovoljava uslov da sadrži vrednost veću od njegovog levog deteta a manju od desnog, ali ipak, to nije BSP: vrednost 5 je u desnom podstablu čvora koji sadrži 20, što nije u skladu sa svojstvom BSP.</s>

<s>Kako rešiti ovo?</s><s>Ispostavlja se da umesto da donesemo odluku zasnovanu isključivo na vrednosti čvora i njegove dece, potrebne su nam informacije koje potiču i od roditelja.</s><s>U prethodnom primeru, kada bismo zapamtili čvor sa vrednošću 20, videli bismo da čvor sa vrednošću 5 ne zadovoljava uslove BSP.</s>

<s>Tako da, uslovi koje treba da proverimo za svaki čvor su: a) ako je čvor levo dete svog roditelja, onda mora biti manji (ili jednak) od roditelja i mora da prenese vrednost od svog roditelja svom desnom podstablu da bi bili sigurni da nijedan od čvorova u tom podstablu nije veća od roditelja, i slično b) ako je čvor desno dete svog roditelja, onda mora biti veće od svog roditelja i mora da prenese vrednost od svog roditelja svom levom podstablu da bi bili sigurno da nijedan od čvorova u tom podstablu nije manji od roditelja.</s>

<s>Jednostavno, ali elegantno rekurzivno rešenje u Javi, može da objasni ovo malo bolje:</s>

<s>public static boolean isBST(TreeNode node, int leftData, int rightData)
    {
    if (node == null)
        return true;
    
    if (node.getData() > leftData || node.getData() <= rightData)
        return false;
    
    return (isBST(node.left, node.getData(), rightData) && isBST(node.right, leftData, node.getData()));
    }</s>

<s>Poziv ove funkcije može izgledati ovako:</s>

<s>if(isBST(root, Integer.</s><s>MAX_VALUE, Integer.</s><s>MIN_VALUE))
         System.out.println("This is a BST.");
    else
         System.out.println("This is NOT a BST!");</s>

<s>Razlike između binarnog stabla i binarnog stabla pretrage</s>

<s>Binarno stablo: Ukratko, binarno stablo je stablo kod koga svaki čvor ima dva najviše dva deteta.</s><s>U binarnom stablu, levo i desno dete mogu imati vrednosti nezavisne od vrednosti roditelja.</s>

<s>3
   /   \
  4     5</s>

<s>Binarno stablo pretrage: Kod binarnog stabla pretrage, levo dete sadrži vrednost manju od roditelja, a desno dete sadrži vrednost koja je veća od vrednosti roditelja.</s>

<s>4
    / \
   3   5</s>

<s>Operacije 
Operacije, kao što su pretraga, kod binarnog stabla zahtevaju poređenje između čvorova.</s><s>Ova poređenja se obavljaju sa pozivima funkciji komparatora.</s><s>Komparator može biti definisam implicitno ili eksplicitno, u zavisnosti od jezika u kome je implementirano binarno stablo pretrage. can be explicitly or implicitly defined, depending on the language in which the binary search tree was implemented.</s><s>Čest komparator je manje od funkcije, na primer, a < b, gde su a i b ključevi dva čvora a i b u binarnom stablu pretrage.</s>

<s>Pretraga 
Pretraga binarnog stabla pretrage za određenim ključem može se uraditi rekurzivno ili iterativno.</s>

<s>Počinjemo sa korenim čvorem.</s><s>Ako je stablo null, onda ključ koji tražimo ne postoji u stablu.</s><s>Ako je ključ jednak korenu, onda je pretraga gotova i vraćamo čvor.</s><s>Ako je ključ manji od vrednosti korena, onda pretražujemo levo podstablo.</s><s>Slično tome, ako je ključ veći od korena, pretražujemo desno podstablo.</s><s>Ovaj proces se ponavlja sve dok ne pronađemo ključ ili preostalo podstablo ne postane null.</s><s>Ako ključ nije pronađen pre nego što dođemo do null podstabla, onda taj ključ ne postoji u stablu.</s><s>Ovo se lako radi sa rekurzivnim algoritmom:</s>

<s>function Find-recursive(key, node):  // call initially with node = root
     if node = Null or node.key = key then
         return node
     else if key < node.key then
         return Find-recursive(key, node.left)
     else
         return Find-recursive(key, node.right)
Isti algoritam se može implementirati iterativno:
 function Find(key, root):
     current-node := root
     while current-node is not Null do
         if current-node.key = key then
             return current-node
         else if key < current-node.key then
             current-node := current-node.left
         else
             current-node := current-node.right
     return Null</s>

<s>U najgorem slučaju, ovaj algoritam mora da traži od korena stabla do lista najdaljeg od korena, tako da operacija pretrage traje proporcijalno visini stabla.</s><s>U proseku, binarno stablo pretrage sa n čvorova ima visinu O (log n).</s><s>Ali, u najgorem slučaju, visina može biti i O(n).</s>

<s>Ubacivanje elementa 
Ubacivanje elementa počinje isto kao i pretraga; ako ključ nije jednak korenu, pretražujemo levo ili desno podstablo ka malopre.</s><s>Na kraju dolazimo do eksternog čvora i dodajemo novu ključ-vrednost (ovde kao 'newNode') kao njegovo levo ili desno dete, u zavisnosti od vrednosti čvora.</s>

<s>Evo kako izgleda tipično dodavanje elementa u binarno stablo pretrage u jeziku C++:</s>

<s>void insert(Node*& root, int data) {
  if (!root) 
    root = new Node(data);
  else if (data < root->data)
    insert(root->left, data);
  else if (data > root->data)
    insert(root->right, data);
  return;
}</s>

<s>Navedena destruktivna funkcija modifikuje stablo u mestu.</s><s>Nakon njenog izvršavanja, izgubiće se prethodna verzija stabla.</s><s>Druga mogućnost je da, kao u sledećem primeru u jeziku Python, rekonstruišemo sve pretke ubačenog čvora; svaka referenca na originalno stablo ostaje validna, i tako je stablo stalna struktura podataka:</s>

<s>def binary_tree_insert(node, key, value):
     if node is None:
         return TreeNode(None, key, value, None)
     if key == node.key:
         return TreeNode(node.left, key, value, node.right)
     if key < node.key:
         return TreeNode(binary_tree_insert(node.left, key, value), node.key, node.value, node.right)
     else:
         return TreeNode(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))</s>

<s>Ubacivanje elementa u BSP, zahteva vreme proporcionalno visini stabla u najgorem slučaju, a to je O(n).</s><s>U prosečnom slučaju, složenost je O(log n).</s>

<s>Brisanje elementa 
Postoje tri slučaja koje treba razmotriti: 
 Brisanje lista (čvora bez dece): Brisanje lista je lako, samo ga izbacujemo iz stabla.</s><s>Brisanje čvora sa jednim detetom: Briše se čvor, i zamenjuje sa svojim detetom.</s><s>Brisanje čvora sa oba deteta: Neka se čvor koji brišemo zove N. Ne brišemo N. Umesto toga, biramo njegovog in-order sledbenika, ili njegovog in-order prethodnka, R. Kopiramo vrednost R u N, i rekurzivno pozovemo brisanje na R dok ne dođemo do nekog od prva dva slučaja.</s>

<s>Čvorovi sa decom su teži za brisanje.</s><s>Kao sa svim binarnim stablima, in-order sledbenik čvora je najlevlji čvor u njegovom desnom podstablu, a njegov in-order prethodnik je najdešnji element u njegovom levom podstablu.</s><s>Brišemo ga u slkadu sa jednim od dva jednostavina slučaja iznad.</s>

<s>Ukoliko često koristimo in-order sledbenika ili in-order prethodika za svaki slučaj sa dva deteta, može doći do nebalansiranog stabla, tako da neke implementacije biraju jedan od ta dva slučaja u različitim trenucima.</s>

<s>def find_min(self): # Gets minimum node (leftmost leaf) in a subtree
    current_node = self
    while current_node.left_child:
        current_node = current_node.left_child
    return current_node</s>

<s>def replace_node_in_parent(self, new_value=None):
    if self.parent:
        if self == self.parent.left_child:
            self.parent.left_child = new_value
        else:
            self.parent.right_child = new_value
    if new_value:
        new_value.parent = self.parent</s>

<s>def binary_tree_delete(self, key):
    if key < self.key:
        self.left_child.binary_tree_delete(key)
    elif key > self.key:
        self.right_child.binary_tree_delete(key)
    else: # delete the key here
        if self.left_child and self.right_child: # if both children are present
            successor = self.right_child.find_min()
            self.key = successor.key
            successor.binary_tree_delete(successor.key)
        elif self.left_child:   # if the node has only a *left* child
            self.replace_node_in_parent(self.left_child)
        elif self.right_child:  # if the node has only a *right* child
            self.replace_node_in_parent(self.right_child)
        else: # this node has no children
            self.replace_node_in_parent(None)</s>

<s>Obilazak stabla</s>

<s>Kada je binarno stablno kreirano, možemo vratiti njegove elemente in-order, rekurzivnim obilaskom levog podstabla čvora, pristupom samom čvoru, i onda rekurzivnim obilaskom desnog podstabla čvora, zatim nastavljajući ovaj šablon za svaki čvor nakon što mu rekurzivno pristupimo.</s><s>Kao sa svim binarnim stablima, imamo i pre-order i post-order obilazak, ali nijedan nije koristan za binarno stablo pretrage.</s><s>In-order obilazak će uvek vratiti sortiran niz elemenata čvora.</s>

<s>Kod za in-order obilazak u jeziku Python:</s>

<s>def traverse_binary_tree(node, callback):
    if node is None:
        return
    traverse_binary_tree(node.leftChild, callback)
    callback(node.value)
    traverse_binary_tree(node.rightChild, callback)</s>

<s>Obilazak je složenosti O(n) , zato što se mora obići svaki čvor.</s>

<s>Sortiranje</s>

<s>Binarno stablo pretrage se može iskoristiti za implementaciju jednostavnog, ali efikasnog algoritma za sortiranje.</s><s>Slično kao kod heap sort-a, ubacujemo sve vrednosti koje želimo da sortiramo u novu strukturu podataka, u ovom slučaju binarno stablo pretrage, i onda ga obiđemo in-order obilaskom, i dobijamo rezultat:</s>

<s>def build_binary_tree(values):
    tree = None
    for v in values:
        tree = binary_tree_insert(tree, v)
    return tree</s>

<s>def get_inorder_traversal(root):
    '''
    Returns a list containing all the values in the tree, starting at *root*.</s><s>Traverses the tree in-order(leftChild, root, rightChild).
    '''
    result = []
    traverse_binary_tree(root, lambda element: result.append(element))
    return result</s>

<s>Najgori slučaj build_binary_tree je —ako mu damo sortirani niz vrednosti, on ih ulanča u povezanu listu bez levog podstabla.</s><s>Na primer, build_binary_tree([1, 2, 3, 4, 5]) stvara stablo tree (1 (2 (3 (4 (5))))).</s>

<s>Postoji nekoliko načina za izbegavanje ove mane sa jednostavnim binarnim stablima; najčešća je samobalansirajuće binarno stablo pretrage.</s><s>Ako uradimo istu proceduru koristećo takvo stablo, najgora složenost je O(nlog n).</s>

<s>Vrste 
Postoji mnogo vrsta binarnih stabla pretrage.</s><s>AVL-stabla i Crveno-crna stabla su oblici samobalansirajućeg binarnog stabla pretrage.</s><s>Rašireno stablo je binarno stablo pretrage koje automatski pomera elemente kojima se često pristupa bliže korenu.</s><s>U Treap-u (heap stablo), svaki čvor čuva i (nasumično izabran) prioritet i roditeljski čvor ima viši prioritet od svoje dece.</s><s>Tango stablo su stabla optimizovana za brzu pretragu.</s>

<s>Druga dva prideva koja opisuju binarno stablo pretrage su kompletno i degenerisano stablo.</s>

<s>Kompletno binarno stablo je binarno stablo koje je skroz puno, sa mogućnošću izuzetka donjeg nivoa, koje je napunjeno sa leva na desno.</s><s>U kompletnom binarnom stablu, svi čvorovi su najlevlje moguće.</s><s>To je stablo sa n nivoa, gde za svaki nivo d <= n - 1, broj postojećih čvorova na nivou d je jednak 2d. Ovo znači da svi mogući čvorovi postoje na ovim nivoima.</s><s>Dodatan uslov za kompletno binarno stablo je da za n-ti nivo, svi postojeći čvorovi moraju da budu popunjeni s leva na desno.</s>

<s>Degenerisano stablo je stablo gde za svaki roditeljski čvor, postoji samo jedno dete čvor.</s><s>Ono je nebalansirano i, u najgorem slučaju, performanse se spuštaju na nivo povezane liste.</s><s>Ako funkcija za dodavanje čvora ne podržava rebalansiranje, onda se lako može stvoriti degenerisano stablo ako mu dodajemo podatke koji su već sortirani.</s><s>Ovo znači da u merenju performansi, stablo će se na kraju ponašati kao povezana lista.</s>

<s>Poređenje performansi 
D. A. Heger (2004) je objavio poređenje performansi binarnih stabla pretrage.</s><s>Treap ima najbolje performanse u proseku, dok Crveno-crna stabla ima najmanje variajcija u performansama.</s>

<s>Optimalno binarno stablo pretrage</s>

<s>Ako ne želimo da modifikujemo stablo pretrage, i znamo tačno koliko često će se pristupati svakom elementu, možemo da konstruišemo  optimalno binarno stablo pretrage, stablo pretrage kod koga je prosečna cena potraživanja elementa minimalizovana.</s>

<s>Ako ne znamo unapred kojim redom će se pristupati elementima stabla, možemo da koristimo Rašireno drvo.</s>

<s>Primer u Python-u:</s>

<s>import sys
import random</s>

<s>random list generator
def random_list (min, max, elements):
    list = random.sample(range(min, max), elements)
    return list</s>

<s>class for nodes
class Node :
    def __init__(self, data) :
        self.p = None
        self.r = None
        self.l = None
        self.data1 = data   
        self.data2 = str(data)</s>

<s>tree class
class Tree :
    #root is only field
    
    #constructor
    def __init__(self) :
        self.root = None</s>

<s>#method for adding nodes to tree
    def add(self, val) : #same as insert method from PDF
        if(self.root == None) :
            self.root = Node(val)
        else :
            self._add(val, self.root)</s>

<s>#side method for recursive adding
    def _add(self, val, node) :
        #if less add it to left side
        if(val < node.data1) :
            if(node.l != None) :
                self._add(val, node.l)
            else :
                node.l = Node(val)
                node.l.p = node
        #if val is greater add it to right side
        else :
            if(node.r != None) :
                self._add(val, node.r)
            else :
                node.r = Node(val)
                node.r.p = node</s>

<s>#In-Order-Walk
    def in_order_walk(self, node) :
        if(node != None) :
            self.in_order_walk(node.l)
            print("print node data : ", node.data1, node.data2)
            self.in_order_walk(node.r)</s>

<s>#Print-root
    def print_root(self) :
        print("Data in root node", self.root.data1, self.root.data2)</s>

<s>#Search the tree for wanted key
    def tree_search(self, current, key) :
        if (current == None or key == current.data1) :
            return current
        if (key < current.data1) :
            return self.tree_search(current.l, key)
        else :
            return self.tree_search(current.r, key)</s>

<s>#Search the tree for wanted key iterative way
    def iterative_tree_search(self, current, key) :
        while (current != None and key != current.data1) :
            if (key  < current.data1) :
                current = current.l
            else :
                current = current.r
        return current</s>

<s>#Find the tree minimum
    def tree_minimum(self, node) :
        while (node.l != None) :
            node = node.l
        return node</s>

<s>#Find tree maximum
    def tree_maximum(self, node) :
        while(node.r != None) :
            node = node.r
        return node</s>

<s>#Print node's parent
    def print_parrent(self, node) :
        if (node.p != None) :
            print("Parent node of node ", node.data1, "is", node.p.data1)
        else :
            print("The node ", node.data1, "is root")</s>

<s>#Transplant
    def transplant(self, u, v) :
        if (u.p == None) :
            self.root = v
        elif (u == u.p.l) :
            u.p.l = v
        else :
            u.p.r = v
        if (v != None) :
            v.p = u.p</s>

<s>#Deleting node
    def delete(self, node) :
        if (node.l == None) :
            self.transplant(node, node.r)
        elif (node.r == None) :
            self.transplant(node, node.l)
        else :
            y = self.tree_minimum(node.r)
            if (y.p != z) :
                self.transplant(y, y.r)
                y.r = node.r
                y.r.p = y
            self.transplant(node, y)
            y.l = node.l
            y.l.p = y</s>

<s>#In-Order-Walk-With-RetVal
    def in_order_walk_with_retval(self, node) :
        global x
        if(node != None) :
            self.in_order_walk_with_retval(node.l)
            x.append(node)
            self.in_order_walk_with_retval(node.r)</s>

<s>Testiranje 
x = list()</s>

<s>Testing here
tree = Tree();
A = random_list(0, 20, 10)
print(A)
key = A[9]
key_i = A[6]
key_invalid = 100</s>

<s>for i in range(0, len(A)) :
    tree.add(A[i])</s>

<s>tree.print_root()</s>

<s>testing in order walk
tree.in_order_walk(tree.root)</s>

<s>testing tree search
f_k = tree.tree_search(tree.root, key)
if (f_k != None) : 
    print("Found the key", f_k.data1, "and we searched for ", key)
else :
    print("No key", key, "found")</s>

<s>f_k = tree.tree_search(tree.root, key_invalid)
if (f_k != None) : 
    print("Found the key", f_k.data1, "and we searched for ", key_invalid)
else :
    print("No key", key_invalid, "found")</s>

<s>testing iterative search
f_k_i = tree.iterative_tree_search(tree.root, key_i)
if (f_k_i != None) : 
    print("Found the key", f_k_i.data1, "and we searched for ", key_i)
else :
    print("No key", key_i, "found")</s>

<s>testing tree minimum
temp = tree.tree_minimum(tree.root)
print("Tree minimum", temp.data1)</s>

<s>testing tree maximum
temp = tree.tree_maximum(tree.root)
print("Tree minimum", temp.data1)</s>

<s>testing print parent
tree.print_parrent(temp)
tree.print_parrent(tree.root)</s>

<s>Testing inserting
print("Inserting 110 and -5 to tree")
tree.add(110)
tree.add(-5)
tree.in_order_walk(tree.root)
 testing tree minimum
temp = tree.tree_minimum(tree.root)
print("Tree minimum", temp.data1)
 testing tree maximum
temp = tree.tree_maximum(tree.root)
print("Tree minimum", temp.data1)</s>

<s>testing print parent
tree.print_parrent(temp)</s>

<s>Trying to delete maximum
temp = tree.tree_maximum(tree.root)
tree.delete(temp)
print("Tree after deleting max")
tree.in_order_walk(tree.root)</s>

<s>Trying to delete minimum
temp = tree.tree_minimum(tree.root)
tree.delete(temp)
print("Tree after deleting min")
tree.in_order_walk(tree.root)</s>

<s>print("########")</s>

<s>tree.in_order_walk_with_retval(tree.root)</s>

<s>for i in x :
    print(i.data1)</s>

<s>Vidi još 
 Samobalansirajuće binarno stablo pretrage
 Binarna pretraga
 Treap
 Tango stablo
 Crveno-crno stablo
 AVL-stablo</s>

<s>Reference</s>

<s>Literatura</s>

<s>Spoljašnje veze 
 Literate implementations of binary search trees in various languages  on LiteratePrograms
  Includes an iterative C# implementation of AVL trees.</s><s>C implementation using GLib.</s><s>Binary Tree Visualizer (JavaScript animation of various BT-based data structures)
 
  C++ implementation.</s><s>Binary Search Tree Example in Python
  Gives an example binary tree implementation.</s>

<s>Binarna stabla
Stabla (strukture podataka)</s>

