超级揽胜 零利酬宾 2016款路虎揽胜行政版现车到店 豪

百度 会议将《政府工作报告》提出的12个方面57项重点任务逐项分解、明确责任，要求各部门、各单位依法履职，勤勉尽责，建立抓落实工作责任制，一把手要亲自抓、负总责，抓紧制定推进重点工作的方案和台账，做到每项任务有措施、有进度安排、有责任人，对市场和群众期盼的重点措施要抓紧出台实施，强化督查，确保落地见效，确保完成全年经济社会发展主要目标任务，实现新一届国务院工作良好开局。

Tr?r er en av de mest brukte datastrukturene innenfor informatikken. Den bygger p? matematikkens grafteori.

Et tre er en samling elementer kalt noder, som forbindes med pekere (kanter). én node er definert som roten i treet. Det kan ikke finnes sykler i et tre, og det m? v?re sammenhengende.

Et tre med $N$ noder vil ha $N-1$ kanter.

En node sies ? v?re barnet til noden den pekes p? fra niv?et over, og er forelderen til nodene den peker p? i niv?et under. Noder som ikke har noen barn kalles bladnoder. Et tre inneholder mange subtr?r, der roten i et subtre er barnet til en node i treet p? niv?et over.

En sti fra node n₁ til n_k er definert som en sekvens av noder n₁, n₂, ..., n_k slik at n_i er forelderen til n_i+1 for alle i fra og med én til k. I et tre er det n?yaktig én sti fra roten til hver node. Dybden av en node er lengden p? en sti fra roten av treet til noden. H?yden av en node er lengden p? den lengste stien fra noden ned til en bladnode.

Bin?re tr?r

Et bin?rt tre: hver node peker p? maksimum to barn

Et bin?rt tre er et tre der hver node kan ha maksimum to barn. Man kan derfor la hver node ha en direkte peker til hvert enkelt barn. Tr?r av denne typen vil ha en gjennomsnittlig dybde p? $O({\sqrt {n}})$.

Bin?re tr?r brukes innenfor flere omr?der av informatikken, og spesielt innenfor kompilatordesign.

Bin?re s?ketr?r

I et bin?rt s?ketre har hver node f?tt tilordnet en verdi. Et bin?rt s?ketre kjennetegnes av at verdien i en node er st?rre enn alle verdiene i venstre subtre, og mindre enn alle verdiene i h?yre subtre.

Et bin?rt s?ketre vil ha en gjennomsnittlig dybde p? $O(\log _{2}n)\,$. Dette gj?r at man raskt kan finne et element i et bin?rt s?ketre.

Innsetting av et element i et slikt tre er ogs? relativt enkelt. Det gj?res ved ? s?ke seg frem til riktig plass i treet, p? samme m?te som for finn-operasjonen, og deretter dytte noden man tar plassen til ned som barnet til noden man setter inn.

Det er noe verre ? slette en node fra det bin?re s?ketreet. Om noden man vil slette er en bladnode, kan den slettes umiddelbart. Om noden man vi lette bare har ett barn, kan man slette den og la foreldrenoden til den man slettet peke p? barnenoden til noden man slettet. Om noden man vil slette har to barn, m? man erstatte noden man sletter, men det minste barnet i h?yre subtre, og rekursivt slette noden man flytter opp.

R?d-svarte tr?r

En variant av bin?re s?ketr?r kalles r?d-svarte tr?r. I denne tretypen f?r hver node tildelt en farge, enten r?d eller svart, basert p? tre regler:

1. Roten i treet er svart
2. Om en node er r?d, m? barna v?re svarte
3. Alle stier fra en node til en null-referanse m? inneholde det samme antallet svarte noder.

Disse reglene f?rer til at h?yden p? et r?d-svart tre med n noder er maksimum $2log_{2}(n+1)\,$. S?king blir derfor alltid en logaritmisk operasjon, faktisk kan alle operasjoner p? r?d-svarte tr?r gj?res med tidsforbruk $O(log_{2}n)\,$.

Det er relativt fiklete ? sette inn nye elementer i et r?d-svart tre. Dette gj?r at denne datastrukturen ikke lenger brukes s? mye.

B-tr?r

B-tr?r brukes ofte n?r datamengden blir s? stor at et helt tre ikke kan legges i hovedminnet, slik at deler av det m? legges p? platelageret. Da man typisk kan gj?re hundrevis av tusen regneoperasjoner i prosessoren i l?pet av tiden det tar ? gj?re én diskaksess, er det viktigste ? minimere antallet diskoperasjoner i slike tilfeller.

I et B-tre av orden M lagres alle data i bladnodene. Ikke-bladnoder vil inneholde n?kler som brukes i s?kingen i treet. Roten i B-treet har mellom to og M barn, og de andre ikke-bladnodene har mellom M/2 (rundet av oppover) og M barn. Alle bladnoder har mellom L/2 (rundet av oppover) og L dataverdier i seg, der L er en konstant typisk valgt p? grunnlag av st?rrelsen p? diskblokkene til disken treet skal lagres p?.

Bin?rheaper

En bin?rheap er en form for prioritetsk? som representeres ved hjelp av et tre. I motsetning til andre typer tr?r implementeres vanligvis ikke en bin?rheap ved hjelp av grafer, men med bruk av et array.

En bin?rheap er et bin?rtre som er fullstendig fylt opp, med et mulig unntak for det nederste niv?et, som fylles opp fra venstre mot h?yre. En bin?rheap med h?yde $h$ vil derfor inneholde mellom $2^{h}$ og $2^{h+1}-1$ noder. Dette gj?r at at operasjoner p? en bin?rheap vil v?re $O(logN)$.

Ved hjelp av denne datastrukturen er det lett ? finne det minste elementet i en datamengde (eventuelt det st?rste, om man velger ? heller implementere treet slik). Dette kommer av at det minste elementet i en bin?rheap alltid ligger i roten. Siden hvert subtre ogs? er en bin?rheap, vil hver node ha mindre verdi enn alle deres barn, barnebarn og andre ?etterkommere?.

Disse attributtene gj?r ogs? at det er greit ? sette nye elementer inn i en bin?rheap. En sett inn-operasjon vil v?re $O(1)$ gjennomsnittlig, og $O(logN)$ i verste fall. Dette f?rer ogs? med seg at oppbygningen av en bin?rheap vil i gjennomsnitt v?re en $O(N)$-operasjon.