hierarki

struktur eller organisation som har en rangskala där varje person eller annat ingående element är överordnad, underordnad eller båda. I synnerhet en sådan struktur som har många led och krav på att de underordnade ska rätta sig efter de överordnade. – Ordet användes från början om kyrkans uppbyggnad, men det har överförts till alla slags organisationer, från arméer till företag. (Hierarki kommer av de grekiska orden för präst och styrelse.) Det används också om strukturering av information i överordnade och underordnade kategorier. De underordnade kategorierna har egenskaper som de ”ärver” av de överordnade, se hierarkisk. – Om man ritar en hierarkisk struktur som en graf är det en riktad trädstruktur. – På engelska: hierarchy.

[datastrukturer] [informationshantering] [ändrad 14 maj 2018]

polyhierarki

en variant av hierarkiskt ordnad information där element kan ligga under två eller flera överordnade kategorier. – Exempel: piano kan klassificeras både som stränginstrument (pianon har strängar, som gitarr och fiol) och som tangentinstrument (som orgel och synt). Om man använder en polyhierarkisk struktur för att ordna information på webben ger man användarna flera vägar till det de söker, och utvecklaren slipper välja (stränginstrument eller tangentinstrument?). Det gör det lättare att till exempel hitta en produkt i en postorderkatalog på webben. – Om man ser den polyhierarkiska strukturen som en graf kan man säga att en nod kan ha två eller fler föräldrar. En vanlig (enkel) hierarki kan ritas upp som en trädstruktur, men en polyhierarki är mer som en buske och förgrenar sig både uppåt och nedåt. – Jämför med multipelt arv.

[datastrukturer] [14 maj 2018]

riktad acyklisk graf

en graf där förbindelserna mellan noderna (kanterna) beskriver enkelriktade relationer, och där det inte går att komma tillbaka till utgångspunkten om man följer förbindelserna i angiven riktning. Sådana grafer kan bland annat åskådliggöra förlopp i tiden. – På engelska: directed acyclic graph, förkortat DAG.

[datastrukturer] [nätverk] [9 maj 2018]

binärträd

(binary tree) – en trädformad datastruktur där varje nod har högst två barn. (”Barn” är grenar, kanter, som går till direkt underordnade noder.) En datamängd är fördelad bland noderna. Som alla trädformade data­struk­turer är trädet upp-och-ner­vänt med roten överst. Det kan bara finnas en rot. En nod kan ha noll, en eller två barn. En nod med noll barn kallas för löv. – Binärträd används ofta för lagring av information och för att möjliggöra sök­ningar. De värden som står i varje nod är då ofta hänvisningar. – Att balansera ett binärträd är att fördela noderna så att djupet från rot till löv blir så likartat som möjligt i alla förgreningar. Binärträdets höjd (det största djupet som finns i trädet) ska alltså ligga så nära det genom­snitt­liga djupet som möj­ligt. Den genom­snitt­liga söktiden, om man söker efter värden som kan finnas var som helst i binär­trädet, blir kortast om trädet är balanserat. – Att sortera ett binärträd är att se till att värdena på noderna är ordnade enligt ett system – alfabetisk, num­mer­ord­ning eller annat. Det innebär att nya värden måste läggas in på en bestämd plats i trädet, inte bara där det är enklast att lägga det. I ett sorterat träd kan man lätt ta kortaste vägen till ett visst värde. – Att se till att ett binärträd är både balanserat och sorterat kan vara omöjligt.

[datastrukturer] [9 mars 2017]

rotationskö

(round robin) – i programmering: med tidsbegränsning. Det är en data­struktur. Processer som står i kö behandlas i tur och ordning (först in – först ut), men det får bara ta en viss begränsad tid för varje process (sam­ma tid för alla). Om pro­cessen inte kan avslutas i tid avbryts be­hand­lingen, och processen får ställa sig sist i kön. Fördelen med principen ro­ta­tions­kö är att en tids­kräv­ande pro­cess inte kan block­era andra processer. – Kallas på svenska också för cirkulär processlista.

[datastrukturer]