Binární vyhledávací strom

Z CHWiki

[editovat] Binárny vyhľadávací strom (BVS)

- stromová štruktúra – binárny strom (ľavý syn, pravý syn)

- !! implementácia tabuľy => vrchol stromu obsahuje informáciu o prvku tabuľky (Kľúč + prípadne ďalšie Info)

Pre každý podstrom BVS (vrátane celého BVS) platí: - klúče všetkých prvkov ľavého podstromu sú menšie ako klúč prvku v koreni - klúče všetkých prvkov pravého podstromu sú väčšie ako klúč prvku v koreni - vyvážený binárny strom – úrovne ľubovoľných dvoch listov sa líšia maximálne o 1

-Operácie s BVS

- Vlož (napr. 15,13,7,18,17,25,9,22) - prvok sa vkladá vždy ako list - pri hľadaní vrcholu, ktorému sa vkladaný prvok pridá ako syn sa začína od koreňa BVS, ak kľúč vkladaného prvku je nenší ako kľúč vrchola – pokračuje sa jeho ľavým synom, ak je väčší – pokračuje sa pravým synom - nebezpečie degenerácie BVS (ak majú vkladané kľúče rovnomerné rozdelenie – nehrozí veľká degenerácia)

- Zruš – realizácia závisí od toho, koľko potomkov má rušený prvok - ak je to list (nemá syna) – zruší sa (problémov) - ak má jedného syna – otec rušeného prvku nahradí rušený prvok - ak má dvoch synov – rušený vrchol sa nahradí buď "najpravejším" vrcholom v jeho ľavom podstrome alebo "najľavejším" vrcholom v jeho pravom podstrome

- Nájdi – začína sa od koreňa BVS, ak klúč hľadaného prvku je menší ako kľúč vrchola – pokračuje sa ľavým synom, ak je väčší – pokracuje sa pravým synom

- Prehliadka - ako pre ľubovoľný binárny strom - do hĺbky, do šírky, PREORDER (K-Ľ-P), INORDER (Ľ-K-P - podľa veľkosti kľúčov), POSTORDER (Ľ-P-K)

- Pamäťová reprezentácia BVS - ako u binárneho stromu - implicitná – poľom (koreň BVS = A[1]; A[2*I] = ľavý syn vrchola A[I]; A[2*I+1] = pravý syn vrchola A[I] - explicitná – dynamická voľná pamäť