AA drevo - Vaje za utrjevanje

Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

AA drevo - Vaje za utrjevanje

Avtor: Igor Efremov

AA drevo KVIZ

Katera izmed naslednjih trditev ne drži?

AA drevo je iskalno dvojiško drevo

Stopnja lista v AA drevesu je vedno enaka 1

Stopnja levega otroka je manjša ali enaka stopnji njegovega očeta

Pravilno

Naprej

Napačno

Poskusi znova

AA drevo KVIZ

Kdaj je potrebna leva rotacija?

Kadar pri dodajanju ali brisanju vozlišč nastane desna horizontalna povezava

Kadar pri dodajanju ali brisanju vozlišč nastane leva horizontalna povezava

Kadar pri dodajanju ali brisanju vozlišč nastane dvojna desna horizontalna povezava

Pravilno

Naprej

Napačno

poskusi znova

AA drevo KVIZ

Pri brisanju vozlišča iz AA drevesa velja...

na mesto zbrisanega vozlišča postavimo poljubno vozlišče

na mesto zbrisanega vozlišča postavimo vozlišče, ki je v levem poddrevesu zbrisanega vozlišča najbolj levo

na mesto zbrisanega vozlišča postavimo vozlišče, ki ima prvo večjo vrednost kot vozlišče, ki smo ga zbrisali

na mesto zbrisanega vozlišča postavimo vozlišče, ki je v desnem poddrevesu zbrisanega vozlišča najbolj levo

Pravilno

Naprej

Napačno

Poskusi znova

AA drevo NALOGE

Naloga 1

Iz danega AA drevesa izbriši vozlišče z indeksom 68.

Rešitev je prikazana v obliki filmčka

AA drevo NALOGE

Naloga 2

Sestavi AA drevo iz naslednjih vozlišč 4,12,23,11,8,33,61,21,42,6

Vozlišča vstavljamo po vrsti. Najprej vozlišče 4(Slika 1), nato vozlišče 12 (Slika 2). Vstavimo še vozlišče 23 (Slika 3). Opazimo, da imamo dvojno desno horizontalno povezavo, zato izvedemo levo rotacijo. Vozlišču 12 povečamo stopnjo za 1. Dobimo drevo kot na sliki 4.

Slika 1

Slika 2

Slika 3

Slika 4

AA drevo NALOGE

Dodamo vozlišče 11. Drevo ustreza vsem 5 lastnostim AA dreves (slika 5). Dodamo vozlišče 8. Imamo levo horizontalno povezavo (slika 6), zato izvedemo desno rotacijo (slika 7).

Slika 5

Slika 6

Slika 7

AA drevo NALOGE

Zdaj imamo dvojno desno horizontalno povezavo (slika 7), zato izvedemo levo rotacijo (slika 8). Vozlišču 8 povečamo stopnjo za 1. Spet imamo levo horitontalno povezavo (na sliki 8 med vozliščema 12 in 8), zato izvedemo desno rotacijo (slika 9). Preverimo, če drevo ustreza lastnostim AA dreves. Ustreza, dodamo novo vozlišče 33 (slika 10).

Slika 8

Slika 9

Slika 10

AA drevo NALOGE

Dodamo vozlišče 61. Imamo dvojno desno horizontalno povezavo (slika 11), zato izvedemo levo rotacijo (slika 12). Ponovno imamo dvojno desno horizontalno povezavo, spet izvedelo levo rotacijo (slika 13).

Slika 11

Slika 12

Slika 13

AA drevo NALOGE

Dodamo vozlišče 21. Imamo levo horizontalno povezavo (slika 14), zato izvedemo desno rotacijo (slika 15).

Slika 14

Slika 15

AA drevo NALOGE

Dodamo vozlišče 42. Imamo levo horizontalno povezavo (slika 16), zato izvedemo desno rotacijo (slika 17). Vstavimo še zadnje vozlišče 6 (slika 18). Preverimo, če naše drevo ustreza vsem lastnostim AA dreves. Ustreza, to je naše končno drevo!!!