
sheersh vriksh

ack sheersh vriksh ack dwiaadhaari vriksh parr adharit ack detta sanrachana haye joe binaa jarh vaale gatishil pedon key liye mukhya roop seey vibhinn path-sambandhit sanchaalan key liye upayog kiya jaataa haye. yeh saral vibhajan aur vijay algorithm kii anumati detaa haye. taba seey ise ack pedh key vibhinn gunon jaise vyaas, kendra aur madhya koo gatishil roop seey banaae rakhane key liye badhaaya gayaa haye.
ack sheersh vriksh sootra _ 1 koo ack "antarnihit vriksh" sootra _ 2 key liye paribhaashit kiya gayaa haye aur adhikatam dou sheershon key ack sett sootra _ 3 koo baahari seema sheersh kahaa jaataa haye.
shabdawali.
seema node.
seema sheersh dekhein
seema sheersh.
ack judey hue upa-vriksh mein ack sheersh ack "seema sheersh" haye yadi yeh upa-vriksh key baahar ack sheersh seey ack kinare seey judaa huaa haye.
baahari seema sheersh.
sheersh vriksh sootra _ 1 mein sheershon kii ack jodee taka koo baahari seema sheersh kahaa jaa sakata haye, unhein samooh key seema sheersh key roop mein socha jaa sakata haye joe poore sheersh vriksh kaa pratinidhitva kartaa haye.
samooh.
ack "samooh" ack judaa huaa upa-vriksh haye jisamen adhikatam dou seema sheersh hotey hain.
diye gaye samooh sootra _ 5 key seema sheershon key sett koo sootra _ 6 key roop mein darshaaya jaataa haye.
pratyek samooh sootra _ 5 key saath upayogkarta kuchh metaa soochana sootra _ 8 koo jodd sakata haye aur vibhinn aantarik sanchaalan key tahat ise banaae rakhane key tareeke dey sakata haye.
path samooh.
yadi sootra _ 9 mein cumm seey cumm ack kinara haye tou sootra _ 5 koo "path samooh" kahaa jaataa haye.
bindu samooh.
patti kaa guchch dekhein
patti kaa guchch.
yadi sootra _ 9 mein koee kinara naheen haye.ee. sootra _ 5 mein kewal ack seema sheersh hotaa haye tou sootra _ 5 koo "leaf cluster" kahaa jaataa haye.
kinare kaa samooh.
ekal kinare vaale samooh koo "kinare kaa samooh" kahaa jaataa haye.
patti key kinare kaa guchhe.
mool samooh mein ack patti koo kewal ack seema sheersh key saath ack samooh dwara darshaaya jaataa haye aur ise "patti key kinare kaa samooh" kahaa jaataa haye.
path kinare kaa samooh.
dou seema nodes vaale kinare key samoohon koo "path kinare kaa samooh" kahaa jaataa haye.
aantarik node.
sootra _ 5 mein ack node koo sootra _ 16 kaa "aantarik node" kahaa jaataa haye.
samooh maarg.
sootra _ 5 key seema sheershon key beach key maarg koo sootra _ 5 kaa "samooh path" kahaa jaataa haye aur ise sootra _ 19 dwara darshaaya jaataa haye.
vilay yogya samooh.
dou samooh sootra 20 aur sootra 21 "vilay yogya" hain yadi sootra 22 ack ekal tunn sett haye (unake paas samaan roop seey ack node haye) aur sootra 23 ack samooh haye.
parichay.
"sheersh pedh" kaa upayog ack gatishil vann (pedon key samooh) koo banaae rakhane key liye kiya jaataa haye.
mool vichaar mool vriksh sootra _ 2 (i) mein nodes kii sankhya mein laghuganak oonchaai key santulit dwiaadhaari vriksh sootra _ 1 koo banaae rakhna haye.ee. sootra _ 26 samay mein); sheersh vriksh anivarya roop seey mool vriksh sootra _ 2 key punaraavarti upkhand koo samoohon mein darshaata haye.
samanya taur parr vriksh sootra _ 2 kaa kinaaron parr vajan hoe sakata haye.
mool vriksh sootra _ 2 key kinaaron key saath ack-seey-ack patrachar haye aur sheersh vriksh sootra _ 1 key patti node aur sootra _ 1 kaa pratyek aantarik node ack samooh kaa pratinidhitva kartaa haye joe samoohon key sangh key kaaran banata haye joe isake bachche hain.
sheersh vriksh detta sanrachana koo sootra _ 32 samay mein aarambh kiya jaa sakata haye.
isaliye sheersh vriksh sootra _ 1 over (sootra _ 34 sootra _ 3) ack dwiaadhaari vriksh haye joe
ack sheersh vaale pedh mein ack khaali sheersh vriksh hotaa haye, aur kewal ack kinare vaalaa pedh kewal ack node hotaa haye.
yeye pedh swatantra roop seey badhaane yogya hain joe upayogkarta koo detta sanrachana key aantarik kamkaj key vivaran mein jaane key binaa lachilepan aur utpaadaktaa kii ack vistrit vividhata kii anumati dete hain, jise "black boxes" key roop mein bhee jaanaa jaataa haye.
gatishil sanchaalan.
nimnalikhit teen upayogkarta dwara sweekarya vann adyatan hain.
aantarik sanchaalan.
vann adyatan sabhi adhikansh sootra _ 26 aantarik sanchaalan key ack anukram dwara kiye jaate hain, jiska anukram aage key sootra _ 26 samay mein ganana kii jaati haye. aisaa hoe sakata haye kii ack pedh key adyatan key dauran, ack patti kaa samooh ack path samooh aur parivartit hoe sakata haye. sheersh vriksh key liye adyatan vishesh roop seey inn aantarik sanchaalan dwara kiye jaate hain.
sootra _ 65 koo pratyek aantarik sanchaalan seey judey upayogkarta paribhaashit kaary koo coll karke adyatan kiya jaataa haye.
vibhajan koo aamtaur parr cleanformula _ 84 vidhi kaa upayog karke lagu kiya jaataa haye joe sootra _ 74 aur sootra _ 80 key adyatan key liye sootra _ 65 kaa upayog karke upayogkarta vidhi koo coll kartaa haye aur sootra _ 65 koo update kartaa haye taaki yeh gyaat hoe kii isake bachchon mein koee lambit adyatan kii aavashyakta naheen haye. sootra _ 5 koo upayogkarta paribhaashit karyon koo coll kiye binaa tyag diyaa jaataa haye. aksar binaa vibhajit kiye prashnon key liye saaf-suthra honah aavashyak hotaa haye.
yadi vibhajan swachchh subrutin kaa upayog naheen kartaa haye, aur saaf karane kii aavashyakta haye, tou iska prabhaav vilay aur vibhajan key sanyojan seey overhead key saath praapt kiya jaa sakata haye.
agale dou kaary uparokt dou key anuroop hain aur aadhar samoohon key liye upayog kiye jaate hain.
gair-sthaaniya khoj.
upayogkarta chusoformula _ 76 operation koo paribhaashit curr sakata haye joe ack root (nonleaf) cluster key liye apane child cluster mein seey ack kaa chayan kartaa haye. sheersh vriksh blackbox khoj formula _ 76 dincharya pradaan kartaa haye, joe prashnon koo chunane aur sheersh vriksh key punargathan (aantarik sanchaalan kaa upayog karke) kaa ayojan kartaa haye taaki yeh sabhi chayanit samoohon key pratichhedan mein ekmatra kinare kaa pataa lagaa sakey. kabhi-kabhi khoj ack maarg taka seemit honey chaahiye. aise uddeshyon key liye gair-sthaaniya khoj kaa ack prakaar haye.
yadi root cluster sootra _ 5 mein dou baahari seema sheersh hain, tou kinare koo kewal path sootra _ 9 parr khoja jaataa haye. yeh nimnalikhit sanshodhan karane key liye paryaapt haih yadi kewal root cluster bachchon mein seey ack path samooh haye, tou ise chayan operation koo bulaaye binaa default roop seey chunaa jaataa haye.
gair-sthaaniya khoj key udaaharan.
sootra _ 43 seey sootra _ 44 taka lambe maarg parr i-th kinare koo sootra _ 5 = expose ({v, w}) dwara kiya jaa sakata haye, jisake baad upayukt chayan key saath khoj (sootra _ 5) kii jaa sakati haye. chayan koo lagu karane key liye humm sootra _ 43 kaa pratinidhitva karane vaale vaishvik charr kaa upayog karate hain aur sootra _ 110 kaa pratinidhitva karane vaale vaishvik charr kaa chayan karate hain sootra _ 112 key saath samooh sootra _ 20 kaa chayan karein yadi sootra _ 113 kii lambai cumm seey cumm sootra _ 114 haye. sanchaalan kaa samarthan karane key liye lambai koo sootra _ 115 mein banaae rakhaa jaanaa chaahiye.
gair-ikai lambai vaale kinaaron key saath graph key liye isi tarah key kaary koo taiyar kiya jaa sakata haye. usa sthiti mein doori dou kinaaron key beach ack kinare yaa sheersh koo sambodhit curr sakati haye. humm iss tarah seey chuna sakate hain kii sheersh kii or jaane vaalaa kinara baad key mamle mein vaapas aaa jaae. ack sthiraank dwara ack path key saath sabhi kinare kii lambai koo badhaane key liye paribhaashit adyatan hoe sakata haye. aise paridrishya mein yeye adyatan kewal root cluster mein nirantar samay mein kiye jaate hain. bachchon koo vilambit adyatan vitarit karane key liye saaf-suthra honah aavashyak haye. chayan koo lagu karane seey pahale saaf koo bulaaya jaanaa chaahiye. sootra 115 mein lambai banaae rakhane key liye usa mamle mein sootra 115 mein bhee ikai lambai banaae rakhane kii aavashyakta hogi.
vertex sootra _ 43 vaale pedh key kendra koo khojane key liye ack antim bindu key roop mein kendra key saath dwi-kendra kinare yaa kinare koo dhoondhana sambhav haye. kinare koo sootra _ 5 = expose ({v}) dwara paaya jaa sakata haye jisake baad upayukt chayan key saath khoj (sootra _ 5) hoe sakata haye. chayan sootra _ 121 sootra _ 21 key saath bachchon key beach chayan kartaa haye, sootra _ 123 key saath uchch adhikatam doori key sootra _ 124 key saath bachche. sanchaalan kaa samarthan karane key liye seema sheersh seey samooh upa-vriksh mein adhikatam doori sootra _ 115 mein banaae rakhee jaani chaahiye. jisake liye samooh path kii lambai key rakharkhaav kii bhee aavashyakta hoti haye.
dilchasp parinam aur anuprayog.
mool roop seey anya tarikon dwara lagu kiye gaye kaee dilchasp anuprayogon koo sheersh vriksh key interfaces kaa upayog karke aasaani seey lagu kiya gayaa haye. inmein seey kuchh
karyanvayan.
sheersh vrikshon koo vibhinn tarikon seey lagu kiya gayaa haye, unamen seey kuchh mein "bahustariya vibhajan" (sheersh-vriksh aur gatishil graph algorithm jacob holm aur christian dee lichtenberg) kaa upayog karke karyanvayan shamil haye. takniki report), aur yahaan taka kii sleeter-turgeon aiss-tii pedon (aamtaur parr parishodhan samay seema key saath), frederickson key topology pedon (sabse kharaab mamle samay seema key saath) (alstrup aur anya. sheersh pedon key saath poori tarah seey gatishil pedon mein jaankaari banaae rakhna).
parishodhan key karyanvayan adhik saral hotey hain, aur samay kii jatilata mein chhote gunak karakon key saath.
isake vipareet sabse kharaab mamle key karyanvayan seey poochtaachh key dauran anaavashyak jaankaari adyatan koo bund karke prashnon koo tej karane kii anumati milati haye (dridhata takneekon dwara lagu). prashn kaa uttar diye jaane key baad sheersh vriksh kii mool sthiti kaa upayog kiya jaataa haye aur prashn sanskaran koo tyag diyaa jaataa haye.
bahustariya vibhajan kaa upayog karna.
ack vriksh sootra _ 2 key samoohon key kissy bhee vibhajan koo ack samooh vibhajan vriksh cptformula _ 179 dwara vriksh sootra _ 2 mein pratyek samooh koo ack kinare seey badalkar darshaaya jaa sakata haye. yadi humm vibhajan sootra _ 2 key liye ack ranneeti p kaa upayog karate hain tou cpt cptpformula _ 182 hoga yeh kewal ack kinare taka hii punaraavarti roop seey kiya jaataa haye.
humm dekhenge kii sambandhit sheersh vriksh sootra _ 1 key sabhi nodes koo iss bahustariya vibhajan key kinaaron mein vishisht roop seey mapp kiya gayaa haye. bahustariya vibhajan mein kuchh kinare hoe sakate hain joe sheersh vriksh mein kissy bhee node key anuroop naheen hain, yeye aise kinare hain joe isake neeche key star mein kewal ack bachche kaa pratinidhitva karate hain, i.ee. ack sadharan samooh. kewal way kinare joe samagr samoohon seey mell khaate hain, sheersh vriksh sootra _ 184 mein nodes seey mell khaate hain
ack vibhajan ranneeti mahatvapurna haye jaba humm vriksh sootra _ 2 koo samoohon mein vibhajit karate hain. kewal ack saavdhaanipoorvak ranneeti yeh sunishchit karati haye kii humm ack sootra _ 26 oonchaai bahustariya vibhajan (aur isaliye sheersh vriksh) mein samaapt hoe jaaen.
uparokt vibhajan ranneeti sootra _ 26 samay mein sheersh vriksh key rakharkhaav koo sunishchit karati haye.

