Kasutaja:Enigola/liivakast
Graafiteoorias nimetatakse puuks sidusat ja tsükliteta graafi. Olenevalt käsitlusest, võidakse puuks lugeda ainult suunamata graafe, mis vastavad puu tingimusele. Paljud andmestruktuurid informaatikas põhivad puul, aga üldiselt on nende puhul üks tipp valitud juureks, mille tulemusena saadakse juurega puu.
Definitsioonid[muuda | muuda lähteteksti]
Puu[muuda | muuda lähteteksti]
Puuks nimetatakse suunatud graafi G, mis rahuldab järgmisi võrdväärseid tingimusi:
- G on sidus ja tsükliteta.
- G on tsükliteta ja ükskõik millise serva lisamisel tekib tsükkel.
- G on sidus, kuid ükskõik millise serva eemaldamisel muutub mittesidusaks.
- G on sidus ja 3-tipuline täisgraaf ei ole G alamgraaf.
- G iga kahte tippu ühendab täpselt üks tee.
Kui graafil G on lõplik arv n serva, siis järgmised väited on samuti võrdväärsed ülaltoodutega:
- G on sidus ja tal on n - 1 serva.
- G on tsükliteta ja tal on n - 1 serva.
Kui vastavalt käsitlusele võivad suunatud graafid ka puud olla, siis on nad seda juhul, kui nende alusgraaf on puu. Samuti võidakse olenevalt käsitlusest puuks lugeda ainult juurega puid. Graafi millel pole ühtegi tippu, ei loeta üldjuhul puuks, nagu ei loetaga teda ka graafiks.
Mets[muuda | muuda lähteteksti]
Metsaks nimetatakse graafi, mille kõik sidusad komponendid on puud. Võrdväärselt saab öelda, et mets on tsükliteta graaf. Ka üksik puu ja tühigraaf (ilma servadeta graaf) on metsad. Kuna puude puhul kehtib tingimus V - E = 1, kus V on graafi tippude arv ja E graafi servade arv, siis saame metsas olevate puude arvu kui lahutame metsa kõigi tippude arvus TV, meta kõigi servade arvu TE: TV - TE = puude arv metsas.
Juurega puu[muuda | muuda lähteteksti]
Juurega puu on puu, milles ühte tippu nimetatakse juureks või juurtipuks. Kui juurega puu on suunatud, suunavad üldjuhul kõik kaared (suunatud servad) kas juurest eemale või juure poole. Tipu ülemtipuks nimetatakse naabertippu, mis jääb teele tipust juureni. Igal tipul peale juure on üks ülemtipp. Tipu alamtipuks nimetatakse tippu, mille jaoks on antud tipp ülemtipp. Leht on tipp, millel pole alamtippe. Iga tipp, mis ei ole ei juur ega leht, on vahetipp.
Juurega puu tipu kõrgus on kõige pikema lehtede suunalise tee pikkus. Puu kõrgus on puu juure kõrgus. Tipu sügavus on tee pikkus sellest tipust juureni. Juure sügavus on null, lehtede kõgus on null ja ühest tipust koosneva puu kõgus ja sügavus on mõlemad null. Kui graafi ilma ühegi tiputa loetakse korrektseks puuks, siis tavaliselt loetakse selle kõrgusega ja sügavuseks -1. Tippude sügavus on oluline puude tasakaalustamisel, mida on tihti tarvis otsimispuude, näiteks AVL-puu, puhul.
Juurega puude on üheks olulisemaks andmestruktuuriks informaatikas. Praktikas on kasutuses tihti järjestatud puud. Järjestatud puu on juurega puu, milles iga tipu alamtippudele on määratud kindel järjestus. [1]
Kahendpuu[muuda | muuda lähteteksti]
Kahendpuu on juurega puu, mille igal tipul on maksimaalselt kaks alamtippu, mida nimetatakse vasakuks ja paremaks alamtipuks või alluvaks. Rekursiivse definitsiooni kohaselt on kahendpuu puu, mis on kas tühi või millel on täpselt kaks haru, mis on mõlemad samuti kahendpuud. Informaatikas on kahendpuud olulised andmestruktuurid, mida kasutatakse tihti otsimisalgoritmide puhul.
Omadused[muuda | muuda lähteteksti]
- Igal n tipulisel puul on n - 1 serva. [2]
- Iga puu on tasandiline graaf.
- Iga puu on kahealuseline graaf.
- Iga kolme puu tipu puhul, on nendevahelistel teedel täpselt üks ühine tipp.