Википедија

Бинарно стабло претраге

У информатици, бинарно стабло претраге (БСП), познато и као сортирано бинарно стабло, је бинарно стабло засновано на чворовима, где сваки чвор има упоредљиви кључ (са додељеном вредношћу) и задовољава услов да је вредност сваког чвора већа од вредности сваког чвора у његовом левом подстаблу и мања од вредности сваког чвора у његовом десном подстаблу. Сваки чвор има највише два детета. Свако дете мора да буде или лист (нема ниједно дете) или корен још једног бинарног стабла претраге. БСП је динамичка структура података, и величина БСП-а је ограничена само количином слободне меморије у оперативном систему. Највећа предност бинарног стабла претраге је да остаје уређено, што омогућава брже време претраге него већина других структура. Основна својства бинарног стабла претраге:[1]

  • Лево подстабло чвора садржи само чворове које имају мању вредност од њега.
  • Десно подстабло чвора садржи само чворове које имају већу вредност од њега.
  • Лево и десно подстабло морају такође бити бинарна стабла претраге.
  • Сваки чвор може имати највише 2 детета.
  • Не смеју постојати дупликати чворова.
  • Постоји јединствен пут од корена до сваког чвора.
Бинарно стабло претраге величине 9 и дубине 3, са кореном 8 и листовима 1, 4, 7 и 13

Највећа предност бинарног стабла претраге у односу на остале структуре података је да алгоритми сортирања и алгоритми претраге као нпр. претрага у дубину (ин-ордер) могу бити веома ефикасни. Остале предности су:

  • Бинарно стабло претраге има брзо убацивање и брисање елемената када је балансирано.
  • Код је једноставнији него код осталих структура података.
  • Чува кључеве у чворовима на такав начин да се претрага, убацивање и брисање елемената може урадити ефикасно.
  • Веома једноставна имплементација.
  • Чворови у стаблу су динамички по природи.

Бинарно стабло претраге је фундаментална структура података помоћу које се конструишу апстрактније структуре података као нпр. скупови, мултискупови и асоцијативни низови. Неки од недостатака су:

  • Облик бинарног стабла претраге зависи само од реда убацивања елемената, и може бити дегенерисано.
  • Када убацујемо или тражимо елемент у бинарном стаблу претраге, кључ сваког посећеног чвора мора да се упореди са кључем елемента ког убацујемо или тражимо.
  • Кључеви у бинарном стаблу претраге могу бити дугачки, што може утицати на временску сложеност.

Провера да ли је стабло БСП или није

уреди

Понекад имамо бинарно стабло, и потребно је одредити да ли је оно БСП. Ово је занимљив проблем који има једноставно рекурзивно решење.

БСП својство--сваки чвор у десном подстаблу мора да буде већи од тренутног чвора и сваки чвор у левом подстаблу мора да буде мањи (или једнак) од тренутног чвора--је кључна ствар помоћу које одређујемо да ли је стабло БСП или није. На први поглед, изгледа као да је довољно само да обиђемо стабло, проверимо да ли сваки чвор садржи вредност која је већа од вредности његовог левог детета и мања од вредности његовог десног детета, и ако ово тврђење важи за сваки чвор у стаблу, онда је то БСП. Ово је такозвани "Похлепни приступ". Али, очигледно је да овај приступ неће радити за следеће стабло: 

     20
    /  \
  10    30
       /  \
      5    40

I наведеном стаблу, сваки чвор задовољава услов да садржи вредност већу од његовог левог детета а мању од десног, али ипак, то није БСП: вредност 5 је у десном подстаблу чвора који садржи 20, што није у складу са својством БСП.

Како решити ово? Испоставља се да уместо да донесемо одлуку засновану искључиво на вредности чвора и његове деце, потребне су нам информације које потичу и од родитеља. У претходном примеру, када бисмо запамтили чвор са вредношћу 20, видели бисмо да чвор са вредношћу 5 не задовољава услове БСП.

Тако да, услови које треба да проверимо за сваки чвор су: а) ако је чвор лево дете свог родитеља, онда мора бити мањи (или једнак) од родитеља и мора да пренесе вредност од свог родитеља свом десном подстаблу да би били сигурни да ниједан од чворова у том подстаблу није већа од родитеља, и слично б) ако је чвор десно дете свог родитеља, онда мора бити веће од свог родитеља и мора да пренесе вредност од свог родитеља свом левом подстаблу да би били сигурно да ниједан од чворова у том подстаблу није мањи од родитеља.

Једноставно, али елегантно рекурзивно решење у Јави, може да објасни ово мало боље: 

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

Позив ове функције може изгледати овако: 

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

Разлике између бинарног стабла и бинарног стабла претраге

уреди

Бинарно стабло: Укратко, бинарно стабло је стабло код кога сваки чвор има два највише два детета. У бинарном стаблу, лево и десно дете могу имати вредности независне од вредности родитеља. 

    3
  /   \
 4     5

Бинарно стабло претраге: Код бинарног стабла претраге, лево дете садржи вредност мању од родитеља, а десно дете садржи вредност која је већа од вредности родитеља. 

    4
   / \
  3   5

Операције

уреди

Операције, као што су претрага, код бинарног стабла захтевају поређење између чворова. Ова поређења се обављају са позивима функцији компаратора. Компаратор може бити дефинисам имплицитно или експлицитно, у зависности од језика у коме је имплементирано бинарно стабло претраге. Чест компаратор је мање од функције, на пример, а < б, где су а и б кључеви два чвора а и б у бинарном стаблу претраге.

Претрага

уреди

Претрага бинарног стабла претраге за одређеним кључем може се урадити рекурзивно или итеративно.

Почињемо са кореним чворем. Ако је стабло нулл, онда кључ који тражимо не постоји у стаблу. Ако је кључ једнак корену, онда је претрага готова и враћамо чвор. Ако је кључ мањи од вредности корена, онда претражујемо лево подстабло. Слично томе, ако је кључ већи од корена, претражујемо десно подстабло. Овај процес се понавља све док не пронађемо кључ или преостало подстабло не постане нулл. Ако кључ није пронађен пре него што дођемо до нулл подстабла, онда тај кључ не постоји у стаблу. Ово се лако ради са рекурзивним алгоритмом: 

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)

Исти алгоритам се може имплементирати итеративно: 

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

У најгорем случају, овај алгоритам мора да тражи од корена стабла до листа најдаљег од корена, тако да операција претраге траје пропорцијално висини стабла. У просеку, бинарно стабло претраге са н чворова има висину О (лог н). Али, у најгорем случају, висина може бити и О(н).

Убацивање елемента

уреди

Убацивање елемента почиње исто као и претрага; ако кључ није једнак корену, претражујемо лево или десно подстабло ка малопре. На крају долазимо до екстерног чвора и додајемо нову кључ-вредност (овде као 'неwНоде') као његово лево или десно дете, у зависности од вредности чвора.

Ево како изгледа типично додавање елемента у бинарно стабло претраге у језику 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;
}

Наведена деструктивна функција модификује стабло у месту. Након њеног извршавања, изгубиће се претходна верзија стабла. Друга могућност је да, као у следећем примеру у језику Пyтхон, реконструишемо све претке убаченог чвора; свака референца на оригинално стабло остаје валидна, и тако је стабло стална структура података: 

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


Убацивање елемента у БСП, захтева време пропорционално висини стабла у најгорем случају, а то је О(н). У просечном случају, сложеност је О(лог н).

Брисање елемента

уреди

Постоје три случаја које треба размотрити:

  • Брисање листа (чвора без деце): Брисање листа је лако, само га избацујемо из стабла.
  • Брисање чвора са једним дететом: Брише се чвор, и замењује са својим дететом.
  • Брисање чвора са оба детета: Нека се чвор који бришемо зове Н. Не бришемо Н. Уместо тога, бирамо његовог ин-ордер следбеника, или његовог ин-ордер претходнка, Р. Копирамо вредност Р у Н, и рекурзивно позовемо брисање на Р док не дођемо до неког од прва два случаја.

Чворови са децом су тежи за брисање. Као са свим бинарним стаблима, ин-ордер следбеник чвора је најлевљи чвор у његовом десном подстаблу, а његов ин-ордер претходник је најдешњи елемент у његовом левом подстаблу. Бришемо га у слкаду са једним од два једноставина случаја изнад.

 
Брисање чвора са два детета из бинарног стабла претраге. Прво надјемо најдешњи чвор у левом подстаблу, ин-ордер претходник 6. Копирамо ту вредност у чвор који треба да обришемо. Ин-ордер претходник се онда може лако обрисати, зато што има највише једно дете. Исти метод ради симетрично за ин-ордер следбеника 9.

Уколико често користимо ин-ордер следбеника или ин-ордер претходика за сваки случај са два детета, може доћи до небалансираног стабла, тако да неке имплементације бирају један од та два случаја у различитим тренуцима. 

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)

Обилазак стабла

уреди

Када је бинарно стаблно креирано, можемо вратити његове елементе ин-ордер, рекурзивним обиласком левог подстабла чвора, приступом самом чвору, и онда рекурзивним обиласком десног подстабла чвора, затим настављајући овај шаблон за сваки чвор након што му рекурзивно приступимо. Као са свим бинарним стаблима, имамо и пре-ордер и пост-ордер обилазак, али ниједан није користан за бинарно стабло претраге. Ин-ордер обилазак ће увек вратити сортиран низ елемената чвора.

Код за ин-ордер обилазак у језику Пyтхон: 

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)

Обилазак је сложености О(н) , зато што се мора обићи сваки чвор.

Сортирање

уреди
 

Бинарно стабло претраге се може искористити за имплементацију једноставног, али ефикасног алгоритма за сортирање. Слично као код хеап сорт-а, убацујемо све вредности које желимо да сортирамо у нову структуру података, у овом случају бинарно стабло претраге, и онда га обиђемо ин-ордер обиласком, и добијамо резултат: 

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

Најгори случај build_binary_tree је  —ако му дамо сортирани низ вредности, он их уланча у повезану листу без левог подстабла. На пример, build_binary_tree([1, 2, 3, 4, 5]) ствара стабло трее (1 (2 (3 (4 (5))))).

Постоји неколико начина за избегавање ове мане са једноставним бинарним стаблима; најчешћа је самобалансирајуће бинарно стабло претраге. Ако урадимо исту процедуру користећо такво стабло, најгора сложеност је О(нлог н).

Врсте

уреди

Постоји много врста бинарних стабла претраге. АВЛ-стабла и Црвено-црна стабла су облици самобалансирајућег бинарног стабла претраге. Раширено стабло је бинарно стабло претраге које аутоматски помера елементе којима се често приступа ближе корену. У Треап-у (хеап стабло), сваки чвор чува и (насумично изабран) приоритет и родитељски чвор има виши приоритет од своје деце. Танго стабло су стабла оптимизована за брзу претрагу.

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

Комплетно бинарно стабло је бинарно стабло које је скроз пуно, са могућношћу изузетка доњег нивоа, које је напуњено са лева на десно. У комплетном бинарном стаблу, сви чворови су најлевље могуће. То је стабло са н нивоа, где за сваки ниво д <= н - 1, број постојећих чворова на нивоу д је једнак 2д. Ово значи да сви могући чворови постоје на овим нивоима. Додатан услов за комплетно бинарно стабло је да за н-ти ниво, сви постојећи чворови морају да буду попуњени с лева на десно.

Дегенерисано стабло је стабло где за сваки родитељски чвор, постоји само једно дете чвор. Оно је небалансирано и, у најгорем случају, перформансе се спуштају на ниво повезане листе. Ако функција за додавање чвора не подржава ребалансирање, онда се лако може створити дегенерисано стабло ако му додајемо податке који су већ сортирани. Ово значи да у мерењу перформанси, стабло ће се на крају понашати као повезана листа.

Поређење перформанси

уреди

D. А. Хегер (2004)[2] је објавио поређење перформанси бинарних стабла претраге. Треап има најбоље перформансе у просеку, док Црвено-црна стабла има најмање вариајција у перформансама.

Оптимално бинарно стабло претраге

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

Ако не желимо да модификујемо стабло претраге, и знамо тачно колико често ће се приступати сваком елементу, можемо да конструишемо[3] оптимално бинарно стабло претраге, стабло претраге код кога је просечна цена потраживања елемента минимализована.

Ако не знамо унапред којим редом ће се приступати елементима стабла, можемо да користимо Раширено дрво.



Пример у Пyтхон-у:

импорт сyс импорт рандом

  1. рандом лист генератор

деф рандом_лист (мин, маx, елементс): 

   list = random.sample(range(min, max), elements)
   return list
  1. цласс фор нодес

цласс Ноде : 

   def __init__(self, data) :
       self.p = None
       self.r = None
       self.l = None
       self.data1 = data   
       self.data2 = str(data)
  1. трее цласс

цласс Трее : 

   #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. Тестирање

x = лист()

  1. Тестинг хере

трее = Трее(); А = рандом_лист(0, 20, 10) принт(А) кеy = А[9] кеy_и = А[6] кеy_инвалид = 100

фор и ин ранге(0, лен(А)) : 

   tree.add(A[i])

трее.принт_роот()

  1. тестинг ин ордер wалк

трее.ин_ордер_wалк(трее.роот)

  1. тестинг трее сеарцх

ф_к = трее.трее_сеарцх(трее.роот, кеy) иф (ф_к != Ноне) : 

   print("Found the key", f_k.data1, "and we searched for ", key)

елсе : 

   print("No key", key, "found")

ф_к = трее.трее_сеарцх(трее.роот, кеy_инвалид) иф (ф_к != Ноне) : 

   print("Found the key", f_k.data1, "and we searched for ", key_invalid)

елсе : 

   print("No key", key_invalid, "found")


  1. тестинг итеративе сеарцх

ф_к_и = трее.итеративе_трее_сеарцх(трее.роот, кеy_и) иф (ф_к_и != Ноне) : 

   print("Found the key", f_k_i.data1, "and we searched for ", key_i)

елсе : 

   print("No key", key_i, "found")
  1. тестинг трее минимум

темп = трее.трее_минимум(трее.роот) принт("Трее минимум", темп.дата1)

  1. тестинг трее маxимум

темп = трее.трее_маxимум(трее.роот) принт("Трее минимум", темп.дата1)

  1. тестинг принт парент

трее.принт_паррент(темп) трее.принт_паррент(трее.роот)

  1. Тестинг инсертинг

принт("Инсертинг 110 анд -5 то трее") трее.адд(110) трее.адд(-5) трее.ин_ордер_wалк(трее.роот)

  1. тестинг трее минимум

темп = трее.трее_минимум(трее.роот) принт("Трее минимум", темп.дата1)

  1. тестинг трее маxимум

темп = трее.трее_маxимум(трее.роот) принт("Трее минимум", темп.дата1)

  1. тестинг принт парент

трее.принт_паррент(темп)

  1. Трyинг то делете маxимум

темп = трее.трее_маxимум(трее.роот) трее.делете(темп) принт("Трее афтер делетинг маx") трее.ин_ордер_wалк(трее.роот)

  1. Трyинг то делете минимум

темп = трее.трее_минимум(трее.роот) трее.делете(темп) принт("Трее афтер делетинг мин") трее.ин_ордер_wалк(трее.роот)

принт("########")

трее.ин_ордер_wалк_wитх_ретвал(трее.роот)


фор и ин x : 

   print(i.data1)




Види још

уреди

Референце

уреди
  1. ^ Гилберг, Р.; Фороузан, Б. (2001), „8”, Дата Струцтурес: А Псеудоцоде Аппроацх Wитх C++, Пацифиц Грове, ЦА: Броокс/Цоле, стр. 339, ИСБН 978-0-534-95216-7 
  2. ^ Хегер, Доминиqуе А. (2004), „А Дисqуиситион он Тхе Перформанце Бехавиор оф Бинарy Сеарцх Трее Дата Струцтурес” (ПДФ), Еуропеан Јоурнал фор тхе Информатицс Профессионал, 5 (5): 67—75, Архивирано из оригинала (ПДФ) 27. 03. 2014. г., Приступљено 20. 04. 2014 
  3. ^ Гоннет, Гастон. „Оптимал Бинарy Сеарцх Треес”. Сциентифиц Цомпутатион. ЕТХ Зüрицх. Архивирано из оригинала 30. 08. 2002. г. Приступљено 1. 12. 2013. 

Литература

уреди

Спољашње везе

уреди
 
Бинарно стабло претраге на Викимедијиној остави.
Преузето из „https://sr.wikipedia.org/w/index.php?title=Binarno_stablo_pretrage&oldid=28057103”