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:
- Vrijednost (v)
- Lijevo dijete (l)
- Desno dijete (d)
- Roditelj (roditelj)
- Broj elemenata u podstablu (n)
- Broj istih elemenata (brojač)
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.
Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License