Iskalno drevo

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 15:42, 18 december 2005
Plantevj (Pogovor | prispevki)

← Prejšnja različica
Različica od 16:48, 18 december 2005
AndrejStivicevic (Pogovor | prispevki)

Naslednja različica →
Vrstica 1: Vrstica 1:
-ISKALNO DREVO+'''Iskalna drevesa''' so posebna vrsta dreves. Uporabljajo se za predstavitev podatkov, po katerih želimo učinkovito iskati.
- +Iskalno drevo ima [[vozlišče|vozlišča]] označena s podatki, ki jih lahko primerjamo po velikosti. Veljati mora pravilo:
-Iskalna drevesa so posebna vrsta dreves. Uporabljajo se za predstavitev podatkov, po katerih želimo učinkovito iskati. +
-Iskalno drevo ima vozlišča označena s podatki, ki jih lahko primerjamo po velikosti. Veljati mora pravilo: +
*Podatek v korenu drevesa je večji od vseh podatkov v levem poddrevesu in manjši od vseh podatkov v desnem poddrevesu. *Podatek v korenu drevesa je večji od vseh podatkov v levem poddrevesu in manjši od vseh podatkov v desnem poddrevesu.
V iskalnem drevesu t lahko najdemo podatek x z naslednjim postopkom: V iskalnem drevesu t lahko najdemo podatek x z naslednjim postopkom:
-1. če je t prazno drevo, podatka x ni v drevesu, + 
-2. y := podatek v korenu drevesa t, +# če je t prazno drevo, podatka x ni v drevesu,
-3. če je y == x, smo podatek našli, +# y := podatek v korenu drevesa t,
-4. če je y < x, iščemo v levem poddrevesu t +# če je y == x, smo podatek našli,
-5. če je y > x, iščemo v desnem poddrevesu t+# č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. Vsa iskalna drevesa niso enako dobra. Drevo, ki je zelo globoko in "suho" je slabo, nizko in "debelo" drevo pa je dobro.
 +
 +[[Kategorija:Programski jezik]]
 +[[Kategorija:Pojmovnik]]

Različica od 16:48, 18 december 2005

Iskalna drevesa so posebna vrsta dreves. Uporabljajo se za predstavitev podatkov, po katerih želimo učinkovito iskati. Iskalno drevo ima vozlišča označena s podatki, ki jih lahko primerjamo po velikosti. Veljati mora pravilo:

  • Podatek v korenu drevesa je večji od vseh podatkov v levem poddrevesu in manjši od vseh podatkov v desnem poddrevesu.

V iskalnem drevesu t lahko najdemo podatek x z naslednjim postopkom:

  1. če je t prazno drevo, podatka x ni v drevesu,
  2. y := podatek v korenu drevesa t,
  3. če je y == x, smo podatek našli,
  4. če je y < x, iščemo v levem poddrevesu t
  5. č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.

Osebna orodja