fak Flashcards
fa
homogen, dinamikus, hierarchikus, neha folytonos, neha szetszort
bejarasok
pre, in, post order
kifejezesfa
post es prefix bejaras egyertelmu
binaris keresofa kiegyensulyozottsaga
kiegyensulyozott, ha a bal es a jobb oldali level kozott maximum 1 a kulonbseg
kiegyensulyozott keresofa torles es beszuras
logaritmus2 n
piros fekete fa nyilvantartas
kulcs, szin, bal gyerek, jobb gyerek, szulo
gyoker midig fekete
minden nil fekete
minden csucsra igaz, hogy minden alatta levo levelekhez vezeto uton ugyan annyi fekete csucs van
piros fekete fa magassaga
2*log2(n+1)
piros fekete fa muveletek
folytonos, vagy lancolt reprezentacio
tree-insert/delete + recolor + rotate
iterative-tree-search
piros fekete fa forgatas
egy adott levelet kicsereljuk egy masik levellel, majd ahhoz merve atrendezzuk
piros fekete fa beszuras
mindig piros csucsot szurunk be
elso, harmadik es otodik tulajdonsag NEM serulhet
3 eset:
- z nagybacsija piros
- z nagybacsija fekete es haromszogben van
- z nagybacsikaja fekete es egyenesunk van
B-fa
- merevlemezkhez alakitottak ki
- nem binaris fak, lapozas szamanak minimalizalasa a celja
- a magassagat az hatarozza meg, hogy hanyszor fordulunk egy hattertarhoz
B-fa, elagazasi tenyezo
a csucsok gyermekeinek szamat elagazasi tenyezonek hivjuk
ha ez valtozo, akkor atlagos elagazasi tenyezonek hivjuk
sokszor 50-2000 kozotti elagazasi tenyezo
B-fa tulajdonsagai
- x.n a az x-ben tarolt kulcsok szama
- a kulcsok novekvo sorrendben vannak
- logikai erteke van, ami csak akkor igaz, ha x level
- ha x nem level, akkor tartalmaz egy mutatot ami x gyerekeire mutat, jelolese x.c1…
- minden elvel azonos szinten helyezkedik el
- minden csucs legfeljebb 2t-1 kulcsot tartalmazhat, es minimum t-1
b-fa magassaga
logt(n+1/2)
