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

У информатици, под обиласком стабала сматра се процес посећивања сваког чвора у стаблу (структура података), тачно једном, систематски. Овакви обиласци се класификују по реду у којем су чворови посећени. Следећи алгоритми су описани за бинарно стабло, али могу се генерализовати за остала стабла, такође.

Врсте

У поређењу са линеарним структурама података као што су повезане листе и једнодимензионалним низовима, који користе канонски метод обиласка, структуре стабала могу се обићи на много различитих начина. Почевши од корена бинарног стабла, постоје три главна корака која се могу извести а ред по којем су изведени дефинише врсту обиласка. Ови кораци (без неког одређеног реда) су: извођење акције на тренутном чвору („посећивање“ чвора), обилазак на леви син чвора и обилазак на десни син чвора.

Обилазак стабла преставља повезивање свих чворова у петљу на неки начин. Зато што од једног датог чвора постоји више могућих следећих чворова (то није линеарна структура података), онда, код секвенцијалног рачунања (не паралелног), неки чворови морају бити одложен – складиштен на неки начин да би био посећен после. Ово се често ради преко стека (ЛИФО) или реда (ФИФО). Како је стабло самореференцијална (рекурзивно дефинисано) структура података, обилазак се може објаснити као рекурзија, или корекурзија, у том случају одложени чворови се складиште „прећутно“, а у случају рекурзије у стек позива.

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

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

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

Поред ових основних обиласаза, постоји много комплекснијих или хибридних шема, као то су лимитиране претраге у дубину и итеративне продубљујуће претраге у дубину.

Претрага у дубину

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

Преордер:^[1]

„Посета“ корену
Обилазак левог подстабла
Облазак десног подстабла

Инордер (симетрично):^[1]

Обилазак левог подстабла
„Посета“ корену
Обилазак десног подстабла

Постордер:^[1]

Обилазак левог подстабла
Обилазак десног подстабла
„Посета“ корену

Траг обиласка се назива секвенцијализација стабла. Ниједна секвенцијализација према пре-, ин- или пост-ордер не описује обилазак дрвета једниствено. Или пре-ордер или пост-ордер упарени са ин-ордером је довољна да се стабло опише уникатно, док пре-ордер са пост-ордером оставља неке двосмислености у структури стабла.^[2]

Генеричко стабло

Да би обишао стабло у обиласку у дубину, изведите следеће операције рекурзивно на сваком чвору:

Извести преодрер операцију
for i=1 to n-1 do
1. Посети дете[i], if постоји
2. Извести инордер операцију
Посетити дете[n], if постоји
Извести постордер операцију

Где је n број чворова деце. У зависности од датог проблема, пре-ордер, ин-ордер и пост-ордер операције могу бити празне, или желите само да посетите одређен чвор, па су ове операције опционалне. Такође, у пракси више од једне пре, ин и пост-ордер операције могу бити потребне. Нпр, приликом уношења у тернарно стабло, пре-ордер операција се изводи поређењем елемената. Пост-ордер операције могу бити потребне касније да врате стабло у равнотежу.

Претрага у ширину

Стабла могу такође бити обилажена по нивоима, где се, пре преласка на нижи ниво, посећује сваки чвор.

Употреба

Пре-ордер обиласци приликом дуплирања чворова и вредности могу направити комплетну копију бинарног стабла. Такође се може користити за прављење префиксних израза (Пољска нотација) из стабала израза: обилазак стабла израза пре-ордерски.

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

Пост-ордер обиласци приликом брисања или ослобађања чворова и вредности могу избрисати или ослободити цело бинарно стабло. Такође, могу генериати постфиксну репрезентацију бинарног стабла.

Пример

Бинарно стабло:

Претрага у дубину

Преордер секвенца обиласка: F, B, A, D, C, E, G, I, H (корен, лево, десно)
Инордер секвенца обиласка: A, B, C, D, E, F, G, H, I (лево, корен, десно)
Постордер секвенца обиласка: A, C, E, D, B, H, I, G, F (лево, десно, корен)

Претрага у ширину

Секвенца обиласка по нивоима: F, B, G, A, D, I, C, E, H

Имплементације

Претрага у дубину

Преордер

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

Све имплементације изнад захтевају простор за позив стека пропорцијалан висини дрвета. У лоше балансираном стаблу, ово може бити битно. Можемо уклонити потребност стека одржавајући показиваче у сваком чвору, или дељењем стабла на нити.(следећи део)

Морисов инордер обилазак користећи нити

Бинарно стабло је се дели на нити постављањем сваког показивача детета да показује на ин-ордер претходник чвора и сваки десни показивач детета да показује на ин-ордер следбеника чвора. Предности:

Избегава рекурзије, које користе кол стек и узимају меморију и време
Чвор чува податке родитеља

Недостаци

Стабло је комплексније
Више је склоно грешкама када оба детета нису приказана и обе вредности чворова показују на своје претке.

Морисов обилазак је имплементација ин-ордер обиласка који користи нити:

Креира веза са ин-ордер следбеником
Штампа податке користећи ове везе
Враћа промене на оригинално дрво

Претрага у ширину

Такође, испод је наведен псеудокод за једноставни обилазак нивоа заснован на реду и захтеваће простор пропорцијалан максималном броју чворова на датој ширини. Може бити једнак укупном броју чворова / 2. Ефикаснији по питању простора приступ за ову врсту обиласка може бити имплементиран користећи итеративну продубљујућу претрагу у дубину(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)

Бесконачна стабла

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

Основна потреба обиласка је посећивање сваког чвора. За бесконачна стабла, једноставни алгоритми често не успеју ово да ураде. Нпр, када је дато бинарно стабло бесконачне дубине, обилазак у дубину ће ићи надоле по једној страни стабла, никад не посећивајући остатак, и ин и пост-ордер неће никада посетити ниједан члан, јер није достигао лист. Обилазак у ширину, по нивоима, ће обићи бинарно стабло бесконачне дубине без проблема, и стварно ће обићи свако везано стабло.

Са друге стране, ако је дато стабло дубине 2, где коренски члан има бесконачно много деце, и свако од те деце има двоје деце, обилазак у дубину ће обићи све чворове, када исцрпи унуке, он ће прећи на следеће. Док код обилазака у ширину, никада неће доћи до унука, зато што ће покушавати да исцрпи сву децу прво.

Софитициранија анализа може се остварити преко бесконачних редних бројева: нпр, обилазак у ширниу дубине 2 стабла изнад ће узети ?· два корака ? за први ниво, а други ? за други ниво.

Једноставне претраге обилазака у дубину и ширину не обиђу свако бесконачно стабло, и нису тако ефикасни на веома великим стаблима. Ипак, хибридне методе обићи свако бесконачно стабло, есенцијално преко диагоналног аргумента (диагонално – комбинација вертикалног и хоризонталног – одговара комбинацији дубине и ширине).

Конкретно, узевши гранајуће бесконачно стабло бесконачне дубине, означавамо корен $(),$ , децу чвора $(1),(2),\dots ,$ а унуке чвора $(1,1),(1,2),\ldots ,(2,1),(2,2),\ldots ,$ и тако даље. Чланови су 1-1(бијекција) са одређеним секвенцама позитивних бројева, који су бројиви и могу бити постављени у ред прво по броју улаза, а затим и лексикографским редом узевши у обзир дати број улаза, који дају обилазак. Експлицитно:

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)

итд.

Ово може бити тумачено као уношења на мапу бинарног стабла бесконачне дубине на ово стабло и онда примењивање обиласка у ширину. Заменити доње ивице повезивањем родитељског члана на његов следечи а затим дете са десним ивицама првогд детета са другим, другог са трећим и тако дања. Иако сваким корако може ићи или доле или лево, који показује односе између бесконачног бинарног стабла и нумерисања одозго; сума свих улаза одговара дистанци од корена, који одговара 2^н-1 на дубини н-1 у бесконачном бинарном стаблу.

Референце

Литература

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 Архивирано на сајту Wayback Machine (15. јун 2010)

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

Animation Applet of Binary Tree Traversal
The Adjacency List Model for Processing Trees with SQL Архивирано на сајту Wayback Machine (15. јул 2013)
Storing Hierarchical Data in a Database with traversal examples in PHP
Managing Hierarchical Data in MySQL
Working with Graphs in MySQL Архивирано на сајту Wayback Machine (14. фебруар 2019)
Non-recursive traversal of DOM trees in JavaScript Архивирано на сајту Wayback Machine (22. мај 2013)
Sample code for recursive and iterative tree traversal implemented in C.
Sample code for recursive tree traversal in C#. Архивирано на сајту Wayback Machine (30. септембар 2009)
See tree traversal implemented in various programming language on Rosetta Code
Tree traversal without recursion

[holtenotes-1] а ^б ^в Lecture 8 - Tree Traversal

[2] Which combinations of pre-, post- and in-order sequentialisation are unique?

[1]

[2]