Obilazak stabla

U informatici, pod obilaskom stabala smatra se proces posećivanja svakog čvora u stablu (struktura podataka), tačno jednom, sistematski. Ovakvi obilasci se klasifikuju po redu u kojem su čvorovi posećeni. Sledeći algoritmi su opisani za binarno stablo, ali mogu se generalizovati za ostala stabla, takođe.

Vrste

U poređenju sa linearnim strukturama podataka kao što su povezane liste i jednodimenzionalnim nizovima, koji koriste kanonski metod obilaska, strukture stabala mogu se obići na mnogo različitih načina. Počevši od korena binarnog stabla, postoje tri glavna koraka koja se mogu izvesti a red po kojem su izvedeni definiše vrstu obilaska. Ovi koraci (bez nekog određenog reda) su: izvođenje akcije na trenutnom čvoru („posećivanje“ čvora), obilazak na levi sin čvora i obilazak na desni sin čvora.

Obilazak stabla prestavlja povezivanje svih čvorova u petlju na neki način. Zato što od jednog datog čvora postoji više mogućih sledećih čvorova (to nije linearna struktura podataka), onda, kod sekvencijalnog računanja (ne paralelnog), neki čvorovi moraju biti odložen – skladišten na neki način da bi bio posećen posle. Ovo se često radi preko steka (LIFO) ili reda (FIFO). Kako je stablo samoreferencijalna (rekurzivno definisano) struktura podataka, obilazak se može objasniti kao rekurzija, ili korekurzija, u tom slučaju odloženi čvorovi se skladište „prećutno“, a u slučaju rekurzije u stek poziva.

Ime dato određenom stilu obilaska dolazi od reda kojim se čvorovi posećuju. Najjednostavnije, da li jedan ide dole prvi ili preko prvo. Obilazak u dubinu se dalje kvalifikuje po poziciji korenskog elementa sa obzirom na leve i desne čvorove. Zamislite da su levi i desni čvorovi konstanta u prostoru, onda korenski čvor može biti postavljen sa leve strane levog čvora, između levog i desnog čvora, ili sa desne strane desnog čvora. Ne postoji ekvivalent varijacija u obilasku u širinu – kada se gleda ređanje dece, obilazak u širinu je nedvosmislen.

Za svrhe ilustracije, smatra se da levi čvorovi uvek imaju prioritet u odnosu na desne čvorove. Ređanje može biti i suprotno pod uslovom da se isto ređanje primenjuje za sve metode obilaska.

Obilazak u dubinu je lako primenljiv preko steka, uključujući i rekuzivno (preko kol steka), dok je obilazak u dubinu lako primenljiv preko reda, uključujući i korekurzivno.

Pored ovih osnovnih obilasaza, postoji mnogo kompleksnijih ili hibridnih šema, kao to su limitirane pretrage u dubinu i iterativne produbljujuće pretrage u dubinu.

Pretraga u dubinu

Postoje tri vrste obilazaka u dubinu: pre-order, in-order i post-order. Za binarno stablo, oni su definisani kao rekurzivne operacije na svakom čvoru, počevši sa korenom čvora slede:

Preorder:

1. „Poseta“ korenu
2. Obilazak levog podstabla
3. Oblazak desnog podstabla

Inorder (simetrično):

1. Obilazak levog podstabla
2. „Poseta“ korenu
3. Obilazak desnog podstabla

Postorder:

1. Obilazak levog podstabla
2. Obilazak desnog podstabla
3. „Poseta“ korenu

Trag obilaska se naziva sekvencijalizacija stabla. Nijedna sekvencijalizacija prema pre-, in- ili post-order ne opisuje obilazak drveta jednistveno. Ili pre-order ili post-order upareni sa in-orderom je dovoljna da se stablo opiše unikatno, dok pre-order sa post-orderom ostavlja neke dvosmislenosti u strukturi stabla.

Generičko stablo

Da bi obišao stablo u obilasku u dubinu, izvedite sledeće operacije rekurzivno na svakom čvoru:

1. Izvesti preodrer operaciju
2. for i=1 to n-1 do
   1. Poseti dete[i], if postoji
   2. Izvesti inorder operaciju
3. Posetiti dete[n], if postoji
4. Izvesti postorder operaciju

Gde je n broj čvorova dece. U zavisnosti od datog problema, pre-order, in-order i post-order operacije mogu biti prazne, ili želite samo da posetite određen čvor, pa su ove operacije opcionalne. Takođe, u praksi više od jedne pre, in i post-order operacije mogu biti potrebne. Npr, prilikom unošenja u ternarno stablo, pre-order operacija se izvodi poređenjem elemenata. Post-order operacije mogu biti potrebne kasnije da vrate stablo u ravnotežu.

Pretraga u širinu

Stabla mogu takođe biti obilažena po nivoima, gde se, pre prelaska na niži nivo, posećuje svaki čvor.

Upotreba

Pre-order obilasci prilikom dupliranja čvorova i vrednosti mogu napraviti kompletnu kopiju binarnog stabla. Takođe se može koristiti za pravljenje prefiksnih izraza(Poljska notacija) iz stabala izraza: obilazak stabla izraza pre-orderski.

In-order obilaci se veoma često koriste za binarnu pretragu stabala, jer vraća vrednosti iz podvučenog seta po redu prema koji komparator postavlja u stablu za binarnu pretragu.

Post-order obilasci prilikom brisanja ili oslobađanja čvorova i vrednosti mogu izbrisati ili osloboditi celo binarno stablo. Takođe, mogu generiati postfiksnu reprezentaciju binarnog stabla.

Primer

Binarno stablo:

Pretraga u dubinu

• Preorder sekvenca obilaska: F, B, A, D, C, E, G, I, H (koren, levo, desno)

• Inorder sekvenca obilaska: A, B, C, D, E, F, G, H, I (levo, koren, desno)

• Postorder sekvenca obilaska: A, C, E, D, B, H, I, G, F (levo, desno, koren)

Pretraga u širinu

• Sekvenca obilaska po nivoima: F, B, G, A, D, I, C, E, H

Implementacije

Pretraga u dubinu

Preorder

preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left) 
  preorder(node.right)

iterativePreorder(node)
  parentStack = empty stack
  while not parentStack.isEmpty() or node != null
    if node != null then
      visit(node)
      parentStack.push(node.right)
      node = node.left
    else
      node = parentStack.pop()

Inorder

inorder(node)
  if node == null then return
  inorder(node.left)
  visit(node)
  inorder(node.right)

iterativeInorder(node)
  parentStack = empty stack
  while not parentStack.isEmpty() or node != null
    if node != null then
      parentStack.push(node)
      node = node.left
    else
      node = parentStack.pop()
      visit(node)
      node = node.right

Postorder

postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  visit(node)

iterativePostorder(node)
  if node == null then return
  nodeStack.push(node)
  prevNode = null
  while not nodeStack.isEmpty()
    currNode = nodeStack.peek()
    if prevNode == null or prevNode.left == currNode or prevNode.right == currNode
      if currNode.left != null
        nodeStack.push(currNode.left)
      else if currNode.right != null
        nodeStack.push(currNode.right)
    else if currNode.left == prevNode
      if currNode.right != null
        nodeStack.push(currNode.right)
    else
      visit(currNode)
      nodeStack.pop()
    prevNode = currNode

Sve implementacije iznad zahtevaju prostor za poziv steka proporcijalan visini drveta. U loše balansiranom stablu, ovo može biti bitno. Možemo ukloniti potrebnost steka održavajući pokazivače u svakom čvoru, ili deljenjem stabla na niti.(sledeći deo)

Morisov inorder obilazak koristeći niti

Binarno stablo je se deli na niti postavljanjem svakog pokazivača deteta da pokazuje na in-order prethodnik čvora i svaki desni pokazivač deteta da pokazuje na in-order sledbenika čvora. Prednosti:

1. Izbegava rekurzije, koje koriste kol stek i uzimaju memoriju i vreme
2. Čvor čuva podatke roditelja

Nedostaci

1. Stablo je kompleksnije
2. Više je sklono greškama kada oba deteta nisu prikazana i obe vrednosti čvorova pokazuju na svoje pretke.

Morisov obilazak je implementacija in-order obilaska koji koristi niti:

1. Kreira veza sa in-order sledbenikom
2. Štampa podatke koristeći ove veze
3. Vraća promene na originalno drvo

Pretraga u širinu

Takođe, ispod je naveden pseudokod za jednostavni obilazak nivoa zasnovan na redu i zahtevaće prostor proporcijalan maksimalnom broju čvorova na datoj širini. Može biti jednak ukupnom broju čvorova / 2. Efikasniji po pitanju prostora pristup za ovu vrstu obilaska može biti implementiran koristeći iterativnu produbljujuću pretragu u dubinu(iterative deepening depth-first search).

levelorder(root)
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    visit(node)
    if node.left ≠ null
      q.enqueue(node.left)
    if node.right ≠ null
      q.enqueue(node.right)

Beskonačna stabla

Iako se obilasci obično rade za stabla sa ograničenim brojem članova, mogu biti urađeni i sa beskonačnim stablima. Ovo je od posebnog značaja za funkcionalno programiranje, kako se beskonačne strukture podataka mogu često lako definisati i raditi, iako nisu ocenjene, ovo bi uzelo beskonačno mnogo vremena. Neka stabla ograničenim brojem članova su prevelika za reprezentaciju, kao što su stablo igre za šah, tako da je korisno analizirati ih kao da su beskonačna.

Osnovna potreba obilaska je posećivanje svakog čvora. Za beskonačna stabla, jednostavni algoritmi često ne uspeju ovo da urade. Npr, kada je dato binarno stablo beskonačne dubine, obilazak u dubinu će ići nadole po jednoj strani stabla, nikad ne posećivajući ostatak, i in i post-order neće nikada posetiti nijedan član, jer nije dostigao list. Obilazak u širinu, po nivoima, će obići binarno stablo beskonačne dubine bez problema, i stvarno će obići svako vezano stablo.

Sa druge strane, ako je dato stablo dubine 2, gde korenski član ima beskonačno mnogo dece, i svako od te dece ima dvoje dece, obilazak u dubinu će obići sve čvorove, kada iscrpi unuke, on će preći na sledeće. Dok kod obilazaka u širinu, nikada neće doći do unuka, zato što će pokušavati da iscrpi svu decu prvo.

Sofiticiranija analiza može se ostvariti preko beskonačnih rednih brojeva: npr, obilazak u širniu dubine 2 stabla iznad će uzeti ?· dva koraka ? za prvi nivo, a drugi ? za drugi nivo.

Jednostavne pretrage obilazaka u dubinu i širinu ne obiđu svako beskonačno stablo, i nisu tako efikasni na veoma velikim stablima. Ipak, hibridne metode obići svako beskonačno stablo, esencijalno preko diagonalnog argumenta (diagonalno – kombinacija vertikalnog i horizontalnog – odgovara kombinaciji dubine i širine).

Konkretno, uzevši granajuće beskonačno stablo beskonačne dubine, označavamo koren $(),$, decu čvora$(1),(2),\dots ,$ a unuke čvora $(1,1),(1,2),\ldots ,(2,1),(2,2),\ldots ,$ i tako dalje. Članovi su 1-1(bijekcija) sa određenim sekvencama pozitivnih brojeva, koji su brojivi i mogu biti postavljeni u red prvo po broju ulaza, a zatim i leksikografskim redom uzevši u obzir dati broj ulaza, koji daju obilazak. Eksplicitno:

0: ()
1: (1)
2: (1,1) (2)
3: (1,1,1) (1,2) (2,1) (3)
4: (1,1,1,1) (1,1,2) (1,2,1) (1,3) (2,1,1) (2,2) (3,1) (4)

itd.

Ovo može biti tumačeno kao unošenja na mapu binarnog stabla beskonačne dubine na ovo stablo i onda primenjivanje obilaska u širinu. Zameniti donje ivice povezivanjem roditeljskog člana na njegov sledeči a zatim dete sa desnim ivicama prvogd deteta sa drugim, drugog sa trećim i tako danja. Iako svakim korako može ići ili dole ili levo, koji pokazuje odnose između beskonačnog binarnog stabla i numerisanja odozgo; suma svih ulaza odgovara distanci od korena, koji odgovara 2^n-1 na dubini n-1 u beskonačnom binarnom stablu.

Literatura

• Dale, Nell. Lilly, Susan D. "Pascal Plus Data Structures". D. C. Heath and Company. Lexington, MA. 1995. Fourth Edition.
• Drozdek, Adam. "Data Structures and Algorithms in C++". Brook/Cole. Pacific Grove, CA. 2001. Second edition.
• http://www.math.northwestern.edu/~mlerma/courses/cs310-05s/notes/dm-treetran Arhivirano 2010-06-15 na Wayback Machine-u

Spoljašnje veze

• Animation Applet of Binary Tree Traversal
• The Adjacency List Model for Processing Trees with SQL Arhivirano 2013-07-15 na Wayback Machine-u
• Storing Hierarchical Data in a Database with traversal examples in PHP
• Managing Hierarchical Data in MySQL
• Working with Graphs in MySQL Arhivirano 2019-02-14 na Wayback Machine-u
• Non-recursive traversal of DOM trees in JavaScript Arhivirano 2013-05-22 na Wayback Machine-u
• Sample code for recursive and iterative tree traversal implemented in C.
• Sample code for recursive tree traversal in C#. Arhivirano 2009-09-30 na Wayback Machine-u
• See tree traversal implemented in various programming language on Rosetta Code
• Tree traversal without recursion