Note de curs, clasele 11-12, 17 mai 2013: Difference between revisions

From Algopedia
Jump to navigationJump to search
No edit summary
 
(No difference)

Latest revision as of 14:21, 24 May 2013

Preambul

Căutăm o structură care să permită inserare / ștergere / căutare / minim / maxim / anterior / următor / enumerare interval (x, y), toate în O(log n). Am discutat deja despre skip lists, care se implementează ușor. Există și soluții bazate pe arbori binari, care prezintă interes din multe motive.

Arbori cartezieni

  • cerință: pentru un vector V, să se calculeze muchiile unui arbore binar construit astfel
    • nodul minim din vector, fie el pe poziția i, este rădăcina arborelui
    • nodurile 0 ... i - 1 constituie arborele stâng, construit recursiv
    • nodurile i + 1 ... n - 1 constituie arborele drept, construit recursiv
  • pentru rezolvare, începem de la problema nearest neighbor: dându-se un vector V, să se calculeze un alt vector W unde W(i) este cel mai mare indice j < i pentru care V[j] < V[i]
  • pe aceasta știm să o rezolvăm în O(n)
  • pentru arborele cartezian, precalculăm cei mai apropiați vecini mai mici, atât în stânga, cât și în dreapta
  • părintele elementului i este maximul dintre vecinul stâng și cel drept
  • demonstrație de ce este așa
  • observație: arborele cartezian are proprietate de heap
  • aplicație: putem reduce RMQ la LCA folosind arborele cartezian
  • scurtă recapitulare despre cum reducem LCA la RMQ folosind o parcurgere Euler

Arbori binari aleatori

  • să considerăm cele n! permutări ale mulțimii { 1, 2, ..., n}. Pentru fiecare din ele, construim un arbore binar de căutare inserând cele n numere în ordinea dată de permutare
  • numai două permutări duc la un arbore complet degenerat: cele ordonate crescător sau descrescător
  • mult mai multe for genera un arbore perfect echilibrat (de exemplu, 15 noduri pe 4 niveluri)
  • intuitiv, arborii aleatori sunt bine echilibrați, dar unde este media?
  • demonstrație că 1 + 1/2 + ... + 1/k < ln k
  • o valoare i < x apare pe calea dinspre rădăcină spre nodul x numai dacă i este primul număr din intervalul [i, x] care este inserat
    • demonstrație
  • așadar P[i apare înaintea lui x] = 1 / (x - i + 1)
  • la fel și pentru i > x
  • lungimea așteptată a căii de la rădăcină la orice x este suma probabilităților pentru fiecare i, adică maxim 2 * ln n

Treaps

  • vrem să fie arbori binari de căutare, adică parcurgerea în inordine să genereze setul ordonat de chei
  • vrem să fie și heap / arbore cartezian, adică orice părinte să fie mai mic decât copiii săi
  • dar, pentru un set de numere dat, singurul arbore binar cu aceste proprietăți este cel degenerat spre dreapta
  • atunci, heap-ul nu mai este construit după înseși valorile numerelor, ci după niște priorități generate aleator
  • demonstrație că treap-ul construit pentru un set de perechi (valoare, prioritate) este unic
    • rădăcina este obligatoriu nodul cu prioritate minimă, etc.
  • subarborii au maxim 3 n / 4 noduri cu probabilitate 0,5 (dacă ne uităm care din cele n noduri ar putea fi ales drept rădăcină)
  • deci, intuitiv, un treap este bine echilibrat
  • de fapt, am putea obține același treap sortând numerele după prioritate și inserându-le într-un arbore binar neechilibrat
  • echivalent, un treap este un arbore binar neechilibrat în care inserăm o permutare random a celor n elemente

Operații pe treap:

  • căutare: binară; nimic deosebit
  • inserare: generăm o prioritate aleatoare; inserăm în arborele binar după valoare; rotim spre rădăcină câtă vreme nodul are prioritate mai mică decât a părintelui
  • ștergere: ca la arborii binari de căutare; în plus, elementul așezat în locul celui șters trebuie rotit pentru ordonarea priorităților
  • split (spargere după o valoare x în doi arbori cu cheile mai mici, respectiv mai mari decât x): inserăm x cu prioritate minimă în arbore; atunci el va ajunge la vârf, iar copiii stâng și drept au chei mai mici, respectiv mai mari decât x
  • caching (experimental): la fiecare accesare a unui nod, generăm o nouă prioritate și o folosim dacă este mai mică decât cea veche. Arborele nu mai este random, dar nodurile mai des folosite urcă în arbore.

Arbori echilibrați

  • principii: nu putem garanta înălțimea O(log n), dar 2 O(log n) este posibil
  • mecanismul de bază este rotația după inserări / ștergeri, pentru a păstra structura arborelui
  • dacă un arbore nu este modificat în timpul citirii, ci numai în timpul modificării, algoritmul se paralelizează bine
  • scurtă discuție despre arbori roșu - negru (sunt greu de implementat)

Arbori splay

  • nu oferă garanții despre înălțimea arborelui
  • analiza este amortizată, peste multe accesări, iar timpul este logaritmic
  • sunt optimizați pentru cazul practic în care 10% dintre elemente au 90% dintre accesări
  • se implementează mai ușor, căci nu rețin înălțimi, culori etc. pentru fiecare nod
  • principiu: la fiecare accesare, nodul găsit este rotit (splayed) până la rădăcină
  • observație: arborele se modifică și în timpul căutării, ceea ce nu se paralelizează bine
  • trei tipuri de rotații:
    • zig-zig (când x este nepotul stâng-stâng sau drept-drept al bunicului său)
    • zig-zag (când x este nepotul stâng-drept sau drept-stâng al bunicului său)
    • zig (când x este copilul rădăcinii)
  • bottom-up splaying: după ce găsim nodul, sau ultimul nod candidat, îl rotim până la vârf
  • top-down splaying: pe măsură ce ne îndreptăm spre nod, rotim arborele
    • este mai greu de înțeles, dar mai eficient și cu mai puține cazuri particulare
  • discuția operațiilor pe arbori splay

Analiza complexității

  • enunțarea metodei potențialului
  • demonstrarea propriu-zisă rămâne pentru ora viitoare