Stabla

Definicija stabla

Stablo je u računarstvu način predstavljanja hijerarhije. To je struktura podataka koja vuče analogije s rodoslovnim stablima. Prema definicijama teorije grafova, stablo je aciklički povezani graf u kojem svaki čvor ima nula ili više djece. Čvor je najmanja jedinica građe stabla. Na donjim slikama čvorovi su kućice i ono što piše u njima. Crte koje povezuju dva čvora zovu se veze. Djeca nekog čvora su svi čvorovi koji se nalaze ispod tog čvora a izravno su povezani s njime. Roditelj nekog čvora je čvor kojemu je dani čvor dijete. Čvor bez djece zove se list. Čvor bez roditelja nazivamo korijenom.

{F135,size=full} Slika 1. - Primjer stabla

Binarna stabla

Binarno stablo je struktura podataka koja se predstavlja kao stablo u kojem niti jedan čvor nema više od dvoje djece. Također, korijen stabla je samo jedan, tj. na vrhu smije biti samo jedan element. Slika 1 nije primjer binarnog stabla, dok Slika 2 to jest.

{F136,size=full} Slika 2. – Primjer binarnog stabla

U binarnom stablu svaki čvor ima točno jednog roditelja, s izuzećem korijena stabla, koji nema roditelja. Nadalje, svaki čvor ima naviše dvoje djece – čvorova kojima je on roditelj. Za ostale pojmove pogledajte pojmovnik.

Notacija

Čvor

U svakom čvoru ćemo pamtiti sljedeće informacije:

Ako su još neki podaci potrebni za neku od opisanih struktura, to će biti posebno naglašeno u tekstu koji opisuje tu strukturu.

Slike

Čvor ćemo predstavljati sivom bojom, osim ako u tekstu nije drugačije naznačeno. Veze predstavljamo crnim linijama, osim ako u tekstu nije drugačije naznačeno.

Složenost

Složenost svakog algoritma bit će napisana u veliko-O notaciji, osim ako u tekstu nije drugačije naznačeno. Veliko-O notacija (ili samo O notacija) jest način zapisivanja neke funkcije u kojoj zanemarujemo sve osim najjače potencije. Na primjer, funkciju bismo u O notaciji prikazali kao . Funkciju bismo, pak, prikazali kao . Primijetite da baza logaritma koji stoji u O notaciji nije bitna jer se ona lako može zamijeniti bilo kojom drugom množeći s konstantom.

© 2009. Bruno Rahle Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License