From Wikipedia, the free encyclopedia
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]
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
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 je fundamentalna struktura podataka pomoću koje se konstruišu apstraktnije strukture podataka kao npr. skupovi, multiskupovi i asocijativni nizovi. Neki od nedostataka su:
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!");
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, 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 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 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).
Postoje tri slučaja koje treba razmotriti:
Č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.
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)
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.
.png)
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).
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.
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.
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
def random_list (min, max, elements):
list = random.sample(range(min, max), elements) return list
class Node :
def __init__(self, data) :
self.p = None
self.r = None
self.l = None
self.data1 = data
self.data2 = str(data)
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)
x = list()
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()
tree.in_order_walk(tree.root)
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")
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")
temp = tree.tree_minimum(tree.root) print("Tree minimum", temp.data1)
temp = tree.tree_maximum(tree.root) print("Tree minimum", temp.data1)
tree.print_parrent(temp) tree.print_parrent(tree.root)
print("Inserting 110 and -5 to tree") tree.add(110) tree.add(-5) tree.in_order_walk(tree.root)
temp = tree.tree_minimum(tree.root) print("Tree minimum", temp.data1)
temp = tree.tree_maximum(tree.root) print("Tree minimum", temp.data1)
tree.print_parrent(temp)
temp = tree.tree_maximum(tree.root) tree.delete(temp) print("Tree after deleting max") tree.in_order_walk(tree.root)
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)
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
