DIMA - Teorie grafů



Prohledávání binárních stromů

Teorie ⇫

Binární strom, levý/pravý syn

Kořenový strom (T,r) nazýváme binární strom, jestliže každý vrchol stromu (T,r) má nejvýše dva přímé následníky, které nazýváme levý a pravý syn.

Vrcholově ohodnocený binární strom:

Binární strom, jehož každý vrchol je ohodnocen reálným číslem, nazýváme vrcholově ohodnocený binární strom.

Skutečnost, že v binárním stromě má každý vrchol nejvýše dva následníky, je využita pro zavedení speciálních algoritmů, tzv. metod PREORDER, INORDER a POSTORDER (viz též prefix, infix, postfix). Jedná se o prohledávání binárních stromů do hloubky, ve kterých zohledníme zpracování každého vrcholu v rozdílných „okamžicích“. Zřejmé to bude z následujících rekurzívních zápisů příslušných procedur.

Nechť je dán binární strom (T,r) s kořenem r. Pro každý vrchol v stromu T definujme procedury:

  • procedure PREORDER (T,v)
    • zpracování vrcholu v
    • jestliže existuje dosud nezpracovaný levý syn vL vrcholu v, pak PREORDER (T,vL)
    • jestliže existuje dosud nezpracovaný pravý syn vP vrcholu v, pak PREORDER (T,vP)
    • návrat k přímému předchůdci (otci) vrcholu v
  • procedure INORDER (T,v)
    • jestliže existuje dosud nezpracovaný levý syn vL vrcholu v, pak INORDER (T,vL)
    • zpracování vrcholu v
    • jestliže existuje dosud nezpracovaný pravý syn vP vrcholu v, pak INORDER (T,vP)
    • návrat k přímému předchůdci (otci) vrcholu v
  • procedure POSTORDER (T,v)
    • jestliže existuje dosud nezpracovaný levý syn vL vrcholu v, pak POSTORDER (T,vL)
    • jestliže existuje dosud nezpracovaný pravý syn vP vrcholu v, pak POSTORDER (T,vP)
    • zpracování vrcholu v
    • návrat k přímému předchůdci (otci) vrcholu v

Někdy se můžeme setkat i s českým překladem metod. Potom se metoda PREORDER nazývá přímé vyhledávání, metoda INORDER vnitřní vyhledávání a metoda POSTORDER zpětné vyhledávání.

Vlastní postup vyhledávání je možné shrnout i takto:

  • metoda PREORDER - nejprve je zpracován kořen, pak jeho podstromy
  • metyoda INORDER - nejprve je zpracován levý podstrom, potom kořen a nakonec pravý podstrom
  • metoda POSTORDER - nejprve se zpracují podstromy a kořen až nakonec

Binární strom můžeme využít i pro zpracování matematických operací.

Mějme binární kořenový strom, ve kterém koncové vrcholy jsou čísla (resp. číselné proměnné – identifikátory obsahující číselné hodnoty), ostatní vrcholy kódy aritmetických operací (+, -, *, /). Každý vrchol stromu obsahuje záznam skládající se:

  • z kódu aritmetické operace (+, -, *, /)
  • z číselné hodnoty (lze řešit i odkazem, identifikátorem)

Příklad

Pomocí vhodné procedury řešte výraz: (((2 + 4) - 7) * 9) / ((6 * 2) / 4)

Výraz nejprve překreslíme jako binární strom:

binární strom

Na řešení můžeme použít metodu PREORDER nebo POSTORDER.

  • metodou PREORDER dostaneme pořadí vrcholů: / * - + 2 4 7 9 / * 6 2 4. Nadjeme vždy dvojici číslic se znaménkem před a vykonáme početní operaci:
    • / * - + 2 4 7 9 / * 6 2 4
    • / * - 6 7 9 / 12 4
    • / * -1 9 3
    • / -9 3
    • -3

    Výsledek je -3.

  • metodou POSTORDER dostaneme pořadí vrcholů: 2 4 + 7 - 9 * 6 2 * 4 / /. Tentokrát najdeme vždy dvojici čísel se znaménkem za a opět vykonáme příslušnou početní operaci:
    • 2 4 + 7 - 9 * 6 2 * 4 / /
    • 6 7 - 9 * 12 4 / /
    • -1 9 * 3 /
    • -9 3 /
    • -3

    Jak vidíme, výsledek je opět -3.

Ukázka přidávání vrcholů do binárního vyhledávacího stromu je zde.

Řešený příklad ⇫

Proveďte metody PREORDER, INORDER a POSTORDER.

binární strom

Metoda PREORDER

preorder

PREORDER: a,b,d,e,i,c,f,g,h

Metoda INORDER

inorder

INORDER: d,b,i,e,a,c,g,f,h

Metoda POSTORDER

postorder

POSTORDER: d,i,e,b,g,h,f,c,a

Úlohy k řešení ⇫

1. Jestliže zpracováním vrcholu míníme výpis hodnoty v něm uložené, pak pro binární strom na obrázku níže vypište pořadí hodnot vzhledem k použitým metodám:

strom

Výsledek

PREORDER: 22,5,2,11,7,14,30,25,33,38,60.

INORDER: 2,5,7,11,14,22,25,30,33,38,60.

POSTORDER: 2,7,14,11,5,25,60,38,33,30,22.

2. Aritmetický výraz je reprezentován výrazovým stromem. Tento výraz zapište metodou PREORDER a POSTORDER.

binárnéí strom

Výsledek

PREORDER: - / * A B 9 + D E

POSTORDER: A B * 9 / D E + -

3. Vypočítejte výraz zadaný v binárním stromu.

binární strom

Výsledek

8

Zdroje textů

  1. DIMA - diskrétní matematika, http://oliva.uhk.cz
  2. Hliněný, Petr. Diskrétní Matematika (456-533 DIM), 2006
  3. Kovář, Petr. DISKRÉTNÍ MATEMATIKA a ÚVOD DO TEORIE GRAFŮ ( příklady k procvičení ), 2012