Primerjava hitrosti delovanja preskočnih seznamov in neuravnoteženih dvojiških iskalnih dreves nad naključnimi elementi

Imejmo milijon unikatnih števil od 1 do 1000000. Števila naključno premešamo in jih hkrati vstavimo v preskočni seznam in neuravnoteženo dvojiško iskalno drevo. V nalogi smo obe podatkovni strukturi sprogramirali v programskem jeziku Java, nato pa primerjali število korakov, potrebnih za iskanje vsakega elementa v obeh strukturah.

Število korakov v dvojiškem iskalnem drevesu:

Število korakov v preskočnih seznamih:

Ugotovili smo, da je povprečno število korakov v dvojiškem iskalnem drevesu večje od povprečja v preskočnih seznamih, če pri slednjih ne upoštevamo časa, potrebnega za prehod v nov nivo. Predpostavka je smiselna, saj prehod v nov nivo ne povzroči zgrešitve v predpomnilnku, kar najbolj vpliva na čas izvajanja operacije iskanja.