Iskalno drevo

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

V podčlanku /KlavdijaGerencer najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.

Podatkovna struktura iskalno drevo je posebna vrsta dvojiškega drevesa. Iskalna drevesa so namenjena predstavitvi podatkov, po katerih želimo učinkovito iskati. Iskalno drevo ima v vozliščih shranjene podatke, označene s ključi, ki jih lahko primerjamo po velikosti. Ključ je del podatka, lahko je celo ves podatek.

Veljati mora pravilo:

  • Ključ v vsakem vozlišču je večji od vseh ključev v levem poddrevesu in manjši od vseh ključev v desnem poddrevesu.

V iskalnem drevesu lahko podatke:

  • vstavljamo
  • iščemo
  • obnovimo
  • brišemo (redkeje)

V iskalnem drevesu t lahko najdemo ključ x z naslednjim postopkom:

 če je t prazno drevo, ključa x ni v drevesu, 
 y := ključ v korenu drevesa t, 
 če je y == x, smo podatek našli, 
 če je y > x, iščemo v levem poddrevesu t 
 če je y < x, iščemo v desnem poddrevesu t

Vsa iskalna drevesa niso enako dobra. Drevo, ki je zelo globoko in "suho" je slabo, nizko in "debelo" drevo pa je dobro. Običajno poskušamo obdržati drevo uravnoteženo. Eno od rešitev ponujajo uravnotežena drevesa ali AVL drevesa.

Iskalno dvojiško drevo ponavadi zgradimo takrat, kadar potrebujemo hitro iskanje v množici urejenih elementov (v že zgrajenem dvojiškem drevesu, ki je približno uravnoteženo, je čas iskanja logaritemsko odvisen od števila elementov v drevesu).

Glej tudi

Osebna orodja