Čvor (informatika)

U teoriji grafova, ova slika prikazuje pojednostavljenu mrežu gde svaki broj predstavlja različit čvor.

Čvor je osnovna jedinica koja se koristi u računarstvu. Čvorovi su uređaji ili čuvari podataka na nekoj većoj mreži. Uređaji kao što su personalni računari, mobilni telefoni ili štampači su čvorovi. Prilikom definisanja čvorova na internetu, čvor je sve ono što ima IP adresu. Čvorovi su individualni delovi veće strukture podataka, kao što su povezane liste ili stabla, koja su strukture podataka koje imaju „razgranatu” strukturu. Čvorovi sadrže podatke i takođe mogu biti povezani sa drugim čvorovima. Veze između čvorova često se implementiraju pomoću pokazivača.

Čvorovi i stabla

Čvorovi su često raspoređeni u drvoidne strukture. Te strukture su binarna stabla.^[1] Čvor predstavlja informaciju sadržanu u jedinstvenoj strukturi. Ovi čvorovi mogu da sadrže vrednost ili stanje, ili da eventualno predstavljaju nezavisnu strukturu podataka. Čvorovi su predstavljeni preko jedinstvenog čvora, svog roditelja. Najviša tačka drvoidne strukture naziva se koren^[2], koji nema roditelja, ali je roditelj ili predak ostalim čvorovima koji su u stablu ispod njega. Visina čvora je određena najdužim putem od korena do najdaljeg lista, a visina stabla je jednaka visini korena. Dubina čvora je određena razdaljinom između tog čvora i korena. Za koren se kaže da ima dubinu jednaku nuli.^[3] Podaci se mogu otkriti pomoću ovakvih mrežnih puteva. IP adresa koristi ovaj sistem čvorova kako bi definisala svoj položaj na mreži.

Definicije

Dete: Dete je čvor koji je nastavak nekog drugog čvora. Na primer, računar sa pristupom internetu mogao bi se posmatrati kao dete čvora koji predstavlja internet. Inverzna veza naziva se roditeljski čvor. Ako je čvor C dete čvora A, onda je čvor A roditelj čvora C.
Stepen: Stepen čvora je broj dece čvora.
Dubina: Dubina čvora A je dužina puta od čvora A do korena. Za koren kažemo da ima dubinu 0.
Grana: Veza između čvorova.
Šuma: Skup stabala.
Unutrašnji čvor: Čvor koji ima najmanje jedno dete.
List: Čvor koji nema dece.
Koren: Čvor koji se izdvaja od ostalih čvorova. Obično je prikazan kao najviši čvor stabla.
Rođaci: Čvorovi koji imaju istog roditelja.

Jezici za obeležavanje

Još jedna česta primena čvorova u stablima je u veb razvoju. U programiranju, XML se koristi za razmenu informacija između računarskih programera i računara podjednako. Iz ovog razloga XML se koristi da kreira zajedničke mrežne protokole koji se koriste za produktivni softver, i služi kao baza za razvoj jezika za obeležavanje (markup jezika) modernog veba, kao što je XHTML. Iako slični u pristupu programera, HTML i CSS su jezici koji se koriste za razvoj teksta i dizajna veb-sajtova. Dok XML, HTML i XHTML obezbeđuju jezik i izražajnost, DOM predstavlja prevodioca.^[4]

Tip čvora

Različiti tipovi čvorova su u stablu prikazani specifičnim interfejsima. Drugim rečima, tip čvora definisan je komunikacijom tog čvora sa ostalim čvorovima. Svaki čvor ima svoje osobine koje određuju njegov tip, na primer rođak ili list. Ako je osobina čvora konstantna osobina, ta osobina određuje njegov tip. Tako da, ako je osobina čvora konstanta ELEMENT_NODE, znamo da je taj objekat čvor Element. Ovaj objekat koristi Element interfejs da definiše sve metode i osobine tog čvora.

Različiti W3C World Wide Web Consortium tipovi čvorova i njihovi opisi:

Document predstavlja ceo dokument (koren i DOM-stablo)
DocumentFragment predstavlja objekat dokumenta, koji sadrži deo dokumenta
DocumentType omogućava povezivanje sa entitetima definisanim u dokumentu
ProcessingInstruction predstavlja instrukciju koja se obrađuje
EntityReference predstavlja referencu na entitet
Element predstavlja element
Attr predstavlja atribut
Text predstavlja tekstualni sadržaj elementa ili objekta
CDATASection predstavlja CDATA odeljak u dokumentu (tekst koji neće biti parsiran)
Comment predstavlja komentar
Entity predstavlja entitet
Notation predstavlja notaciju deklarisanu u DTD

Tip čvora	Konstanta
1	ELEMENT_NODE
2	ATTRIBUTE_NODE
3	TEXT_NODE
4	CDATA_SECTION_NODE
5	ENTITY_REFERENCE_NODE
6	ENTITY_NODE
7	PROCESSING_INSTRUCTION_NODE
8	COMMENT_NODE
9	DOCUMENT_NODE
10	DOCUMENT_TYPE_NODE
11	DOCUMENT_FRAGMENT_NODE
12	NOTATION_NODE

Čvor objekat

Čvor objekat predstavljen je u stablu jednim čvorom. Može biti čvor element, čvor atribut, čvor tekst, ili bilo koji tip čvora koji je opisan u odeljku „Tip čvora”. Svi objekti mogu da naslede osobine i metode za razrešavanje sa roditeljem ili detetom, ali nemaju svi objekti roditelja ili dete. Na primer, tekst čvorovi ne mogu imati decu, stoga dodavanje njihovih potomaka rezultira DOM greškom.

Objekti u DOM stablu mogu biti adresirani i manipulisani koristeći metode nad tim objektima. Javni interfejs DOM-a je specifikovan u njegovom programskom interfejsu (API). Istorija DOM-a (Document Object Model) je isprepletana sa istorijom „ratova pretraživača” kasnih 1990-ih godina, između Netscape Navigator-a i Microsoft Internet Explorer-a, kao i sa JavaScript-om i JScript-om, prvim „skript“ jezicima koji su bili naširoko implementirani u veb pretraživačima.

Reference

^ „Binarna stabla, strukture podataka i algoritmi”. allisons.org.
^ „Stablo (struktura podataka)”. National Institute of Standards and Technology. Спољашња веза у |publisher= (помоћ)
^ Миодраг Живковић, Алгоритми, Математички факултет, Београд
^ „Uvod u XML DOM”. W3Schools. Архивирано из оригинала 11. 06. 2014. г. Приступљено 19. 04. 2015. Спољашња веза у |publisher= (помоћ)

Spoljašnje veze

Stabla kao sredstva kompleksne analize podataka Архивирано на сајту Wayback Machine (19. јул 2018)
Opis drvoidnih struktura podataka
World Wide Web Consortium (W3C)

[1] „Binarna stabla, strukture podataka i algoritmi”. allisons.org.

[2] „Stablo (struktura podataka)”. National Institute of Standards and Technology. Спољашња веза у |publisher= (помоћ)

[3] Миодраг Живковић, Алгоритми, Математички факултет, Београд

[4] „Uvod u XML DOM”. W3Schools. Архивирано из оригинала 11. 06. 2014. г. Приступљено 19. 04. 2015. Спољашња веза у |publisher= (помоћ)

[1]