Matematické Fórum

Ahojte,
implementoval som vyvazovaci algorytmus pre vyvazovanie binarneho vyhladavacieho stromu, a potreboval by som zistit, ako by sa dala zistit jeho vypoctova zlozitost.

Algoritmus je nasledovny:

boolean jeStromVyvazeny(Vrchol root){
     nastavMaximalnuVyskuPodstromov(root);
     nastavBallanceIndex(root);
     return skontrolujVyvazenost(root);
}

void vyvazStrom(Vrchol root){
    while(!jeStromVyvazeny(root)){
        vyvazStrom(root);
    }
}

V skratke popisem ako to funguje:
Strom zaneme vyvazovat zavolanim metody vyvaz strom. Ako parameter pri vyvazovani mu dame koren nasho vyvazovaneho BVS. Nasledne bezi cyklus while stale dookola, az pokial nieje strom vyvazeny.  Ak je strom nevyvazeny, zavola sa metoda vyvazStrom(root), ktora prejde rekurzivne cely strom a upravuje nevyvazenost pomocou rotacii.

Ci je strom vyvazeny zistujeme pomocou metody jeStromVyvazeny. V tejto metode sa najkor pomocou metody nastavMaximalnuVyskuPodstromov(root) nastavy maximalna vyska podstromu kazdeho vrcholu stromu. Toto sa udeje tak, že prejdeme rekurzivne cely strom a každemu vrcholu nastavime atribut vyskaPostromu.

Ked sme pourcovali maximalne vysky podstromov tak teraz urcime ballance index vsetkych vrcholov. Ballance index nastavime pomocou metody nastavBallanceIndex(root) a to tak, ze opat prejdeme rekurzivne cely strom a priradime kazdemu vrcholu atribut ballanceIndex.

AKo posledna sa vykona metoda skontrolujVyvazenost(root), ktora prejde opat rekurzivne cely strom a vrati true, ak absolutna hodnota kazdeho z vrcholov stromu je mensia ako 2.

Takze zhrnutie, pri kazdom zavolani metody jeStromVyvazeny(Vrchol root) sa prejde BVS rekurzivne tri krat. Vypoctova zlozitost kazdeho prechodu by mala byt O(n), kde n je pocet vrcholov. Nasledne ak je strom nevyvazeny, tak sa vykona metoda v cykle while vyvazStrom(root), ktora tiez rekurzivne prejde vsetky vrcholy a tej by mala byt tiez vypoctova zlozitost O(n).

Teda mojou otazkou je, ako urcit vyslednu vypoctovu zlozitost celeho agoritmu???

Za kazdu pomoc velmi pekne dakujem :)