Optimalno iskalno dvojiško drevo

Optimalno iskalno dvojiško drevo je drevesna podatkovna struktura, za katero veljajo naslednje lastnosti:

• OID drevo je iskalno drevo:
  Vozlišča so v drevesu urejena tako, da so v levem poddrevesu vedno manjši elementi od korena, v desnem poddrevesu pa večji od korena. Tudi desno in levo poddrevo sta iskalni drevesi. Tako je iskanje elementov v drevesu veliko lažje, saj vemo, v kateri smeri moramo iskati.
  

  Iskalno drevo

• OID drevo je optimalno drevo:
  Optimalno drevo imamo, ko iščemo vedno iste elemente in želimo čimkrajši dostopni čas.
  - Optimalnost pomeni, da je, gledano statistično, kumulativni čas, porabljen za dostop do podatkov z različno verjetnostjo pojavljanja, najmanjši.
  Torej, to je tisto ID, med vsemi ID za v naprej znan nabor podatkov, kjer je iskalni čas () po formuli ( = + ( + )) minimalen.
  Kjer so:
• ... čas iskanja v levem poddrevesu (levo od ključa )
• ... čas iskanja v desnem poddrevesu (desno od ključa )
• ... teža (cena) iskanja ključa

• = + +
  Za lažje razumevanje:
  Če imamo samo 1 ključ v drevesu, ima le ta frekvenco iskanja tega ključa ter frakvenci iskanja besede pred ter za tem ključem (po abecednem vrstnem redu). Označimo frekvenco iskanja tega elementa s , frekvenco iskanja pred in za tem ključem pa s ter . V tem primeru je teža = + + . Čas iskanja pa = + ( + ), kar je v našem primeru enako = + + .
  
  Torej optimalno drevo uporabimo, če iščemo elemente iz znane množice in vemo kako pogosto bomo nek element iz te množice ali zunaj te množice iskali ter želimo čimkrajši iskalni čas.
  

  Optimalno drevo.

  
  

• dinamično programiranje:
  Pri dinamičnem programiranju problem razbijemo na podprobleme, poiščemo optimalne rešitve podproblemov. Nato pa delne rešitve združimo v celoto, pri čemer iz optimalnih delnih rešitev dobimo optimalno končno rešitev problema.
  Torej pri dinamičnem programiranju drevo razbijemo na poddrevesa. Poiščemo optimalne rešitve poddreves, nato pa postopoma gradimo optimalna poddrevesa iz manjših poddreves, dokler ne sestavimo prvotnega drevesa.
  

Pri OID drevesih si pri uvrščanju elementov v drevo pomagamo s pogostostjo iskanja posameznega elementa.
Bolj pogosto kot je element iskan, višje v drevo ga želimo uvrstiti.

Optimalno drevo.

Oglejmo si primer iskalnega ter primer optimalnega drevesa.

Iskalno drevo.

Optimalno drevo.

Če združimo iskalno drevo z optimalnim drevesom, dobimo optimalno iskalno dvojiško drevo.

OID drevo.

1. Primer:

Oglejmo si najprej še en primer dvojiškega drevesa, ki je OID drevo.

Primer OID drevesa.

Zgornje drevo je OID , ker ustreza definiciji iskalnega drevesa in definiciji optimalnosti (iskalni čas je minimiziran).

Sedaj pa še dva primera dreves, ki nista OID drevesi:

2. Primer:

Tole drevo ni OID drevo.

Poglejmo si, zakaj zgornje drevo ni OID drevo. Opazimo, da drevo ne ustreza definiciji iskalnega drevesa, saj je levi sin (vozlišče 'goto') večji od svojega očeta (vozlišče 'do'), moral bi pa biti manjši od korena.

3. Primer:

To drevo ni OID drevo.

Drugi primer pa je drevo, ki sicer ustreza definiciji iskalnega drevesa, ne ustreza pa definiciji optimalnosti in posledično zaradi tega ni OID drevo. Vozlišče z vrednostjo 'goto' ima frekvenco iskanosi 5, njegov levi sin ima večjo frekvenco iskanosti 25. Razlike med frekvencami iskanosti elementov pred 'do', med 'do in 'goto' ter za 'goto', pa so tako majhne, da ne vplivajo na optimalnost med tema dvema elementoma, posledično iskalni čas ni minimiziran.

Opis:

• ključi < < ... <
• verjetnost iskanja ključa je
• verjetnost iskanja elementa med in je (iskanje elementa, ki ga v slovarju ni)
• verjetnost iskanja elementa manjšega od je (iskanje elementa manjšega od najmanjšega ključa v slovarju)
• verjetnost iskanja elementa večjega od je (iskanje elementa večjega od največjega ključa v slovarju)
• vsebuje ključe od do
• celo drevo je
• verjetnost (teža) poddrevesa je
• h je globina ključa v drevesu, h’ je globina praznega poddrevesa
• Iskalni čas

V algoritmu bomo računali težo ter povprečni iskalni čas poddrevesa.

Težo implementiramo kot verjetnost, da pri iskanju ključa pridemo do nekega poddrevesa.

Teža

S pomočjo dinamičnega programiranja težo dobimo tako, da teži poddrevesa prištejemo verjetnost iskanja elementa ter verjetnost iskanja elementa, ki ga ni v drevesu .

= + +

Ker je iskalni čas elementa sorazmeren globini vozlišča iskanega elementa in ker moramo upoštevati tudi iskalni čas elemanta, ki ga ni v drevesu, pridemo do naslednje formule://

Iskalni čas

Čas iskanja lahko izračunamo rekurzivno, tako da času iskanja obeh poddreves prištejemo verjetnost iskanja v poddrevesu:
t() = + t() + + t() +
in ker velja
= + +
lahko zapišemo
t() = t() + + t()

Optimalno iskalno drevo ima naslednjo očitno lastnost: vsako poddrevo v optimalnem iskalnem drevesu je tudi optimalno zato z uporabo dinamičnega programiranja pridemo do :
= + ( + )

Primer: ( je teža, pa čas)

• =atvo; =balon; =cesta; =drevo;
• =5; =8;=4; =2;

• =3; =3; =1; =2; =1
  
  1. Najprej pogledamo drevesa globine 1, torej frekvence besed, ki jih v drevesu ne bo:
  : = = = 3
  : = = = 3
  : = = = 1
  : = = = 2
  : = = = 1
  
  2. Nato drevesa brez vozlišč združimo v drevesa s po enim vozliščem:
  

  Primer izračuna w in p za T(0,1)

  = + + = 3+5+3=11
  = + + = 11+3+3=17
  
  = + + = 3+8+1=12
  = + + = 12+3+1=16
  
  = + + = 1+4+2=7
  = + + = 7+1+2=10
  
  = + + = 2+2+1=5
  = + + = 5+2+1=8
  
  

3. Dobljena poddrevesa moramo združiti v večja drevesa, postopek ponavjlamo dokler ne pridemo do optimalnega drevesa:

Dolžini iskalnih poti se praviloma razlikujeta. Izračunamo obe in drevo, ki ima manjšo, je optimalno. Poglejmo za T(0,2)

= + + = 11+8+1=20
= + min[( + ),( + )] = 20 + min(3+16, 17+1)=38
Optimalni koren je
= + + = 12+4+2=18
= + min[( + ),( + )] = 18 + min(3+10, 16+2)=31
Optimalni koren je
= + + = 7+2+1=10
= + min[( + ),( + )] = 10 + min(1+8, 10+1)=19
Optimalni koren je

Primer izračuna T(0,3)

= + + = 20+4+2=26
= + min[( + ),( + ),( + )] = 26 + min(3+31,17+10, 38+2)=53
Optimalni koren je
= + + = 18+2+1=21
= + min[( + ),( + ),( + )] = 21 + min(3+19,16+8, 31+1)=43
Optimalni koren je

= + + = 26+2+1=29
= + min[( + ),( + ),( + ),( + )] = 29 + min(3+43,17+19, 38+8, 53+1)=65

Sedaj, ko smo se naučili vso teorijo, si lahko pogledamo primer gradnje drevesa na krajšem filmčku.

Poglej filmček

Preskoči primer in nadaljuj s teorijo

Ali drevo na sliki predstavlja OID drevo?

Koliko je teža OID drevesa s slike?

Odgovor:

Preveri

Koliko je skupni čas iskanja, če uporabimo ID drevo s slike?

Preveri

• FERI - Podatkovne strukture
• Janez Kobe - Optimalno dvojiško iskalno drevo
• Dynamic Programming
• OPTIMAL BINARY SEARCH TREES
• Optimalno iskalno drevo/Implementacija(Mathematica)