Пређи на садржај

Binarno stablo pretrage

С Википедије, слободне енциклопедије
Binarno stablo pretrage veličine 9 i dubine 3, sa korenom 8 i listovima 1, 4, 7 i 13

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:[1]

  • 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() <= rightData)
       return false;
   
   return (isBST(node.left, node.getData(), rightData) && isBST(node.right, leftData, node.getData()));
   }

Poziv ove funkcije može izgledati ovako: 

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

Razlike između binarnog stabla i binarnog stabla pretrage

[уреди | уреди извор]

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

    3
  /   \
 4     5

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. 

    4
   / \
  3   5

Operacije

[уреди | уреди извор]

Operacije, kao što su pretraga, kod binarnog stabla zahtevaju poređenje između čvorova. Ova poređenja se obavljaju sa pozivima funkciji komparatora. Komparator može biti definisam implicitno ili eksplicitno, u zavisnosti od jezika u kome je implementirano binarno stablo pretrage. Č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.

Pretraga

[уреди | уреди извор]

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

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

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

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. U proseku, binarno stablo pretrage sa n čvorova ima visinu O (log n). Ali, u najgorem slučaju, visina može biti i O(n).

Ubacivanje elementa

[уреди | уреди извор]

Ubacivanje elementa počinje isto kao i pretraga; ako ključ nije jednak korenu, pretražujemo levo ili desno podstablo ka malopre. 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.

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

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

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: 

 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.

Brisanje čvora sa dva deteta iz binarnog stabla pretrage. Prvo nadjemo najdešnji čvor u levom podstablu, in-order prethodnik 6. Kopiramo tu vrednost u čvor koji treba da obrišemo. In-order prethodnik se onda može lako obrisati, zato što ima najviše jedno dete. Isti metod radi simetrično za in-order sledbenika 9.

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. 

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: 

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: 

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 —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(nlog 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 (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 <= n - 1, broj postojećih čvorova na nivou d je jednak 2d. 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)[2] 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

[уреди | уреди извор]
Rotacija stabla je veoma česta interna operacija u binarnim stablima, da bi se održao savršen ili blizak-savršenom, interni balans u stablu.

Ako ne želimo da modifikujemo stablo pretrage, i znamo tačno koliko često će se pristupati svakom elementu, možemo da konstruišemo[3] 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

  1. random list generator

def random_list (min, max, elements): 

   list = random.sample(range(min, max), elements)
   return list
  1. 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)
  1. 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 < 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

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

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

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

   #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

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

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

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

   #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   

   #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

   #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)
  1. Testiranje

x = list()

  1. Testing here

tree = Tree(); A = random_list(0, 20, 10) print(A) key = A[9] key_i = A[6] key_invalid = 100

for i in range(0, len(A)) : 

   tree.add(A[i])

tree.print_root()

  1. testing in order walk

tree.in_order_walk(tree.root)

  1. 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")

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


  1. 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")
  1. testing tree minimum

temp = tree.tree_minimum(tree.root) print("Tree minimum", temp.data1)

  1. testing tree maximum

temp = tree.tree_maximum(tree.root) print("Tree minimum", temp.data1)

  1. testing print parent

tree.print_parrent(temp) tree.print_parrent(tree.root)

  1. Testing inserting

print("Inserting 110 and -5 to tree") tree.add(110) tree.add(-5) tree.in_order_walk(tree.root)

  1. testing tree minimum

temp = tree.tree_minimum(tree.root) print("Tree minimum", temp.data1)

  1. testing tree maximum

temp = tree.tree_maximum(tree.root) print("Tree minimum", temp.data1)

  1. testing print parent

tree.print_parrent(temp)

  1. Trying to delete maximum

temp = tree.tree_maximum(tree.root) tree.delete(temp) print("Tree after deleting max") tree.in_order_walk(tree.root)

  1. Trying to delete minimum

temp = tree.tree_minimum(tree.root) tree.delete(temp) print("Tree after deleting min") tree.in_order_walk(tree.root)

print("########")

tree.in_order_walk_with_retval(tree.root)


for i in x : 

   print(i.data1)




Vidi još

[уреди | уреди извор]

Reference

[уреди | уреди извор]
  1. ^ Gilberg, R.; Forouzan, B. (2001), „8”, Data Structures: A Pseudocode Approach With C++, Pacific Grove, CA: Brooks/Cole, стр. 339, ISBN 978-0-534-95216-7 
  2. ^ Heger, Dominique A. (2004), „A Disquisition on The Performance Behavior of Binary Search Tree Data Structures” (PDF), European Journal for the Informatics Professional, 5 (5): 67—75, Архивирано из оригинала (PDF) 27. 03. 2014. г., Приступљено 20. 04. 2014 
  3. ^ Gonnet, Gaston. „Optimal Binary Search Trees”. Scientific Computation. ETH Zürich. Архивирано из оригинала 30. 08. 2002. г. Приступљено 1. 12. 2013. 

Literatura

[уреди | уреди извор]

Spoljašnje veze

[уреди | уреди извор]
Binarno stablo pretrage на Викимедијиној остави.
Преузето из „https://sr.wikipedia.org/w/index.php?title=Binarno_stablo_pretrage&oldid=28057103”