Graafik vs puu
Andmestruktuurides kasutatakse graafikut ja puud. Kindlasti on graafiku ja puu vahel mõningaid erinevusi. Binaarses seoses olevate tippude komplekti nimetatakse graafikuks, puuks aga andmestruktuur, millel on omavahel seotud sõlmede komplekt.
Graafik
Graaf on üksuste komplekt, mis on ühendatud servadega ja iga üksust nimetatakse sõlmeks või tipuks. Teisisõnu, graafi saab määratleda kui tippude hulka ja nende tippude vahel on binaarne seos.
Graafi rakendamisel realiseeritakse sõlmed objektide või struktuuridena. Servi saab kujutada erineval viisil. Üks võimalus on see, et iga sõlme saab seostada juhtuvate servade massiiviga. Kui teavet tuleb salvestada sõlmedesse, mitte servadesse, toimivad massiivid sõlmede osutajatena ja esindavad ka servi. Selle lähenemisviisi üks eeliseid on see, et graafikule saab lisada täiendavaid sõlmi. Olemasolevaid sõlme saab ühendada massiividesse elemente lisades. Kuid sellel on üks puudus, kuna sõlmede vahelise serva kindlakstegemiseks on vaja aega.
Teine viis seda teha on säilitada kahemõõtmeline massiiv või maatriks M, millel on Boole'i väärtused. Serva olemasolu sõlmest i j-ni määrab kirje Mij. Selle meetodi üks eeliseid on välja selgitada, kas kahe sõlme vahel on serv.
Puu
Puu on ka arvutiteaduses kasutatav andmestruktuur. See sarnaneb puu struktuuriga ja sisaldab sõlmede komplekti, mis on omavahel seotud.
Puu sõlm võib sisaldada tingimust või väärtust. See võib olla ka eraldi puu või kujutada endast eraldi andmestruktuuri. Puu andmestruktuuris on null või enam sõlme. Kui sõlmel on alamsõlme, nimetatakse seda selle lapse emasõlmeks. Sõlmel võib olla kuni üks vanem. Pikim allakäigutee sõlmest lehele on sõlme kõrgus. Sõlme sügavust tähistab tee selle juureni.
Puu ülemist sõlme nimetatakse juursõlmeks. Juursõlmel pole vanemaid, kuna see on kõige kõrgem. Sellest sõlmest algavad kõik puutoimingud. Kasutades linke või servi, pääseb juursõlmest teistesse sõlmedesse. Kõige alumise taseme sõlme nimetatakse lehesõlmedeks ja neil pole lapsi. Sõlme, millel on arv alamsõlme, nimetatakse sisemiseks sõlmeks või sisemiseks sõlmeks.
Graafiku ja puu erinevus:
• Puud võib kirjeldada kui graafi erijuhtumit, millel puuduvad enesesilmused ja ahelad.
• Puus pole silmuseid, samas kui graafikul võib olla silmuseid.
• Graafis on kolm hulka, st servad, tipud ja hulk, mis esindab nende seost, samas kui puu koosneb üksteisega ühendatud sõlmedest. Neid ühendusi nimetatakse servadeks.
• Puus on palju reegleid, mis kirjeldavad, kuidas sõlmede ühendused võivad toimuda, samas kui graafikul pole reegleid, mis määraksid sõlmedevahelise ühenduse.
