Č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[уреди]

Jednostavno binarno stablo veličine 9 i visine 3, sa korenom čija je vrednost 2. Ovo stablo je nebalansirano i nesortirano.

Č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[уреди]

Spoljašnje veze[уреди]