9.  Stromy

9.5  Binárny vyhľadávací strom

Veľmi užitočným prípadom binárneho stromu je tzv. binárny vyhľadávací strom (binary search tree). Využíva sa výhodne v mnohých triediacich a vyhľadávacích algoritmoch, kde sa kladie dôraz na rýchlosť. Má špeciálnu vlastnosť:

Vrcholy stromu sú ohodnotené celými číslami. Pre každý vrchol platí, že v ľavom synovi je uložená menšia a v pravom synovi hodnota väčšia ako v danom vrchole. Je teda charakteristický tým, že všetky hodnoty v ľavom podstrome sú menšie a v pravom podstrome zase väčšie ako hodnota v koreni stromu. To isté platí pre ľubovoľný podstrom.

Na obrázku je príklad binárneho vyhľadávacieho stromu:



Napíšeme funkciu na vloženie novej hodnoty do binárneho vyhľadávacieho stromu:

typedef struct vrchol {
    int info;
    struct vrchol *ls, *ps;    
} TVrchol;


void vloz(TVrchol **koren, int x)
{
   if (*koren == NULL) {
       *koren = (TVrchol*)malloc(sizeof(TVrchol));
      (*koren)->info = x;
      (*koren)->ls = NULL;
      (*koren)->ps = NULL;
   }
   else {
      if (x < (*koren)->info) vloz(&((*koren)->ls), x);
      else vloz(&((*koren)->ps), x);
   }
}

Pozor!
Prvý parameter musí byť volaný odkazom - t.j. ide pointer na pointer na typ TVrchol. Pri vkladaní nového prvku ako syna nejakého vrcholu musíme totiž po jeho vytvorení v pamäti nastaviť v otcovi príslušný ukazovateľ! Ukazovateľ na pridaný vrchol sa vyvezie "o poschodie" vyššie.

Či sa nejaká hodnota nachádza v binárnom vyhľadávacom strome, môžeme zistiť iteračne. Prechádzame stromom od koreňa, pokračujeme v jednom z podstromov, podľa toho, či je hľadaná hodnota väčšia alebo menšia ako hodnota v koreni. Funkcia najdi vracia ukazovateľ na nájdený vrchol resp. NULL ak sa vrchol s takou hodnotou v strome nenachádza.

TVrchol *najdi(int x, TVrchol *koren)
{
  int najdeny = 0; /* false */

  while ((koren != NULL) && (!najdeny)) {
    if (koren->info == x) najdeny = 1; /* true */
    else if (x < koren->info ) koren = koren->ls;
         else koren = koren->ps;
  }
  return(koren);
}

Rušenie vrcholov môžeme považovať za inverzný problém k pridávaniu vrcholov do stromu. Je však o niečo zložitejší. Ak je vrchol listom alebo má jediného syna, riešenie je jednoduché:

Zrušenie vrcholu bez synov:
Potrebujeme poznať ukazovateľ na otca rušeného vrcholu. Nech je to smerník v a chceme zrušiť jeho ľavého syna. Stačia na to dva príkazy:

free((void*)v->ls); v->ls = NULL;

Zrušenie vrcholu s jediným synom:
Potrebujeme poznať ukazovateľ v na otca rušeného vrcholu. Ten nech je napr. jeho ľavým synom. Nech má rušený vrchol jediného napr. pravého syna. Zapamätáme si ukazovateľ na rušený vrchol (on), prepojíme otca s novým synom a zrušíme príslušný vrchol:

on = v->ls; v->ls = on->ps free((void*)on);

Situácia sa skomplikuje, ak potrebujeme odstrániť vrchol, ktorý má dvoch synov (je vo vnútri stromu) - nemôžeme predsa nahradiť jeden smerník dvoma! Preto sa v takýchto prípadoch rušený prvok nahradí buď najpravejším prvkom ľavého podstromu alebo najľavejším prvkom pravého podstromu.

Ak by sme chceli zo stromu na úvodnom obázku odstrániť napr. vrchol s hodnotou 15, nájdeme najpravejší prvok jeho ľavého podstromu - má hodnotu 12. Nahradíme hodnotu 15 novou hodnotou a najpravejší vrchol zrušíme. Ak by mal najpravejší vrchol ľavého syna, nastavíme ešte príslušný ukazovateľ vo vrchole 10 na tohto syna resp. na NULL ak žiadneho nemá (ako v tomto prípade).

TVrchol *on;  /* ukazovateľ na rušený prvok */

void nahrad(TVrchol **v)   /* pomocná funkcia */
{
  if ((*v)->ps != NULL) nahrad(&(*v)->ps);
  else {
     on->info = (*v)->info;
     on = *v;
     *v = (*v)->ls;
  }
}

void odstran(int x, TVrchol **koren)
{
  if (*koren == NULL) printf("Take cislo v strome nie je\n");
  else {
    if (x < (*koren)->info) odstran(x, &(*koren)->ls);
    else if (x > (*koren)->info) odstran(x, &(*koren)->ps);
         else {
           on = *koren;
           if (on->ps == NULL) *koren = on->ls;
           else if (on->ls == NULL)  *koren = on->ps;
                else nahrad(&on->ls);
           free((void*)on);
         }
  }

Funkcia nahrad sa volá len v treťom prípade - nájde najpravejší prvok ľavého podstromu, nahradí hodnotu rušeného vrcholu, pripraví situáciu na odstránenie najpravejšieho prvku v ľavom podstrome (zmení hodnotu ukazovateľa on).

Precvičme si

  Výškou stromu rozumieme dĺžku cesty od koreňa k najvzdialenejšiemu listu. Ak je koreň na prvej úrovni, jeho synovia na druhej atď., tak najvzdialenejší list bude na úrovni h + 1. Koľko vrcholov môže mať najviac binárny vyhľadávací strom, ak má výšku h?

  Vytvorte program, ktorý pomocou menu umožní pracovať s binárnym vyhľadávacím stromom. Využite vyššie uvedené funkcie a doplňte funkcie na výpis všetkými troma metódami. Nakreslite binárny vyhľadávací strom, ktorý vznikne pridaním desiatich prvkov do prázdneho stromu takto:

for (int i = 1; i <= 10; i++) vloz(&strom, i);

Prezradíme, že ide o tzv. degenerovaný strom. Ako vyzerá?