Pievienot darbus Atzīmētie0
Darbs ir veiksmīgi atzīmēts!

Atzīmētie darbi

Skatītie0

Skatītie darbi

Grozs0
Darbs ir sekmīgi pievienots grozam!

Grozs

Reģistrēties

interneta bibliotēka
Atlants.lv bibliotēka
Akcijas un īpašie piedāvājumi 2 Atvērt
3,49 € Ielikt grozā
Gribi lētāk?
Identifikators:813148
 
Autors:
Vērtējums:
Publicēts: 16.01.2007.
Valoda: Latviešu
Līmenis: Augstskolas
Literatūras saraksts: 5 vienības
Atsauces: Nav
SatursAizvērt
Nr. Sadaļas nosaukums  Lpp.
  Apraksts    3
  Sarkan-Melnā koka datu struktūra    3
  Galvenās īpašības    4
  Melnais-augstums (black-height)    4
  Lemma    5
  Simulācija    5
  Rotācija    5
  Left-Rotate pseudo kods    5
  Ievietošana (Insertion)    6
  RB-Insert pseudo kods    6
  Dzēšana (Deletion)    9
  RB-Delete pseudo kods    9
  RB-Delete-Fixuo pseudo kods    10
  Nobeigums    12
  Izmantotā literatūra    13
Darba fragmentsAizvērt

Koks ir struktūra, kas attēlo hierarhiskas attiecības starp datu laukiem. Koki ir viena no vissvarīgākajām datu struktūrām datoru zinātnē, jo ar to palīdzību var vieglāk organizēt informācijas glabāšanu un tās apstrādi.
Koks – mezglpunktu kopa (var būt tukša), kas satur sakni, kurai ir nulle vai vairāk apakškoku.
Sakne (root) – mezgls, kas ir koka pašā augšā (augšējais līmenis).
Zars (edge) – saite starp 2 līmeņiem.
Mezgls jeb mezglpunkts (node) – katrs lauks kokā. Tie ir domāti informācijas glabāšanai.
Lapa (leaf) – lauks, kuram nav apakšlīmeņu (nav bērnu).
Mezgla augstums (height) – garums garākajam ceļam no šī mezgla līdz kādai lapai. Lapām augstums ir 0.
Mezgla dziļums (depth) – garums ceļam no saknes līdz šim mezglam.
Sarkan-Melno koku atklāja 1972. gadā Baijers (Bayer), zem nosaukuma „simetriski binārie B-koki”.
Sarkan-Melnais koks ir viens no daudzajiem meklēšanas koku struktūrām, ar kuru palīdzību var nodrošināt galvenās funkcionālās operācijas O(lg n) laikā vissliktākajā gadījumā. Tas ir binārs meklēšanas koks ar vienu papildus glabāšanas bitu mezglam, tas ir, krāsu, kura var būt vai nu sarkana (red), vai nu melna (black). Veidojot saites, mezgli var tikt iekrāsoti jebkurā ceļā no saknes līdz lapai, līdz ar to Sarkan-Melnie koki nodrošina, ka šādi ceļi ir vairāk nekā divas reizes garāki nekā jebkuri citi, tā tad koks ir apmēram balansēts.
Sarkan-Melnais koks ir tāda saistīta datu struktūra, kam katrā iekšējā mezglā var būt tieši divi bērni. Ja bērnu vai vecāku mezgli neeksistē, tad attiecīgā mezgla norādes laukums satur vērtību NIL. Šajos kokos uzskata NIL kā ārēju mezglu (vai lapu) un atslēgas kā iekšējos koka mezglus. Sarkan-Melnā binārā meklēšanas koka mezglu x laukumi:
atslēga (key): x atslēga, key[x];
loceklis (satellite): locekļa x dati, satellite[x];
kreisais (left): norāde uz x kreiso bērnu, left[x];
labais (right): norāde uz x labo bērnu, right[x];
p (parent): mezgla x vecāki, p[x];
krāsa (color): mezgla krāsa, vai nu sarkana vai arī melna, color[x].
Ja kreisais, labais vai p nav norādīti mezglā, tad tie ir NIL.…

Autora komentārsAtvērt
Parādīt vairāk līdzīgos ...

Atlants

Izvēlies autorizēšanās veidu

E-pasts + parole

E-pasts + parole

Norādīta nepareiza e-pasta adrese vai parole!
Ienākt

Aizmirsi paroli?

Draugiem.pase
Facebook

Neesi reģistrējies?

Reģistrējies un saņem bez maksas!

Lai saņemtu bezmaksas darbus no Atlants.lv, ir nepieciešams reģistrēties. Tas ir vienkārši un aizņems vien dažas sekundes.

Ja Tu jau esi reģistrējies, vari vienkārši un varēsi saņemt bezmaksas darbus.

Atcelt Reģistrēties