Leksion 10 Algoritmike

Pemet e Kerkimit Binar

Implementimi i PKB-ve

Definicione

• Pemë binare: Një strukturë me maksimum dy bij për çdo nyje.

• Pemë e kërkimit binar (PKB): Një pemë binare ku:

  • Çdo nënpemë e majtë ka çelësa më të vegjël se çelësi i nyjes.

  • Çdo nënpemë e djathtë ka çelësa më të mëdhenj se çelësi i nyjes.

• Nënpemë: Pema bijë e një nyjeje.

• Çelës: Një pjesë e të dhënave që e rendit, indekson, ose referohet grupi i të dhënave.

Krijimi i PKB-ve në C++

struct peme_nyje {
    int info;
    peme_nyje *majte;
    peme_nyje *djathte;
};
peme_nyje *rrenja; // var global
bool ugjet;
int celes;

Funksioni Bosh

• bool bosh(peme_nyje *p): Kthen true nëse pema është boshe, false përndryshe.

• Implementim:

if (p == NULL) {
    return true;
} else {
    return false;
}

Shtimi i Kulmeve në PKB

void insert(int vl, peme_nyje *&p) {
    if (p == NULL) {
        p = new peme_nyje;
        p->info = vl;
        p->majte = NULL;
        p->djathte = NULL;
    } else {
        if (vl <= p->info)
            insert(vl, p->majte);
        else
            insert(vl, p->djathte);
    }
}

Bredhja Pararendore (Pre-order Traversal)

void pararendore(peme_nyje *t) {
    if (t != NULL) {
        cout << t->info;
        pararendore(t->majte);
        pararendore(t->djathte);
    }
}

Bredhja Nderrendore (In-order Traversal)

void nderrendore(peme_nyje *t) {
    if (t != NULL) {
        nderrendore(t->majte);
        cout << t->info;
        nderrendore(t->djathte);
    }
}

Bredhja Pasrendore (Post-order Traversal)

void pasrendore(peme_nyje *t) {
    if (t != NULL) {
        pasrendore(t->majte);
        pasrendore(t->djathte);
        cout << t->info;
    }
}

Kërkimi në PKB

void kerko(int celes, bool &ugjet, peme_nyje *t) {
    if ((t != NULL) && (!ugjet)) {
        if (celes == t->info)
            ugjet = true;
        else if (celes < t->info)
            kerko(celes, ugjet, t->majte);
        else
            kerko(celes, ugjet, t->djathte);
    }
}

Heqja e Nyjeve në PKB

• Raste të ndryshme të heqjes së nyjeve:

  • Një bir ose asnjë bir: Thjesht kthehet biri tjetër.

  • Dy bija: Përdorimi i pasardhësit më të vogël nga nënpema e djathtë.

Funksioni Përdorimi për Heqjen e Nyjes

struct peme_nyje* fshijNyje(struct peme_nyje *t, int celes) {
    if (t == NULL) return t;
    if (celes < t->celes)
        t->majte = fshijNyje(t->majte, celes);
    else if (celes > t->celes)
        t->djathte = fshijNyje(t->djathte, celes);
    else {
        // Heqja e nyjes
    }
    return t;
}

Rrotullimet në PKB

• Rrotullimet majtas dhe djathtas përdoren për të ruajtur balancën e pemës në PKB.

Rrotullimi Majtas

Left-Rotate(T, x) {
    // Algoritmi për rrotullimin majtas
}

Rrotullimi Djathtas

Right-Rotate(T, x) {
    // Algoritmi për rrotullimin djathtas
}

Shtimi në PKB

Shtimi nga Rrenja

• Rregulli: Në zbritje majtas ose djathtas, kryhen rrotullime për të rikthyer përmbajtjen e pemës.

Shtimi si Një Nyje Pranë Rrenjës

• Ky metodë përpiqet të zvogëlojë lëvizjen e nyjeve përmes rrotullimeve pas shtimit.

Konkluzion

• Pema e kërkimit binar ofron efikasitet në kërkime dhe organizimin e të dhënave në mënyrë hierarkike, duke ndihmuar në ruajtjen e performancës gjatë operacioneve të ndryshme si shtimi, heqja dhe kërkimi.