Bästa svaret
Skillnad mellan diagram och träddatastruktur:
Diagram
- I diagrammet kan det finnas mer än en väg, dvs att grafen kan ha enkelriktade eller dubbelriktade vägar mellan noder.
- I diagrammet finns inget sådant begrepp rot -nod.
- Diagrammet kan ha slingor, kretsar såväl som kan ha självslingor.
- I diagram finns det inga sådana föräldrabarnsförhållande.
- Grafer är mer komplexa jämfört med träd eftersom det kan ha cykler, slingor etc.
- Diagrammet korsas av DFS : Djup först sökning och i BFS : Algoritm för första sökning i bredd.
- Grafen kan vara cyklisk eller cyklisk. / li>
- Det finns huvudsakligen två typer av grafer: Riktade och ej riktade grafer.
- Grafapp licenser: Färgläggning av kartor, algoritmer, diagramfärgning, jobbplanering etc.
- I diagram, nr. av kanterna beror på diagrammet.
- Diagrammet är en nätverksmodell.
Träd
- Trädet är en speciell form av ett diagram, dvs minimalt ansluten graf och har bara en väg mellan två hörn.
- Träd är ett speciellt fall av diagram utan slingor, inga kretsar och inga självslingor.
- I trädet finns exakt en root node och alla barn har bara en förälder.
- I träd finns det ett föräldrabarnsförhållande så att flöde kan vara där med riktning topp till botten eller vice versa.
- Träd är mindre komplexa än grafer som att de inte har några cykler, inga självslingor och fortfarande är anslutna.
- Trädgenomgång är ett slags specialfall av traversal av diagrammet. Trädet passeras i Förbeställning , Beställning och Efterbeställning (alla tre i DFS eller i BFS algoritm)
- Träd finns i kategorin DAG: Directed Acyclic Graphs är ett slags riktat diagram som inte har några cykler.
- Olika typer av träd är: Binärt träd , Binärt sökträd, AVL-träd, högar.
- Trädapplikationer : sortering och sökning som Tree Traversal & Binary Search.
- Trädet har alltid n-1 kanter.
- Tree är en hierarkisk modell.
Svar
Så, kd-träd, vid första blicken, kan tyckas vara mer teoretiska än praktiska. Men det är verkligen inte fallet.
kd-träd innehåller en mängd viktiga applikationer, varav några inkluderar:
1 Närmaste grannsökning
Låt oss säga att du tänker bygga en Social polis i din smartphone. Social Cop hjälper människor att rapportera brott till närmaste polisstation i realtid.
Så vad verkar vara ett problem här?
Ja, du gissade rätt. Vi måste söka efter polisstationen närmast brottsplatsen innan vi försöker rapportera något.
Hur kunde vi göra det snabbt ?
Det verkar som om k-d-träd kan hjälpa dig att hitta närmaste granne till en punkt på en tvådimensionell karta över din stad. Allt du behöver göra är att konstruera ett tvådimensionellt kd-träd från platserna för alla polisstationer i din stad och sedan fråga kd-trädet för att hitta närmaste polisstation till en viss plats i staden.
Okej, jag förstår vad de kan göra. Men hur gör de det?
Om du redan vet hur binära sökträd fungerar, förstå hur kd-träd fungerar vara inget nytt. k-d-träd hjälper till att partitionera utrymme precis som binära sökträd hjälper till att partitionera verklig linje . k-d träd delar rekursivt en region av rymden och skapar en binär rymdpartition på varje nivå i trädet.
Så här ser en tredimensionell region i rymden uppdelad av ett tredimensionellt kd-träd ut [1]:
Ett tredimensionellt kd-träd. Den första delningen (röd) skär rotcellen (vit) i två underceller, var och en delas sedan (grön) i två underceller. Slutligen delas var och en av dessa fyra (blå) i två underceller. Eftersom det inte finns någon mer uppdelning kallas de sista åtta bladceller.
Och hur är trädet konstruerat?
Till att börja med har du en uppsättning punkter i ett k-dimensionellt utrymme.Låt oss ge oss ett exempel på ett 2-dimensionellt kd-träd:
Ingång: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Output: Ett tvådimensionellt kd-träd [2]:
Vid binära sökträd representeras den binära partitionen av den verkliga linjen vid varje intern nod av en punkt på den verkliga linjen. På samma sätt, i fallet med ett 2-dimensionellt kd-träd, representeras den binära partitionen av det 2-dimensionella kartesiska planet vid varje intern nod av ett linje i planet.
av binära sökträd fungerar punkten som representeras av den interna noden som den punkt som används för att partitionera den verkliga linjen. Hur väljer vi en partitioneringslinje vid 2-dimensionella kd-träd?
I huvudsak , kan du välja vilken linje som helst som passerar genom den punkt som representeras av den interna noden för att dela upp det tvådimensionella kartesiska planet.
Kd-trädutmatningen ovan har konstruerats med en enkel metod för att välja partitioneringslinjen vid varje interna nod i trädet: –
Nivå 0 : – Välj partitioneringslinjen vinkelrätt mot första dimensionen ( X i detta fall) och passerar genom den punkt som representeras av den aktuella noden.
Nivå 1 : – Välj partitioneringslinjen vinkelrätt mot andra dimensionen ( Y i detta fall) och passerar genom den punkt som representeras av den aktuella noden.
: : :
Nivå k-1 : – Välj partitioneringslinjen vinkelrätt mot kth dimension och passerar genom den representerade punkten av noden i fråga. Nivå k : – Välj partitioneringslinjen vinkelrätt mot första dimensionen ( X i detta fall) och passerar genom den punkt som representeras av noden i fråga.
Så i grund och botten växlar vi mellan X- och Y-dimensionerna för att välja en partitioneringslinje vid varje interna nod i kd-trädet.
Etiketterna som du ser bredvid var och en av noderna i kd-trädet [2] representerar valet av dimensionen för partitioneringslinjen vid noder på den nivån.
Låt ” s se nu hur vårt 2-dimensionella kd-träd skiljer det 2-dimensionella planet [3]:
Bra, hur gör jag sökningen?
Jag säger inte att jag lämnar det åt dig, men du ” Jag måste ta hjälp av några andra resurser för att förstå det helt. Jag kan dock säga att denna rymdpartitionering med ett kd-träd kan hjälpa dig att hitta närmaste granne till en viss punkt i rymden utan att behöva utforska alla partitioner vilket är vad vi behövde, göra rapportering i realtid för Social Cop.
För att förstå den närmaste grannalgoritmen på kd-träd är här en bra resurs: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Låt mig snabbt gå igenom några av de andra applikationerna av kd-träd, eftersom större delen av bakgrunden till kd-träd redan har behandlats i diskussionen om den första applikationen.
2. Databasfrågor med en flerdimensionell söknyckel
En fråga som frågar alla anställda i åldersgruppen (40, 50) och som tjänar en lön i intervallet (15000, 20000) per månad kan omvandlas till ett geometriskt problem där åldern ritas längs x-axeln och lönen ritas längs y-axeln [4]
[4] X-axeln anger åldern på arbetstagaren om år , och y-axeln anger månadslönen i tusen rupier .
Ett tvådimensionellt kd-träd på det sammansatta indexet för (ålder, lön) kan hjälpa dig att effektivt söka efter alla anställda som faller i den rektangulära delen av rymden som definieras av frågan som beskrivs ovan.
3. n-kroppsproblem [5]
Hur kan vi effektivt simulera rörelserna för en samling objekt som rör sig under ömsesidig gravationsattraktion?
Den naiva metoden skulle involvera beräkning av gravitationskraften mellan ett objekt på grund av alla andra objekt för att simulera dess rörelse under gravitationell attraktion. Dessutom skulle vi behöva göra det för varje objekt som skulle ta O (n ^ 2) tid.
Med hjälp av k-d-träd kan vi dock dela upp utrymmet och för varje underavdelning av rymden räkna ut dess totala effekt på resten av utrymmet. Nedan är algoritmens pseudokod [6].
Lägg objekten i ett träd. Börja på trädets nedre nivå, för varje region på ett djup d i trädet: Om några barn är löv, beräkna sedan interaktionen direkt Beräkna ” Multipole-expansion ”Konvertera detta till en lokal expansion för modernoden och skicka den. Gå vidare till nivå d-1. När vi når toppen av trädet, återvänd tillbaka ner i trädet och summera de lokala utvidgningarna.
4. Färgreduktion [7]
Vad är ett intelligent sätt att välja 256 färger för att representera en fullfärgsbild?
Den naiva metoden kan vara att plocka upp de färger som används oftast.
En mer effektiv metod kan dock representera färger i termer av deras RGB värden och konstruera ett tredimensionellt kd-träd för att dela utrymmet som innehåller alla färger på bilden. Konstruktionen av k-d-trädet skulle sluta när räkningen av bladnoderna blir lika med 256. Genomsnittet av RGB-värdet för var och en av de 256 partitionerna kan sedan användas för att få en 256 färgpalett för fullfärgsbilden.
Referenser: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Klassificering med närmaste grannar [5], [6], [7] : kD-träd