Binarno stablo pretrage

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. Svaki čvor ima najviše dva deteta. Svako dete mora da bude ili list (nema nijedno dete) ili koren još jednog binarnog stabla pretrage. BSP je dinamička struktura podataka, i veličina BSP-a je ograničena samo količinom slobodne memorije u operativnom sistemu. Najveća prednost binarnog stabla pretrage je da ostaje uređeno, što omogućava brže vreme pretrage nego večina drugih struktura. Osnovna svojstva binarnog stabla pretrage:
* Levo podstablo čvora sadrži samo čvorove koje imaju manju vrednost od njega.
* Desno podstablo čvora sadrži samo čvorove koje imaju veću vrednost od njega.
* Levo i desno podstablo moraju takođe biti binarna stabla pretrage.
* Svaki čvor može imati najviše 2 deteta.
* Ne smeju postojati duplikati čvorova.
* Postoji jedinstven put od korena do svakog čvora.

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. Ostale prednosti su:
* Binarno stablo pretrage ima brzo ubacivanje i brisanje elemenata kada je balansirano.
* Kod je jednostavniji nego kod ostalih struktura podataka.
* Čuva ključeve u čvorovima na takav način da se pretraga, ubacivanje i brisanje elemenata može uraditi efikasno.
* Veoma jednostavna implementacija.
* Čvorovi u stablu su dinamički po prirodi.
Binarno stablo pretrage je fundamentalna struktura podataka pomoću koje se konstruišu apstraktnije strukture podataka kao npr. skupovi, multiskupovi i asocijativni nizovi. Neki od nedostataka su:

* Oblik binarnog stabla pretrage zavisi samo od reda ubacivanja elemenata, i može biti degenerisano.
* 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.
* Ključevi u binarnom stablu pretrage mogu biti dugački, što može uticati na vremensku složenost.

## Provera da li je stablo BSP ili nije

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

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. 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. Ovo je takozvani "Pohlepni pristup". Ali, očigledno je da ovaj pristup neće raditi za sledeće stablo:

      20
     /  \
   10    30
        /  \
       5    40

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.

Kako rešiti ovo? 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. U prethodnom primeru, kada bismo zapamtili čvor sa vrednošću 20, videli bismo da čvor sa vrednošću 5 ne zadovoljava uslove BSP.

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.

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

    public static boolean isBST(TreeNode node, int leftData, int rightData)
    {
    if (node == null)
        return true;
    
    if (node.getData() > leftData || node.getData() Find-recursive(key, node):  *// call initially with node = root*
     **if** node = Null **or** node.key = key **then**
         **return** node
     **else if** key 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 
void insert(Node*& root, int data) {
  if (!root) 
    root = new Node(data);
  else if (data data)
    insert(root->left, data);
  else if (data > root->data)
    insert(root->right, data);
  return;
}


Navedena *destruktivna* funkcija modifikuje stablo u mestu. Nakon njenog izvršavanja, izgubiće se prethodna verzija stabla. 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*:


```python
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))
```


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

### Brisanje elementa
Postoje tri slučaja koje treba razmotriti: 
* **Brisanje lista (čvora bez dece):** Brisanje lista je lako, samo ga izbacujemo iz stabla.
* **Brisanje čvora sa jednim detetom:** Briše se čvor, i zamenjuje sa svojim detetom.
* **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.

Čvorovi sa decom su teži za brisanje. 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. Brišemo ga u slkadu sa jednim od dva jednostavina slučaja iznad.

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.


```python
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

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

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)
```


### Obilazak stabla

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. Kao sa svim binarnim stablima, imamo i pre-order i post-order obilazak, ali nijedan nije koristan za binarno stablo pretrage. In-order obilazak će uvek vratiti sortiran niz elemenata čvora.

Kod za in-order obilazak u jeziku Python:


```python
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)
```


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

### Sortiranje

Binarno stablo pretrage se može iskoristiti za implementaciju jednostavnog, ali efikasnog algoritma za sortiranje. 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:


```python
def build_binary_tree(values):
    tree = None
    for v in values:
        tree = binary_tree_insert(tree, v)
    return tree

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


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

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

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

Druga dva prideva koja opisuju binarno stablo pretrage su *kompletno* i *degenerisano* stablo.

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

Degenerisano stablo je stablo gde za svaki roditeljski čvor, postoji samo jedno dete čvor. Ono je nebalansirano i, u najgorem slučaju, performanse se spuštaju na nivo povezane liste. 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. Ovo znači da u merenju performansi, stablo će se na kraju ponašati kao povezana lista.
 
### Poređenje performansi
D. A. Heger (2004) je objavio poređenje performansi binarnih stabla pretrage. Treap ima najbolje performanse u proseku, dok Crveno-crna stabla ima najmanje variajcija u performansama.

### Optimalno binarno stablo pretrage

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.

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

**Primer u Python-u:
**

import sys
import random

# random list generator
def random_list (min, max, elements):
    list = random.sample(range(min, max), elements)
    return list

# 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)

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

    #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)

    #side method for recursive adding
    def _add(self, val, node) :
        #if less add it to left side
        if(val 
* Samobalansirajuće binarno stablo pretrage
* Binarna pretraga
* Treap
* Tango stablo
* Crveno-crno stablo
* AVL-stablo


## Reference

## Literatura
* 
* 
* 
* 
* 
* 

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