Dvojiško drevo

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Dvojiško drevo je podatkovna struktura. Definiramo ga lahko rekurzivno.

  • Prazno drevo (prazna množica) je dvojiško drevo: T = \emptyset
  • Neprazno drevo T lahko zapišemo v obliki trojice T = (koren,Levi,Desni).

Pri tem je koren podatek (element, vozlišče) izbranega tipa, Levi in Desni pa sta dvojiški drevesi. Imenujemo ju sinova. Ta pojem lahko razširimo še na potomce in prednike.

Vozlišče, ki nima prednikov se imenuje koren drevesa, vozlišče brez potomcev pa list drevesa.

Število vozlišč drevesa imenujemo teža drevesa, dolžino najdaljše poti od korena do katergakoli lista pa je globina drevesa.

Nivo ali raven vozlišča je dolžina poti do korena.

Vsebina

Pregled dvojiškega drevesa

Pregled dvojiškega drevesa je obisk vozlišč v določenem vrstnem redu:

Najpomembnejši :

Vizualizacija

Dvojiško drevo ponazorimo z diagramom, kjer povezave potekajo od zgoraj navzdol. Levo poddrevo narišemo na levi, desno pa na desni. Primer:

Risanje dvojiških dreves

Implementacija s tabelami

Dvojiško drevo lahko implementiramo s trojno tabelo, kadar programski jezik ne podpira drugih, bolj neposrednih metod za implementacijo podatkovnih struktur. V trojno tabelo vpisujemo Koren, Levi in Desni kazalec. Kazalec je v takem primeru kar indeks v tabeli.

Na primer, naslednje dvojiško drevo

lahko s trojno tabelo implementiramo takole:

Pri tem -1 v tabeli kazalcev pomeni prazen kazalec, indeks prvega elementa pa je enak 0.

V posebnih primerih se uporablja implementacija z eno samo tabelo. V tem primeru pustimo prvi element v tabeli neuporabljen in začnemo vpisovati elemente od prvega indeksa dalje. Levi sin elementa z indeksom i se nahaja na indeksu 2i, desni sin pa na indeksu 2i + 1. Zgornje drevo bi v taki implementaciji izgledalo kot

Takšna predstavitev je v primeru levo poravnanih dreves, kakršno je kopica, zelo učinkovita, v primeru izrojenega drevesa pa se veliko prostora v tabeli porabi za predstavitev praznih dreves in je raje ne uporabljamo.

Primeri uporabe

Dvojiško drevo je najbolj uporabno, če ima še dodatno strukturo. Tako je dvojiško drevo osnova za strukturi iskalno drevo in kopica.

Glej tudi

Osebna orodja