[SCRÂTÂND]
[FOȘTIT]
[CLIC]
JASON KU: Bun venit la a
patra sesiune cu probleme.
Vom vorbi în
mare parte despre arbori binari astăzi.
Vom vorbi puțin
despre grămezi binare, care
este un subiect pe care nu îl vom
trata până marțea viitoare,
dar va apărea
în moduri foarte mici
în setul dvs. de probleme 4, care
va avea loc vinerea viitoare.
Așa că voi trece peste un
pic din acel material astăzi.
Dar este în mare parte îngrijorător -
materialul subiectului pentru
astăzi este în mare parte arbori binari, în
special, fiind aplicat
pentru a seta structuri de date
și structuri de date secvențe,
așa cum v-a vorbit profesorul Demaine la
începutul acestei săptămâni.
Dar deocamdată-- de fapt,
de ieri--
ați văzut toate
structurile de date pe care le vom
acoperi--
care vor implementa
interfața setată și
interfața secvenței.
Acele tabele frumoase pe care
vi le arată profesorul Demaine,
sunt acum complete.
Avem niște
structuri de date care
sunt foarte bune-- operațiuni în timp constant
pentru unele operațiuni.
Așa că le putem folosi
pentru unele aplicații.
Și săptămâna aceasta, v-am
descris
arbori, care
realizează, într-adevăr, destul de
bine, pentru orice tip de
operație de interogare pe seturile
sau secvențele mele --
destul de bine, adică
timp logaritmic, nu destul de constant.
Dar, pentru scopurile noastre, log n este--
Adică, pe
computerul tău, practic--
nu asimptotic,
ci practic-- log
n va fi cel mult
ce pe computerul tău?
Ceva de genul 64, nu?
Orice intrare cu care operați
, în cuvinte mașini,
este intrarea dvs.
Trebuie să fiți capabil să
adresați toate acele
cuvinte ale mașinii din intrarea dvs.
Și pe computerul tău, dimensiunea
adreselor cuvintelor mașinii tale
este de 64 de biți, nu?
Și presupunem că
dimensiunea cuvântului este cel puțin
dimensiunea în jurnal a intrării dvs., astfel
încât să puteți aborda intrarea.
Deci, pentru scopurile dvs.,
pe computerul dvs.,
jurnalul n va
fi mai mult de 64,
ceea ce înseamnă că veți primi
o suprasarcină de 50 de ori,
sau pentru cazuri mai mici,
ar putea fi mai mult ca 10,
dacă aveți 1.000 de lucruri.  la
care lucrezi.
Nu e chiar așa de rău, nu?
Este o constantă - nu este
un factor constant în
scopuri teoretice, dar pentru scopurile dvs.,
log n este mult mai bun decât
un factor polinomial - un
alt factor al lui n.
Ai văzut tot codul.
Ați văzut implementări ale
tuturor acestor interfețe de set și secvență
, nu?
Așa că am continuat și am
scris puțin...
Am compilat tot acel cod
din notele voastre de recitare,
din toate
implementările diferitelor interfețe.
Și ceea ce am făcut a fost că am
scris un mic program de testare
pentru a vedea cum funcționează
pe o mașină reală.
Am un mic cod de test aici.
Am un mic folder care
listează o matrice care implementează
o secvență, un
arbore binar care implementează
o secvență, o
matrice dinamică care implementează -
toate aceste tipuri de lucruri.
Apoi setați lucrurile - o matrice sortată
fiind un set într-un arbore binar
și un tabel hash.
Acestea sunt implementările noastre.
Nu folosesc
dicționare Python pentru tabelele hash,
folosesc implementările
care sunt în recitarea ta.
Și voi
rula acest mic
cod Python de eficiență de testare
care practic îl va
elibera pe fiecare.  Va
face o grămadă de
aceste operațiuni diferite
și va măsura pentru a vedea
cât timp a durat.
Înregistrez doar
cât timp a durat.
Nu este o
analiză asimptotică, dar sperăm că
vedem o oarecare separare.
Deci, când apăsați pe asta,
rulează o grămadă de teste.
Hai să aruncăm o privire.
BINE.
Am o grămadă de
operații de secvență.
Avem build, set_at,
get-at, insert, delete,
în diferite locuri.
Și acestea sunt
momentele reale la o anumită scară -
la o anumită rezoluție pe care am avut-o
pentru aceste structuri de date.
Și puteți vedea că construirea -
de fapt, construirea
pe această mașină,
doar alocarea unei
matrice și ștergerea acesteia
este un lucru cu adevărat eficient pe care
Python îl va face pentru mine.
Și asta este de fapt... este
etichetarea greșită ca log n.
Dar aceste alte lucruri,
get_at și set_at-- cu
adevărat, foarte repede, nu?
Este timpul constant.
Și apoi aceste alte
lucruri, în esență,
nu pot face mai bine decât să
parcurg chestia în buclă, așa că
este nevoie de timp liniar.
Și din nou, chestii de secvență,
setarea_at și obținerea_at
sunt lente, dar ștergerea și
eliminarea de la primul lucru,
doar re-conectez
indicatorul, nu?
Matrice dinamice.
Din nou, set_at, get_at este
rapid, pentru că sunt doar
matrice obișnuite.
Și apoi inserarea
și ștergerea ultimului,
asta înseamnă,
în esență, timp constant.
Acum, de fapt... când
rulez aceste teste pentru a mă ocupa de
medii, de
fapt rulez
aceste lucruri, de multe ori,
și le testez performanța.
Și așa că nu văd că
cel mai rău caz se întâmplă aici, nu?  Fac o
medie asupra tuturor
lucrurilor, ceea ce

înseamnă exact amortizarea.  De
aceea am
performanță bună aici.
O masă hash.
Din nou, într-adevăr...
oh, deci despre asta am
vorbit
în sesiunea cu probleme de
săptămâna trecută, implementând
un fel de coadă dublă
cu un tabel hash.
Aceasta este implementarea.
Am vrut doar să ți-o arăt.
Dar de fapt este destul de bine.
Acesta este ceea ce JavaScript
folosește pentru matrice.
Și apoi o secvență binară
reprezentată ca un arbore binar -
un arbore binar echilibrat.
Acesta este codul nostru AVL pe care îl aveam.
Și toate celelalte lucruri
au fost destul de proaste
la insert_at și
delete_at, dar acesta
este comparabil cu toate
celelalte lucruri.
Acum, vezi că acestea sunt
puțin mai multe
cicluri de mașină decât celelalte lucruri,
dar nu chiar atât de rău, de fapt.
Și apoi, pe
partea setată a lucrurilor,
din nou, am avut o matrice sortată.
Ne pare rău, acesta este un
set dintr-o matrice.
Practic, este
o matrice nesortată.
Caut doar toate
lucrurile... sunt vremuri foarte proaste.
Matricea sortată
găsește aceste operațiuni grozave,
dar inserarea și
ștergerea sunt slabe.  De
aceea avem nevoie de arbori binari.
Tabelele hash au operațiuni bune de dicționar
, dar
operațiuni de ordine proastă.
Și apoi arborele de căutare binar
, un arbore binar stabilit, din nou,
face destul de bine în
toate aceste lucruri.
De fapt, devine
destul de bun-- devine mai
bun, dintr-un motiv
oarecare,
decât a făcut-o chiar și matricea sortată.
Nu știu de ce.
Implementările noastre
nu sunt deloc optimizate.
Dar se descurcă destul de
bine asimptotic.
Da?
PUBLIC: Ați putea
explica din nou
de ce prima
trezorerie de date [INAUDIBIL] log n?
JASON KU: Acesta este doar
etichetat pe baza timpului.  Se întâmplă
că,
probabil, există
un C intrinsec sub Python
care alocă acest lucru
și, prin urmare, o face foarte repede.
Programul meu care se
uită la aceste numere
și încearcă să ghicească care
este timpul de rulare asimptotic,
acestea sunt doar etichete bazate
pe aceste lucruri, intervale.
Eu doar... este greșit caracterizat.
PUBLIC: [INAUDIBIL]
JASON KU: Da.  Ei
bine, vreau să spun, de fapt,
dacă ar fi codul C--
dacă toate aceste lucruri ar
fi în C, probabil,
am vedea că bara este
mai lungă, pentru că de fapt
trebuie să treacă și să
atingă toată acea memorie.
Încă face asta aici,
dar toate chestiile cu Python
sunt super crude.
Este de 100 de ori mai lent
decât orice face C.
Și așa vezi
această diferență.
Are sens?
BINE.
Am vrut doar să-ți arăt asta.  S-
ar putea să-l lansăm pentru ca
să vă jucați,
dar am vrut doar să
vă dăm un gust.
OK, vreo întrebare
înainte de a merge mai departe?
Cum dezactiv acest lucru?
Sus, și dezactivat.
Închide.
Da.
BINE.
Trecerea la probleme -
rezolvarea unor probleme.
Aveți setul dvs.
de probleme aici.
Prima este că ne vom
uita la un arbore AVL secvență.
Acesta este un arbore AVL de secvență.  De
unde știu asta?
Nu, neapărat.
Dar aceste lucruri cu
siguranță nu sunt
în ordinea sortată a lucrurilor pe care le
depozitez în ele, da?
Deci ar fi bine să nu
fie un arbore AVL setat.
Este un arbore AVL?
Este echilibrat...
echilibrat pe înălțime?
Da, practic.
De fapt, dacă calculați
dimensiunea fiecărui subarbore,
subarborele din stânga și din dreapta
pe toate acestea -- vă
puteți confirma singur --
sunt echilibrate.
Sunt în plus sau
minus 1 unul de celălalt.
De fapt, acest lucru este la fel de
departe de echilibrat
pe cât ai putea obține
pentru atâtea noduri,
menținând în același timp
echilibrul înălțimii --
menținând proprietatea AVL -- de aceea

acesta este un exemplu instructiv.
E cam la limită.
Și ce am de gând să fac?
Ce lipsește din această
imagine dacă susțin că
acesta este un arbore AVL de secvență?
Ceva idei ce lipsește?
Ce stochează arborele AVL de secvență
pe care nu îl
arăt în această imagine?
PUBLIC: Contează.
JASON KU: Ce?
PUBLIC: Contează.
JASON KU: Contează.
Și?
Este un arbore AVL secvență.
Înălțimi, nu?
Arborii AVL de secvență,
diferiți de arborii AVL setați,
sunt măriți de
două lucruri, nu?
Pentru că trebuie să
mențin echilibrul în timpul
rotațiilor, așa că
trebuie să păstrez înălțimile.
Trebuie să pot spune care sunt
înălțimile acestor subcopaci
în timp constant
când merg în sus prin
copac, repar lucrurile.
Și secvența îmi cere
să stochez acolo numerele lor subarbore
.  Nu
știu...
Nu o să-l desenez
pentru toate aceste lucruri, dar
ce zici de numărul patru?
Care este înălțimea lui?
1, 2, 3.
Aceasta este calea cea mai lungă de la
subarborele rădăcină al acestuia.
Deci aceasta este înălțimea egală cu 3.
Asta a venit de la înălțimea egală cu
2 și înălțimea egală cu 1.
Vede toată lumea asta?
Da?
Și apoi dimensiunea de
aici, cât de mare este?
Adică 1, 2, 3, 4, 5, 6, 7.
Aceasta este... Voi
pune dimensiunea egală cu 7 aici.
Și asta vine de la
acest tip, 1, 2, 3, 4.
Și acest tip este 2.
Deci, cum calculez
dimensiunea subarborelui?
Este dimensiunea subarborelui din stânga plus
dimensiunea arborelui din dreapta plus 1.
Și înălțimea mea ia
maximul de 2 plus 1. În
regulă.
Așa că am făcut toate astea ieri.
Eu doar etichetez aceste lucruri.
Și ceea ce vă cer este
să efectuați o operațiune de ștergere.
Acesta este un arbore de secvențe.
Așa că găsesc lucruri după
indicele lor în copac.
Așa că o să vă rog
să ștergeți al optulea lucru
din secvența mea.
Care este al 8-lea
lucru din secvența mea?
Da?
PUBLIC: Doar pentru a clarifica,
deoarece delete-8 nu este ștergerea
numărului.
JASON KU: Corect.  Ei
bine, șterge_la 8.
Vezi asta?
Este o operație secvențială.
PUBLIC: Oh, bine.
[INAUDIBIL]
JASON KU: Da.
Deci, acest lucru este foarte
important, să faceți
diferența între semantica
secvenței și setările.
Dacă am de-a face
cu secvența, ar
fi bine să nu
caut lucruri intrinseci
pe această structură de date, pentru că nu
este o structură de date intrinsecă
.
Nu suportă asta.
Dacă aș fi vrut să susțin găsirea,
să zicem, indexul cheii 8,
sau ceva de genul acesta,
atunci tot ce aș putea face
este -- este similar cu o matrice.  Ar
trebui doar să parcurg
întreaga secvență
și să-mi spun dacă
chestia este în ea.
Nu se poate face mai bine
decât timpul liniar.
Această structură de date
nu este concepută pentru asta.
Pentru ce este conceput?
Este conceput pentru a găsi lucruri
după indexul lor în secvență.
Deci, cum găsesc al 8-lea index?
Ei bine, vreau să spun, mă
uit la copac
și pot doar număra de-a lungul
traversării în ordine.
Care este traversarea în ordine?
0, 1, 2, 3, 4, 5, 6, 7.
OK, găsit 8.
Dar ce face un
arbore AVL secvență?
Stochez
dimensiunile subarborelor și, când sunt aici,
nu știu la ce index mă aflu.
Cum pot afla la ce
index mă aflu de la rădăcină?
Mă uit la subarborele meu din stânga,
văd câți sunt.
Sunt șapte lucruri aici.
1, 2, 3, 4, 5, 6, 7.
Da.
Pentru că caut al
9-lea articol după indicele 8.
Asta înseamnă că
sunt al 8-lea articol.
Eu sunt tipul de la indicele 7.
Are sens?
Pentru că mă uit la
dimensiunea subarborelui aici.
Deci ce știu?
Știu că indexul pe care îl
caut este în dreapta mea.
Mă duc aici
și se întâmplă să știu...
ce index caut
în acest subarbore?
0, nu?
Vreau primul
lucru din subarborele.
Indexul meu de căutare s-a schimbat
acum, pentru că, în esență, m-am ocupat de
toate aceste opt articole.
Aici, caut al
0-lea lucru din indexul meu.
Mă uit în stânga mea --
dacă nu aș avea un subarboresc din stânga,
aș fi al 0-lea lucru
și m-aș întoarce.
Dar sunt chestii aici.
Așa că caut al 0-lea lucru
aici, care este doar el,
și îl returnez.
Și de fapt, ceea ce
fac este că îl șterg.
Asa ca il sterg.
naiba.
Care este problema aici?
PUBLIC: [INAUDIBIL]
JASON KU: Nu este echilibrat pe înălțime.
Ce nu este echilibrat aici?
PUBLIC: Subarborele din stânga este...
sau, îmi pare rău.
[INAUDIBIL]
JASON KU: Tipul ăsta nu are
înălțime echilibrată, nu?
PUBLIC: --subarborele
din dreapta [INAUDIBIL]..
JASON KU: Subarborele acestui tip
nu este echilibrat pe înălțime, nu?
Tipul ăsta are 2.
Tipul ăsta are 1.
Deci, cum o reparăm?
PUBLIC: Rotiți.
JASON KU: Facem câteva rotații.
Acesta este de fapt
cazul prost care...
al treilea caz prost despre care am
vorbit ieri.
Dacă aș încerca să-l
rotesc la stânga pe tipul ăsta,
cum ar arăta?  Ar
pune 12 aici.  Ar
pune 10 aici.
Și 8 ar fi atașat la asta.
Acum este înălțimea echilibrată greșit
în cealaltă direcție, nu?
Nu e bine.
Așadar, modul de a gestiona
acest caz, în care
sunt grav înclinat spre
dreapta, dar subarborele meu drept
este înclinat spre stânga,
trebuie să fac o rotație aici,
rotație la dreapta și
apoi să fac o rotație.
Asta e formula.
Aici, facem mai întâi
o rotație la dreapta
la 10, ceea ce îmi dă ceva
care arată ca 8, 10.
Acum, evident, asta nu este
mai bine decât era înainte,
dar a fost un
pas intermediar ca să putem repara.
Rotim la dreapta aici și
apoi rotim la stânga aici.
Implicit este că am
roti-o la stânga aici,
dar pentru că aceasta a avut o
înclinație în direcția greșită,
trebuie să o rotesc
mai întâi la dreapta și apoi o putem face.
Așa că acum îi rotesc pe toți
tipii ăștia
și pun 12
aici jos, 8 aici, 10 aici.
Vedeți toată lumea că așa
arată o rotație?
BINE.
Este nevoie de puțin timp pentru a
vă concentra mintea în jurul a ceea ce
este transformarea, dar
sperăm că voi toți ați
urmat acea transformare.  A
existat puțină magie
în timp ce încercam să desenez.
Da?
PUBLIC: Încă nu
simt că acest copac este
echilibrat pe înălțime.
JASON KU: Nu este.
Buna observatie.
De ce este asta?
Acest lucru mai are înălțimea 3.
Care este înălțimea
acestui lucru?
1, nu?
Aceasta este înălțimea 1.
Și de fapt, când
făceam acea rotație,
trebuia să actualizez toate
aceste creșteri.
De ce măriri aveam cu
adevărat nevoie --
ce subarbori s-au
schimbat în timpul acelor lucruri?
Nu-mi amintesc cum
arăta chestia.
Cum arăta chestia?
10 avea 8 în subarborele său, așa că
subarborele său s-a schimbat cu siguranță.
Subarborele lui 8 s-a schimbat.
PUBLIC: [INAUDIBIL]
JASON KU: 12 nu s-au schimbat --
în cele din urmă.
PUBLIC: Acestea sunt
10 și 8 [INAUDIBIL].
JASON KU: OK.
Deci, există analiza de caz
care este în notele dvs. de curs
și a fost făcută în recitare.
Îți spune că
acești gen de subtress A, B, C, D,

cei care s-ar putea
schimba în aceste lucruri,
acei subarbori nu se schimbă.
Singurul subarbore care s-
a schimbat în timpul uneia
dintre aceste operațiuni de remediere, atunci când
faceți una sau două rotații,
sunt fie două noduri, fie
trei noduri
al căror subarbore s-a schimbat.
Aici, s-ar fi putut
întâmpla ca trei subarbori să se fi
schimbat.
Dar în cazul ușor, doar
două noduri-- x și y, cred,
în note-- s-
ar fi putut schimba.
Și atunci când fac asta, trebuie să
recalculez creșterile lor
din creșterile
copiilor lor,
dar este doar un
număr constant dintre acestea,
așa că le recalculez,
deoarece subarborele de sub mine
nu s-au schimbat.
BINE.
Deci avem o
nepotrivire de înălțime aici.
Da?
PUBLIC: [INAUDIBIL]
JASON KU: Corect.
Deci, inițial,
în imagine, 12
are o grămadă de lucruri
în subarborele său -
10 și 8, și tocmai am șters 7.
Deci subarborele lui s-
a schimbat cu siguranță.  Au
fost trei...
PUBLIC: [INAUDIBIL]
JASON KU: Oh, nu, îmi pare rău, a fost.
Da.
Deci aici, trei
subarbori de noduri s-au schimbat.
Dar asta este de fapt cel mai mult.
Îți arăt cel mai rău caz.
Doar trei noduri
posibile în realizarea
unuia dintre aceste
lucruri cu dublă rotație și-
ar fi putut schimba
subarborele.
Și așa trebuie doar să reparăm
creșterea acestor trei
lucruri.
În cazul ușor,
sunt doar două lucruri.  În
regulă.
Avem dezechilibrate.
Cum putem remedia asta?
Aș fi putut fi răutăcios.
Vreau să pot
roti la dreapta aici,
pentru a reechilibra, aș fi putut fi
răutăcios și le-am schimbat pe acestea două.
Dacă le-aș schimba pe cele
două, atunci ar
trebui să fac două rotații
pentru a remedia chestia asta,
pentru că cea din mijloc este
mai grea decât cea din stânga
față de ceea ce fac eu.
Dar nu sunt așa răutăcios, așa că o să
mă rotesc la dreapta.
Cum să fac asta?  Ei
bine, o rotire la dreapta
la 6 va
aduce toate
acestea sub 4
și va lipi acest subarboresc
drept copilul stâng al lui 6.
Are sens?
naiba.
Va fi distractiv să desenezi.
Am de gând să-l redesenez.
Are mai mult sens, nu?
4, 11, 3, 2, 1 și
apoi 6, 5, 9, 8, 12, 10.
Aceasta este rotația corectă la 6. Toată
lumea este bine cu asta?
Rotația--
x-ul meu este 6, y-ul meu este 4. Am
subarbori A, B, C.
Ceea ce fac este să
schimb care dintre x și y
este rădăcina aici.
Deci acum y este rădăcina, iar
subarborii B și C de aici acum devin
copiii lui x sub y.
Și observați că, sperăm,
prin tot acest proces,
traversarea mea în ordine nu s-a
schimbat.
A trebuit să ne actualizăm
creșterile pe parcurs,
dar este o constantă de fiecare
dată când urcăm în copac.
Și urcăm în copac doar de
un număr logaritmic de ori.
Da?
Da.
PUBLIC: [INAUDIBIL].
Deci, de fiecare dată când facem o
rotație, actualizați pur și simplu
mărirea
prin [INAUDIBLE]
înainte de a face orice altă rotație?
JASON KU: Exact.
PUBLIC: A doua parte.
Actualizarea
creșterii înseamnă doar
actualizarea numărului și a
înălțimii și doar a
proprietăților care rămân...
JASON KU: Da.
Practic, ceea ce am
făcut, am definit...
când am augmentat...
Profesorul Demaine
a definit ieri pentru tine
ce este o proprietate subarbore.
Însemna o proprietate pe
care o pot calcula doar
privind copiii mei --
măririle
copiilor mei, recursiv.
Așa că aici, în loc să
încerc să măresc sau să încerc
să mă gândesc, la nivel local, la ce
ar trebui să fie această augmentare,
voi arunca
vechea mea augmentare
și
o voi recalcula de la copiii mei,
pentru că acestea, recursiv,
ar fi bine să fie corecte.
Are sens?
Da?
PUBLIC: Așa că uităm doar
la modul în care funcționează rotația.
Întâmpin probleme cu
capul.
Deci, practic, schimbi
4 și 6, și astfel,
4 devine nodul părinte
și 6 devine nodul potrivit.
JASON KU: Voi
face acest desen.
Este doar ceva ce
trebuie să memorezi.
Acesta este x, B, C și A.
Puteți vedea acea poză?
PUBLIC: [INAUDIBIL]
JASON KU: Ce?
PUBLIC: [INAUDIBIL]
JASON KU: Da.
Este în notele tale.
Nu e mare lucru.
Dar dacă aveți
această structură,
în care x are un copil stâng -
și acești subarbori
pot fi gol sau nu.
Chiar nu contează.
Ceea ce pot face este că mă pot
muta de aici încolo...
are aceeași
ordine de traversare în ordine,
dar are o formă diferită.
Și în special,
înălțimile subcopacilor s-
au schimbat, ceea ce înseamnă că
ne poate ajuta să reechilibram copacul.
Și acesta este
scopul AVL.
Are sens?
PUBLIC: Asta este
rotația corectă?
JASON KU: Aceasta este...
aceasta este o rotație la dreapta.
Aceasta este o rotație la stânga.
Alte intrebari?
Da?
PUBLIC: [INAUDIBIL]
JASON KU: Pe măsură ce
merg pe copac,
fiecare nod pe care ar putea fi nevoit să-l
rezolv cu o reechilibrare,
dar acea reechilibrare face
cel mult două rotații
și există cel mult jurnal
n strămoși care  Am,
pentru că copacul meu a fost
echilibrat în înălțime la 2
bușteni sau ceva de genul ăsta.
Ceea ce înseamnă că,
la maxim, ar putea fi
nevoit să fac patru log n rotații,
pentru că fiecare ar putea
face două rotații.
Are sens?
Acum, în realitate, puteți demonstra
că, într-o operație de ștergere,
este posibil să trebuiască să
faceți un număr logaritmic
al acestor rotații în sus în arbore.
Acesta a fost cazul atât de rău.
Arborele original pe care ți l-am dat
se numește arbore Fibonacci.
Sunt puțini... este cel
mai mare arbore echilibrat pe înălțime pe care îl
puteți avea pe un
anumit număr de noduri.
Da, cele mai puține noduri
pentru o anumită înălțime.
Te poți gândi la asta oricum.
Și dacă generalizezi asta
la un lucru suficient de mare,
atunci acel lucru va
lua un număr logaritmic
de rotații în creștere.
Acum, de fapt,
cu o inserție,
poți dovedi... poți
trece prin analiza cazului.
O operație de inserare va
reechilibra întotdeauna arborele
după o
operație de reechilibrare, care
ar putea include două rotații.
Are sens?
Da?
PUBLIC: [INAUDIBIL]
JASON KU: Da.
Rotație corectă, tipul ăsta
devine un copil potrivit.
PUBLIC: Da.
Deci nu poți... există
anumite rotații pe care
nu le poți efectua, în funcție de
dacă ai avut un copil...
JASON KU: Da.
Dacă nu am avut un subarboresc din stânga,
nu pot efectua o rotație la dreapta
acolo.
O rotație la dreapta necesită
să am un copil stâng.
Deci, dacă o faci... și vei
vedea,
codul nostru
verifică pentru a se asigura că
ai un copil rămas.
Aceasta este o afirmație
că s-ar putea să
vrei să tragi înainte de a
face vreodată una dintre aceste rotații.
Altceva?
Da?
PUBLIC: Doar pentru a
reitera, deci o inserare
poate dura
cel mult două rotații [INAUDIBIL]?
JASON KU: Mhm.
Un număr constant de
rotații, iar ștergerea ar
putea dura un
număr logaritmic de rotații.
Acum, asta nu este ceva ce
trebuie să știi.
Nu este ceva ce
vă demonstrez aici.
Doar ceva
interesant.
Există
scheme de reechilibrare, ca în CRS.
Ei introduc un copac roșu-negru
pentru a introduce echilibrul.
Și acei copaci au de fapt
o legătură mai slabă pe--
nu este la fel de bine
echilibrat ca un arbore AVL.
Permite o înclinare mai mare decât 2.
Și pentru că este un fel de
restricție mai slabă,
ei scapă doar făcând un
număr constant de rotații -
că își pot permite asta
înainte de a repara copacul.
Dar un pic mai complicat.
PUBLIC: [INAUDIBIL]
JASON KU: Foarte frumos.
BINE.
Aveți întrebări despre asta?
OK, deci acum, aceasta este mai degrabă
o întrebare mecanică pe care o vei
primi în seturile tale de probleme.
Și acum trecem mai mult la
întrebările de tip teorie.
Acestea vor fi
întrebări de tip reducere.
BINE.
Prima problemă, Fick Nury.
Acesta este... cineva?
Nick Fury, nu?
Deci este o referință pentru Avengers.
Deci, practic, ceea ce se
întâmplă în chestia asta,
el are o listă de
supereroi, fiecare
are o părere dacă
ar trebui să se lupte cu Sanos.
Iar opinia lor poate
fi puternic pozitivă
sau puternic negativă.
Și, așadar, ceea ce
încearcă Fick să facă este să
găsească, dintre
răzbunatorii săi, care sunt
cei mai extremi
răzbunători, astfel
încât să poată vorbi cu ei.
Nu vrea să
vorbească cu toată lumea.
Vrea să vorbească cu un
număr logaritmic dintre ei.
BINE.
Este un fel de... orice.
Practic, avem o
situație clasificată
în care vi se oferă, ca un
depozit de date de intrare numai pentru citire
a acestor lucruri într-o matrice.
Și vreau să-i găsesc pe
cei de jurnal cu cele mai puternice
păreri.
Are sens?
Și vreau să o fac -
și prima problemă
este în timp liniar.  De
fapt, încă nu știi
cum să faci asta.
Veți ști cum să o faceți cu
materialul pe care îl acoperiți... ei
bine, ei vă învață
o modalitate de a o face în 046,
dar nu
vă vom duce acolo chiar acum.
Vă vom învăța o altă
modalitate de a face acest lucru marți,
care este prin grămezi binare.
Mulțile binare sunt un
lucru interesant.
Implementează un subset
al interfeței set.
Într-adevăr, doar... poți să te
bazezi pe niște x iterabil.
Adun o grămadă de lucruri.
Aceste articole au chei.
Este o structură de date cheie
în același mod.
Implementează ceea ce numim
o interfață de coadă prioritară.
Pot construi aceste lucruri.
Pot introduce lucruri, dar
nu voi face asta aici.
Tot ce am nevoie aici,
pentru această situație,
este un
tip de operație delete_superlative--
în acest caz, probabil max.
Delete_max.
Deci asta este ca... Am
o structură de date,
numesc aceste lucruri.
Are sens?
Da?
PUBLIC: Ce este
o coadă prioritară?
JASON KU: Da.
O coadă de prioritate este
în esență ceva care
implementează aceste două lucruri.
De fapt, există un al treilea
în care pot introduce un lucru nou,
dar nu o să am
nevoie de el acum.
Deci asta
este o coadă prioritară.
Și de fapt, un set...
acesta este un subset al
interfeței setului.
Dreapta?
Lucrul frumos despre un heap--
care, nu
vă voi arăta cum se face,
dar ce poate face un heap--
dacă aș avea ambele
operațiuni implementate
folosind un arbore AVL setat, cât timp mi-
ar lua aceste lucruri.  ?
Cât durează
construirea unui arbore AVL setat?
n log n, nu?
Pentru că, în esență,
primesc o ordine sortată
din chestia asta dacă
inserez aceste lucruri
pe rând --
sau aș putea să le sortez
și apoi să le așez
într-un copac în timp liniar,
așa cum ați văzut câteva  zile
în urmă în recitare.
Dar trebuie să le sortez
la un moment dat, nu?
Sunt cam--
Trebuie să iau cel
puțin n log n timp,
pentru că dacă voi putea
întoarce ordinea lor de traversare
în timp liniar și am
această limită inferioară a n log
n la sortare, am  cam nevoie pentru a
petrece n log n timp aici,
nu?
Și cât timp ar
dura acest delete_max?
PUBLIC: Este sortat, deci log n.
JASON KU: Log n, nu?
Deci este un arbore AVL setat.
Unde este maximul meu?
Este cel mai potrivit lucru.
Pot să merg în jos pe
chestia, să-l scot.
Poate că trebuie să mă reechilibrez.
Dar asta este o operațiune log n.
Este la fel ca
insert-last în subarborele meu.
Pentru un arbore AVL setat,
acesta este n log n.
Acesta este log n.
Acum, există o altă
structură de date care se descurcă mai bine
pentru una dintre aceste operațiuni.
Și același lucru pentru celălalt pe
care l-am învățat mai devreme.
Îți amintește cineva?
Setarea arborelui AVL nu
ne-a oferit de fapt
nimic peste o
matrice sortată într-o matrice dinamică.
Ceea ce a făcut a fost că avem un-- l-
am putea sorta în n log n timp
folosind sortarea de îmbinare sau ceva de genul
ăsta.
Și apoi am putea să
ieșim pe ultima de n ori.
Ar fi o amortizare...
Adică, dacă nu mi-ar
păsa să preiau
această dimensiune, aș putea face asta, în
cel mai rău caz, în timp constant.
Tocmai l-am citit pe
primul... pe ultimul.
Nu am nevoie să redimensionez
matricea, niciodată.
Pot să ignor asta.
Are sens?
BINE.
Dar este in regula.
Dacă aș avea o structură de date
care a implementat aceste două
operațiuni, poate cineva să-
mi spună un algoritm
pentru a genera liste fixe --
nu vă faceți griji cu privire la
timpul de rulare chiar acum -- dar care
folosește doar aceste două operațiuni?
Da?
PUBLIC: Așa că construim
această structură de date.
Este ordonat de la
cel mai mic la cel mai mare în
funcție de valoarea absolută a lui x.
JASON KU: Nu vă faceți griji
despre unde sunt
comandate lucrurile sau ceva de genul acesta.
Nu vă spun cum
sunt implementate aceste lucruri, nu?
Tot ce spun este că pot
accepta o grămadă din aceste lucruri
și pot elimina
maximul și îl pot returna.
BINE?
PUBLIC: Cred că
doar îl construim...
asigură-te că îl construiești
astfel încât nivelurile de opinie să fie
valoarea absolută a
nivelurilor de opinie, nu...
JASON KU: Sigur.
BINE.
Deci e un lucru frumos.
Ceea ce o să fac, după cum
spune colegul tău,
este că voi analiza
toate lucrurile din contribuția mea.  Îl
voi copia într-
un magazin de memorie care poate fi scris.
Acest lucru numai în citire
nu este relevant pentru această parte
a problemei.
Ceea ce o să fac este...
corect.
Îmi pare rău.
Mă gândesc la
setul de probleme pe care îl scriem.  O
amestec.
OK, așa că îl copiem în
noua noastră matrice de dimensiune liniară.
Dar în loc să pun
valorile lor acolo, voi
pune
valorile absolute ale valorilor lor.
Are sens?
Doar verific dacă este negativ.
Dacă este, pun
ceva pozitiv acolo.
BINE?
Și apoi pun acea
matrice în această versiune.
Am pus asta acolo.
Asta va dura ceva...
indiferent de timpul de construcție.
Și apoi pot
șterge max k ori.
Sau pot șterge max de câteva
ori, indiferent de multe lucruri de care
am nevoie.
Dreapta?
Dacă vreau să înregistrez cele mai înalte lucruri,
pot să fac acel jurnal de n ori,
nu?
Deci, pentru asta, dacă aș avea
o astfel de structură de date, aș
putea face acest lucru într-o singură
rulare a acestei operațiuni
și aș putea înregistra n rulări ale
acestei operațiuni.
Are sens?
Aș putea rezolva această
problemă reducând
la această structură de date.
Acum, pentru o matrice sortată
sau un arbore AVL setat,
această operație
deja mă omoară.
Este nevoie de n log n timp.
Lucrul frumos
despre un heap binar
este că face această
operație în timp liniar.  O sa
vezi asta marti.
Și face această
operațiune în log n time.
Care este timpul de rulare
dacă folosesc un heap binar
pentru a implementa această
structură de date?
Ordinea de n ori
jurnalul de ordine de n ori jurnalul n.
Cât de mare este log n pătrat--
log pătrat n-- în comparație cu n?
E mai mic, nu?
Deci, dacă adun cei doi
timpi de rulare împreună,
este încă liniar.
Așa rezolvi
prima problemă.
Nu a trebuit să vă spun
ce este un heap binar
sau cum a făcut ceea ce a făcut.
Tot ce trebuia să
vă spun este că a
făcut această operație
în timp liniar
și a făcut această
operație log n timp.  În
regulă.
Magia vă va fi arătată
marți.
Partea B spune, acum, să presupunem că
computerul lui Fick are
voie doar să scrie în,
cel mult, log n spațiu.
Bine.
Aceasta este o problemă aici.
Pentru că înainte, am copiat
întreaga matrice, am
filtrat-o și
apoi am făcut câteva operații.
Dar nici măcar nu ne-am putea
permite asta dacă
nu am putea stoca totul în
exterior în memorie inscriptabilă.
Deci nu putem face asta.
Deci, într-un anumit sens, acesta este un
mediu mai restrictiv.
Pot să fac mai puține lucruri.
Este mai puțin puternic decât în
situația mea anterioară, în care
aveam atât spațiu
cât mi-am dorit să folosesc.
Așa că are
sens că, poate,
nu am reușit să limităm timpul de funcționare pe
care îl aveam înainte.
Poate că trebuie să
sacrific ceva
pentru că mă aflu într-un
cadru de calcul mai restrâns.
Acum, acesta este ceva ce ai
putea rezolva cu grămezi binare,
dar nu trebuie.  O
puteți rezolva
cu arbori AVL setați.
Are cineva o idee
despre cum ai putea rezolva
asta folosind un arbore AVL setat?
Sunt limitat de numărul meu de...
spațiul meu este, cel mult, log n.
PUBLIC: Deci cât spațiu
ocupă un arbore AVL stabilit?
JASON KU: Corect.
Spațiu - există un
număr constant de pointeri
pentru fiecare dintre aceste noduri.
Și stochez în
notițe și spațiu.
Practic, fiecare structură de date pe care v-am
arătat-o ​​ocupă spațiu --
ordinea lucrurilor pe
care le stocăm.
Nu folosește spațiu suplimentar.  Ar
putea dura mai mult timp
pentru a face anumite lucruri,
dar spațiul ia
numărul de articole pe
care le stocăm plus,
poate, un factor constant.
Așa că am de gând să-mi trag intrarea
aici, pe care o pot citi doar--
nu pot scrie.
Îi dau un-- O să-i
spun doar
A. Deci aceasta este lista mea
cu toate opiniile Revenger.
Pot doar să o citesc.
Dar computerul meu poate scrie doar
în această cantitate logaritmică
de spațiu.
Ce pot pune in acel spatiu?
PUBLIC: Jurnalul [INAUDIBIL]?
JASON KU: Ei bine, cu siguranță pot
pune lucruri de jurnal acolo.
Deci, dacă mi se acordă
această restricție,
probabil că vreau să construiesc o
structură de date de acea dimensiune, care
să conțină acel
număr de lucruri.
Are sens?
Pentru că ce altceva ai de
gând să faci?
Asa ca ti-am dat o idee.
Poate am putea folosi
un set AVL aici.
Văd un logaritm în răspunsul meu.
Este foarte posibil să fi
sortat matrice
sau să fi setat lucruri AVL.
Aceste lucruri îmi dau un jurnal
undeva în timpul meu de rulare,
nu?  Este
atât de logic
încât aș putea avea,
poate, un arbore AVL setat aici.
De ce ar fi util un arbore AVL stabilit
pentru mine?
Da?
PUBLIC: Deoarece
este sortat și
nu aveți
ordinea de traversare,
puteți calcula
ordinea de traversare și puteți introduce [INAUDIBLE]??
JASON KU: Sigur.
Pot să fac toate aceste lucruri.
Dar în special,

mă va ajuta să găsesc
rapid unul mare, nu?
Dacă am un set de
lucruri, va fi --
și voi menține
această structură de date
adăugând lucruri
treptat la ea,
pot afla care
este cel mai mare --
sau cel mai mic --
destul de repede în jurnal  n timp.
Deci, dacă am log n
lucruri într-un copac aici,
care este înălțimea acelui lucru?
PUBLIC: [INAUDIBIL]
JASON KU: Jurnalul nr.
Asta pare familiar.
Deci ce îmi pot permite?
Îmi permit un număr liniar
de operațiuni de arbore AVL opt set
pe această structură de date.
OK, ai avut o întrebare?
PUBLIC: [INAUDIBIL]
JASON KU: OK, îmi pare rău.
Da?
PUBLIC: Pentru ca acesta
să fie un arbore AVL,
trebuie să fie un arbore BTS?
JASON KU: BTS--
BST-uri.
Deci, când vorbesc despre...
cuiva îi place K-Pop coreean.
BINE.
Deci BST-- dar în mod natural-- un
fel de limbaj pe
care probabil că ești
obișnuit să-l auzi
în alte contexte,
ceea ce ne referim, în această
clasă, este un arbore AVL setat.
Acum, uneori, ceea ce
oamenii se referă ca
arbore binar de căutare nu
are semantică de echilibru -
deci ceea ce am putea numi, în
această clasă, un arbore binar stabilit.
Dar într-adevăr, sunt utile
pentru că sunt echilibrate.
Deci, de
obicei, vom presupune doar
că aici vorbim despre
lucruri echilibrate.
Acum, un arbore AVL setat are această
semantică a arborelui de căutare binar
în care sunt ordonate cheile.
Aceste articole au chei
și sunt comandate.
Este o interfață setată.
Pe când v-am prezentat și
o
interfață de secvență, pentru care aceste
lucruri nici măcar nu au chei.
Cum aș putea stoca
acolo semantica setată?
Deci, aceasta este
distincția la care ne
referim când spunem arbore binar de căutare
față de, într-adevăr, un arbore AVL setat
față de [INAUDIBIL].
Da?
PUBLIC: Deci, dacă ne uităm la el
pentru a face un arbore AVL din asta,
ar însemna asta că, atunci când
facem un nod, îi spunem,
introducem
valoarea absolută a [INAUDIBLE]?
JASON KU: Bine, când
faci un arbore AVL stabilit,
trebuie să ne spui ce...
dacă depozitezi obiecte,
trebuie să-
mi spui care este cheia lor.
Doar stocați
niște numere,
ca ceea ce fac eu aici.
Acum, acesta nu este un arbore AVL setat.
Dar dacă stochez doar
numere,
trebuie să vă spun că articolele pe care le
stochez sunt cheile.
Și apoi urmează totul.
Dar dacă aveți un
obiect pe care
încercați să-l sortați, ca
studenții din această sală,
aveți o mulțime de proprietăți.
Vreau pe toți oamenii
cu număr de telefon...
poate vreau să vă scriu
numărul de telefon dintr-un motiv oarecare.
Asta mă va ajuta să
aflu unde locuiești?
Nu... asta
devine puțin...
Nu vreau să merg acolo.
Dar dacă vă dau
un arbore AVL setat,
trebuie să vă spun
pe ce este introdus.
Dacă vă dau un
arbore AVL de secvență,
este evident care va fi
ordinea mea de traversare
pentru că
vă dau o secvență.
Asta a fost intrarea.
Are sens?
În regulă, deci am acest
arbore AVL setat cu dimensiunea jurnalului n.  Cu
ce ​​ar trebui să fie tastată?
PUBLIC: Valoare absolută.
JASON KU:
Valoarea absolută a preferinței lor
sau a opiniei lor.
Nu-mi amintesc
cum se numește asta.
Dar ce log n lucruri pun
aici?  Nu
știu.
Nu știu nimic
despre aceste lucruri.
Ce îl face pe unul
mai bun decât altul?  Să
punem doar
primul log n lucruri.
Are sens?  În
regulă.
Ce mi-ar putea spune asta?
Acum, am pus chestia asta în el.
Cât timp a durat?
PUBLIC: [INAUDIBIL]
JASON KU: Înregistrează de n ori
Log n timp, nu?
Dar asta este mult mai puțin
decât timpul nostru de funcționare pe
care îl căutăm,
așa că nu-mi pasă cu adevărat.
Adică, vreau să
spui cât de mult a durat,
dar pentru scopurile mele,
știu că este
mai mic decât
timpul de funcționare pe care îl caut.
Și am făcut operația aceea o dată.
Nu prea îmi pasă
de asta.
Da?
PUBLIC: Cum ați obținut
jurnalul de n ori jurnalul n?
JASON KU: Pentru că
numărul de lucruri pe care le
stochez în acest
lucru este jurnalul n.
Și așadar, dacă modelul se potrivește cu
timpul de construire al unui arbore AVL
și bag log n acolo,
atunci este log n ori log n.
BINE.
PUBLIC: Deci asta este
doar pentru o iterație?
JASON KU: Ei bine, chiar acum,
tocmai am construit chestia asta.
Poate... L-am construit doar o dată.
Afirm, de asemenea, că poate
nu trebuie să-l construiesc din nou.
Ce aș putea... Deci, până
acum, știu... Nu mi-am
filtrat
deloc datele.
Doar stochez aceste lucruri
în ordine sortată într-un fel.
Ce pot face pentru a
putea începe să procesez
restul datelor?
Da?
PUBLIC: [INAUDIBIL] încearcă
să defilezi prin lista A
și încearcă să găsești pe cineva
care este mai mare decât...
încearcă să păstrezi
maximul [INAUDIBIL]..
JASON KU: Mătură-l pe tipul ăsta să
insereze lucruri
și să mențină mereu...
dacă o fac  asta și
continui să lipesc lucrurile
și voi avea așa
ceva la sfârșit.
Și acum pot doar să citesc cele
mai mari k lucruri.
Cu toate acestea, pe măsură ce introduc
lucruri aici,
treaba mea crește.
PUBLIC: Ei bine,
ștergeți-l pe cel mai mic.
JASON KU: Oh,
șterge lucrurile mici.
Imi place ideea asta.
PUBLIC: Deci,
în principiu, înlocuiți-l.
JASON KU: Da,
practic înlocuiește-l.
Dreapta.
Ce am de gând să fac...
iată o propunere.  O să-l
luăm pe
următorul tip, să-l bagăm.
Minunat.
De care nu-
mi pasă acum?  Cel
mai mic de acolo.
Așa că dă-l afară pe cel mai mic.
Acum, acesta pe care l-
am blocat în luna mai.
Fii cel mai mic.
Deci am cam trecut
prin chestia asta,
dar cât timp mi-a luat asta?
Mi-a luat
înălțimea acestui copac.
Care este înălțimea acestui copac?
PUBLIC: [INAUDIBIL]
JASON KU: Jurnalul nr.
Așa că am pus unul,
am scos unul.
E cel mai mic, nu?
Și continui să fac asta până la
capăt.
Cât timp mi-a luat asta?
JASON KU: [INAUDIBIL]
JASON KU: Da.
Procesarea n minus log n
lucruri, care este practic n.
Și fiecare dintre aceste
operațiuni mi-a luat
înălțimea timpului de copac.
Asta îmi oferă
timpul de funcționare pe care îl
căutăm, n log log n.
sens?
PUBLIC: Amintește asta
de tehnica ferestrei glisante?
JASON KU: Da.
Este un fel de
tehnică a ferestrei glisante.  Este
posibil să fi
folosit unul recent.
BINE.
Toți sunt de acord cu asta?
Da?
PUBLIC: Îmi puteți
aminti doar de contextul despre
care vorbim este
jurnalul n, cum ar fi arborele și unde--
JASON KU: Deci acest lucru--
dimensiunea acestui lucru
este jurnalul n?
PUBLIC: Da.
JASON KU: Adică... îmi pare rău, log n.
Și înălțimea acestui
lucru este un buștean de dimensiune.
PUBLIC: Îmi pare rău, în raport
cu dimensiunea noastră mică a buștenilor
[INAUDIBIL]
Buștenii mici n copaci, sau--
JASON KU: Nu, așa-- îmi pare rău.
Iau chestiile astea-- nu
există nicio
structură de date intermediară aici--
lipesc toate
aceste lucruri în setul AVL.
Da?
PUBLIC: [INAUDIBIL]
JASON KU: Într-un singur
set AVL cu dimensiunea jurnalului n.
Bag un tip,
scot cel mai rău tip afară.
Trecând prin toate lucrurile.
Trebuie să mă asigur că,
atunci când îl bag,
țin evidența
ce Revenger este
și că iau
valoarea absolută
și toate acele
lucruri neplăcute.
Dar asta este ideea de bază.  Doar
iau asta,
bag fereastra înăuntru, bag
ceva,
scot ceva
care poate sau nu-- probabil că
nu este-- același lucru.
Și la sfârșitul
acestei proceduri,
invariantul pe care îl
mențin aici
este că treaba mea are întotdeauna cele
mai mari k opinii dintre cele pe care le-
am procesat până acum.
Acest lucru este evident adevărat
la început,
când construiesc chestia asta.
Și când ajung la final, am
procesat toate lucrurile,
iar acesta are dimensiunea log n, și
astfel am log n cea mai mare-- cea
mai mare-- opinii extremiste.
Și apoi pot doar să fac o
traversare în ordine
a acestui lucru și să mă întorc.
Are sens?
Și am folosit doar
spațiul logaritmic.
Da?
PUBLIC: Stai, nu înțeleg.
Toate opiniile sunt
în arborele AVL?
JASON KU: Toate opiniile sunt
în arborele AVL?
Toate aceste opinii
sunt în arborele AVL.
Și la un moment dat, voi
introduce fiecare părere
în acest arbore AVL.
Dar le voi elimina pe
cele care nu-mi pasă pe
măsură ce merg.
Are sens?
Întotdeauna păstrez
invarianții
că acest lucru, înainte de a
insera ceva,
are exact n elemente de log
în el, și apoi
mențin acel invariant
introducând unul, scoțând unul
.
PUBLIC: Oh, OK, deci pe care îl
ștergi?
JASON KU: Întotdeauna
min, pentru că le
vreau pe cele mai mari.
PUBLIC: Și minul
valorii absolute.
JASON KU: Da.
Mă refer la
valoarea absolută a acestor opinii.
Da?
PUBLIC: [INAUDIBIL]?
JASON KU: Timp total de rulare aici?
Este contabilitate.
Mi-a luat log de n
ori log log n timp
pentru a construi această
structură de date la început,
plus de n ori log log n.
Am făcut, practic, n operații -
asimptotic, n operații.  În
acest fel, sunt de fapt
n minus log n operațiuni.
Și fiecare dintre acele
operațiuni de arbore -- a
face o inserare, o ștergere --
fiecare dintre acestea a luat
înălțimea timpului de arbore.
Și așa este asta.
Bun?
Da?
PUBLIC: Dacă, în loc de unul,
doar inserăm și ștergem,
poți face o comparație și apoi...
JASON KU:
Inserarea și ștergerea
unui arbore AVL setat
face de fapt comparații
în structurile sale de date.
PUBLIC:
Comparați doar cu min.
Și apoi...
JASON KU: Sigur,
ai putea face asta.
Aș putea face altfel.
Aș putea elimina
cel mai mic element de aici,
pentru început, nu?
Și apoi
îl compar cu tipul ăsta,
și apoi, oricare este
mai mare, îl bag înapoi.
Același lucru.
Doar, fac mai
întâi ștergerea și apoi inserarea
sau fac
mai întâi inserarea și apoi ștergerea?
Alte intrebari?  O
mulțime de întrebări.  În
regulă.  Ei
bine, probabil că va
trebui să omit o problemă.
Vom trece la CS--
nu, SCLR.
Care este referința aici?
PUBLIC: [INAUDIBIL]
JASON KU: Da, CLRS.
Aceștia sunt patru cadre universitare
care au scris un manual popular
în informatică.
Acesta este același gen
de lucru.  Au
găsit primele ediții și
vor să le scoată la licitație.
Oamenii pot accesa
site-ul lor.
Au un ID de ofertant.
Este un identificator unic.
Și pot face o licitație
pentru una dintre aceste cărți.
Și o pot schimba
în timpul perioadei de licitație,
dar la sfârșitul
perioadei de licitație,
cadrele universitare vor
să știe cine--
care este
venitul așteptat pe care îl voi
obține prin vânzarea celor
k ofertanți mai mari?
Are sens?
Da?
BINE.
Rețineți că, înainte de a construi
această structură de date,
știu ce este k.
k este un lucru fix.
Deoarece timpul meu de rulare al acestui
venit de obținere depinde de acest k,
nu este o intrare
pentru acea operațiune.
Deci k este un fel de nu
știu ce este, a priori.  Ar
putea fi n peste 2.
Ar putea fi log n.
Ar putea fi 1.
Dar structura de date pe care o
construiesc trebuie
să satisfacă aceste
proprietăți de timp de rulare,
indiferent de alegerea k pe
care mi-au spus-o academicienii.
Are sens?
Ceea ce trebuie să fac este că, în măsura în care trece
timpul,
oamenii fac oferte noi
și își actualizează ofertele.
Și aceste actualizări
pot dura timp de log n.
Dar de îndată ce
închid fereastra,
vreau să pot spune,
în timp constant, care
sunt k ofertanți.
Aveți idei despre cum să faceți asta?
Care sunt operațiunile pe
care trebuie să le fac?
Trebuie să pot
face o nouă ofertă.
Asociate cu un ofertant
este o idee și o ofertă,
care este, de asemenea, un număr întreg --
câți dolari voi
plăti pentru această carte.
Actualizați oferta.
Într-un anumit sens, trebuie să aflu
dacă acea persoană a plasat
oferta înainte, în
structura mea de date.
Deci, la un moment dat, voi avea
nevoie de o găsire a ID-ului ofertantului.
Asta pare posibil?
Așa că aș dori să am
un fel de dicționar
despre ID-urile ofertanților.
Când spun că vreau să am
un dicționar pe ceva,
nu
vă specific încă
cum voi
implementa acel dicționar.
Care sunt opțiunile mele obișnuite?
O masă hash.
Dar dacă am nevoie de
timp în cel mai rău caz?
Un arbore AVL stabilit, nu?
Acesta va fi punctul tău de plecare
pentru un dicționar,
pentru că asta
îmi va da timp de log n pentru a găsi lucruri
printr-o cheie.
Este singurul lucru -- ei
bine, cu excepția unui sortat --
puteți folosi și
o matrice sortată,
dar aceasta
nu va fi dinamică.
Și aici, actualizăm tot timpul
cine se află în structura mea de date
.
Oamenii intră
și fac oferte --
oameni noi care fac oferte.
Așa că setul meu de lucruri la
care îmi pasă
se schimbă tot timpul.
Deci, probabil că asta
mă va îndepărta
de matricele sortate,
pentru că nu sunt
bune cu operațiunile dinamice.
Deci, voi avea nevoie de un fel
de dicționar despre ID-urile ofertanților,
dar va trebui, de asemenea,
să mențin suma celor k
cei mai mari ofertanți.
Are sens?
Și astfel, într-un anumit
sens, trebuie să țin
evidența unei noțiuni ordonate despre
ofertanți, ofertele, care
sunt în structura mea de date.
Are sens?
Deci ordinea va fi
importantă pentru oferte.
Voi avea nevoie de o
căutare a ID-ului ofertantului.
Și cam atât, nu?
BINE.
Da?
PUBLIC: Doar verific.
Deci, dacă ceva
care este cel mai rău caz
rulează în cel mai rău caz, se
așteaptă [INAUDIBIL]..
JASON KU: Da.
Corect.
Da.
Este o observație foarte bună.
Dacă rulează în cel mai rău
caz,
rulează și la momentul așteptat, nu?
Pentru că, în esență,
nu există o randomizare despre
care vorbesc aici.
PUBLIC: [INAUDIBIL]?
JASON KU: Da.
Și așa că există o noțiune mai puternică pe
care vrem să o specificați, și
anume că, de fapt, nu
există nicio randomizare aici.
Nu folosim o tabelă hash.
În această clasă, într-adevăr, aceasta este
singura situație în care
asta va fi o problemă.
Dar dacă este, ceea ce spune această problemă
pentru fiecare [INAUDIBIL],
dacă timpul dvs. de rulare este
așteptat și/sau amortizat în cel mai rău caz
, ceea ce încercăm cu adevărat să
vă facem să spuneți este
care este --
evaluați
timpul de rulare  a algoritmului dvs.
cu calificările corespunzătoare.
Dacă a fost nevoie de cel mai rău
caz, vreau
să spui că a fost nevoie de cel mai rău caz.
Dacă a fost nevoie... dacă ai
folosit o tabelă hash,
vreau să spui așteptat.
Și dacă aceste operațiuni au
fost uneori foarte proaste,
dar în medie, sunt foarte
bune, dacă le-am făcut multe,
se amortiza.
Sau dacă m-aș reduce la
utilizarea unei matrice dinamice
sau dacă m-aș reduce la
utilizarea unui tabel hash,
acele operațiuni dinamice
ar fi în continuare amortizate.
BINE.
Cele dinamice.
Lucrul frumos despre
structurile de date legate
este că operațiunile dinamice
nu sunt amortizate.
Deci vom
putea obține unul.
Acum, pentru această problemă, putem
obține limite în cel mai rău caz,
așa că vom încerca asta.  De
asemenea, puteți face acest lucru în mod așteptat
folosind niște tabele hash
pentru acel dicționar.
Când abordați
o problemă de structuri de date
din această clasă,
doriți să-mi spuneți mai

întâi ce stocați.
Spune-mi ce ar trebui
să fie în acele lucruri --
niște invariante pe
această structură de date
pentru a mă asigura că, atunci când
fac interogări mai târziu,
aceste lucruri
sunt menținute,
astfel încât, dacă mențin
o matrice sortată,
și eu sunt  susținând o
operațiune pentru a găsi maximul, ar
fi mai bine--
orice fac
acestei structuri de date
ar fi mai bine să mențin
invarianții
că aceste lucruri
sunt în ordine sortată
și ultimul lucru
are elementul maxim.
Pentru că chestia mea cu randamentul maxim se va

uita acolo și va returna asta.
Are sens?
Deci vrei să-mi spui
ce este stocat
într-un moment generic în timpul structurii
tale de date
, ce este
menținut - astfel
încât, atunci când accept
operația dinamică sau o interogare,
într-o operațiune dinamică, în care
inserez  și conduc
lucrurile din acest lucru,
trebuie să mă asigur că
mențin acele invariante.
Și când interog,
mă pot baza de fapt
pe acele invariante
pentru a răspunde la întrebarea mea.
Are sens?
Deci, pentru această
problemă-- acesta este 4-3.
Vreo idee?
Am două tipuri de chei cu care s-
ar putea să am de-a face.
Unul este un ID de ofertă și
unul este o ofertă, nu?
Deci, cum aș putea, dacă am două
chei pe care aș dori,
poate, să le comand pe una
și să caut pe alta,
câte structuri de date
crezi că voi folosi?
PUBLIC: Două.
JASON KU: Doi.
Este o presupunere destul de bună.
Deci, unul dintre ei... să
ghicem, nu?
Trebuie să pot
căuta ofertele,
așa că haideți să stocăm acești ofertanți
într-un fel de dicționar
care va putea
căuta rapid acele lucruri.
Deci două structuri de date.
Unul este un dicționar
introdus pe ID-ul ofertantului.
Ce altceva o să vreau?  Care-i
treaba?
Pe de altă parte, un
dicționar stocat pe oferte?
Este un dicționar
ceea ce vreau aici?
PUBLIC: [INAUDIBIL]
configurați arborele AVL [INAUDIBIL]?
JASON KU: Vreau să
mențin ordinea cumva.
Pentru că vreau să
păstrez cele mai mari
lucruri pe care le-am văzut până acum.
Chiar acum, dacă am... la
un moment dat,
ce se va întâmpla?
Dacă mențin cel
mai mare k în orice moment,
este posibil ca
unul dintre acei ofertanți
să-și scadă oferta, astfel încât
să nu mai fie în cea mai mare.  De
asemenea, va trebui să
țin evidența celorlalți tipi
pentru a vedea pe cine ar trebui să adaug înapoi
în acel set, de exemplu.
Iată o idee.
Voi păstra nu doar o
altă structură de date, ci alte două
structuri de date.
Poate că acesta este un salt.
Nu trebuie să faci asta.
Există o modalitate de a face asta
doar cu un altul.
Dar voi mai păstra două.
Unul este un fel de--
o structură de date pentru a
stoca ofertanții cu a--
stocarea celor k ofertanți cei mai mari
și o structură de date
pentru a stoca cei n minus
k ofertanți.
Are sens?
Asta separă problema mea
destul de bine, nu?
De fiecare dată când cineva
interacționează cu această
structură de date, pot
verifica dacă este
mai mare decât cel
mai mic lucru de aici.
Dacă este, pot face același
tip de truc pe care l-am făcut înainte.
Pot să-l scot și să-l înfig pe
cel nou acolo.
Și mergem...
dar l-am eliminat.
Trebuie să întrețin
această proprietate.
Așa că îl bag aici.  Mai
este un caz.
Care este celălalt caz?
Este mai mic.
În acest caz,
nu fac nimic
cu această structură de date și
doar o lipesc aici.
Are sens?
Care sunt operațiunile pe care

trebuie să le mențină aceste structuri de date?
Găsirea minimului sau
maximului acestor două seturi.
Are sens?
De fapt, într-adevăr,
unde sunt acele operațiuni?
nu le mai am.
Dar acestea erau
operațiunile prioritare la coadă.
Aveau delete_max--
și, de asemenea, insert--
au fost lucruri pe care le-a făcut bine.
Așadar, orice
coadă de prioritate, orice
poate face față cu maxime
și minusuri, este bună.
Și care este o
structură de date pe care o cunoașteți,
care poate face față cu maxime
și minusuri destul de eficient?
Setul AVL, nu?
Deci, în loc de
structura de date aici, voi
spune, setați AVL.
Și, evident, va
fi aplaudat prin licitație.
Pentru că asta e lucrul pe care o să
vreau să găsesc
maxime și minute peste.  Toată
lumea urmează
logica
de ce întrețin
aceste lucruri?
Acesta este nivelul
invarianților
pe care vreau să-l mențin,
pentru că,
de exemplu, când mă duc să fac această
interogare, să obțin venituri,
pot doar să parcurg și să
însumez toate aceste lucruri.
Oh, așteptați.
Cât timp am la dispoziție?
Am k timp?
Nu, nu am timp.
Așa că nu... nu îmi permit
să rezumam toate aceste lucruri
la sfârșitul firului meu.
Trebuie să ți-l returnez
în timp constant.
Vreo idee?
Da, doar calculează...
actualizează o sumă.
Împreună cu această
structură de date,
voi păstra un al
patrulea lucru, care
este doar totalul sumelor licitate.
O să-i spun t.
Și asta e ceva pe care îl
mențin.  Face
parte din structura mea de date.  Vă
puteți gândi la asta
ca, am sporit
chestia asta cu un număr.
Și scopul creșterii
acestui lucru cu un număr
este că pot doar...
dacă am nevoie să știu care
este totalul acestor lucruri,
pot doar să mă uit la acel număr.
Are sens?  În
regulă.
Așa că acum, cred,
aproape am terminat.
Practic am terminat, nu?
Cum facem asta?
Cineva mi-a spus
cum aș obține venituri
cu această structură de date.
Practic, ți-am spus.
Uită-te la acest număr.
Returneaza-l.
Pentru că acesta este invariantul pe
care l-am menținut pe structura mea de date
.
Mă bazez pe acest invariant.
Acum, ar fi bine să mă
asigur că acest lucru este bun
când fac operațiuni dinamice.
Mă asigur că o întrețin.
Dar dacă eu, prin inducție, mă asigur
că toate aceste lucruri sunt bune
și când fac o
operație dinamică, toate acele lucruri
sunt menținute,
atunci sunt bine.
Așa că obținerea de venituri, după ce am făcut toată
această muncă suplimentară, este foarte ușor.
Mă uit doar la acest
număr și apoi revin.
Când notăm o
problemă cu structurile de date,
de obicei, vă acordăm câteva puncte,
mai întâi, pentru configurarea structurii dvs. de date
, separat
de operații,
apoi vă acordăm
puncte pentru fiecare operație cu
care ați rezolvat cu succes
și apoi
câteva puncte pentru  corectitudinea
si timpul de rulare.
Da, ai avut o întrebare?
PUBLIC: Deci ar
fi un lucru total pe
care îl actualizăm
ori de câte ori ne încurcăm
cu arborele cu cel mai mare ofertant
și apoi cu n minus k arborele ofertant?
JASON KU: Îmi pare rău,
spune asta din nou?
PUBLIC: Tratăm
totalul cu o creștere pe
care o actualizăm de fiecare
dată când facem ceva?
JASON KU: Da.
Da.
Deci este doar un număr.
Nu este chiar
o structură de date,
este doar un număr pe care îl
stochez în baza de date.  În
regulă.
Cum implementez
o nouă operațiune de licitare?
Da?
PUBLIC: Am o întrebare.
Putem presupune că și
ofertele vor fi unice?
JASON KU: Puteți presupune
că ofertele pot fi unice?
Nu.
Acesta este de fapt ceva care
este o observație cu adevărat utilă.
Am vorbit despre
structurile de date stabilite
ca necesită chei unice.
Cum pot face față
cheilor care nu sunt unice?  De
fapt, se
dovedește că, tabelul hash,
este foarte important
ca acestea să fie chei unice.
Pentru că trebuie să verific
dacă este acolo.
Caut cheia aceea unică.
Când îl găsesc,
trebuie să mă întorc.
Dacă aș avea mai multe
lucruri cu acea cheie, s-
ar putea să nu-l returnez pe
cel pe care îl caut.
Nici măcar nu are sens.
Dar puteți generaliza
infrastructura setului
pentru a face față cu mai multe seturi.
Cum pot face acest lucru?  Ei
bine, cu fiecare cheie...
din nou, stochez chei unice.
Cu fiecare cheie, o pot lega
la un set de secvențe de structură
sau la orice altă structură de date.
Și ceea ce voi face este, voi face...
orice
are cheia aceea, o voi
înfige
în acea structură de date.
Deci, în loc să stochez
un articol acolo,
am posibilitatea de a
stoca multe lucruri acolo.
Acum, trebuie să schimb
semantica aici.
Dacă spun, găsiți pe această
cheie, ei bine, acum, aș putea spune, voi
returna toate
lucrurile cu acea cheie,
sau voi stoca
ceva cu acea cheie.
Dar înțelegi ideea.
Tot ce trebuie să fac este să-l mapez
pe o altă structură de date
pentru a menține [INAUDIBIL].
Ca, poate, vreau toate
lucrurile cu acea cheie.
Vreau să-l găsesc pe cel
cu această altă cheie.
Deci, poate mă conectez la
o structură de date setată
care poate căuta și
alte lucruri, nu?
Dar ideea aici
este că menținem
această proprietate cheie a unicității.
Trebuie să-mi relaxez
semantica, astfel încât să
stochez mai multe lucruri
în acea locație cheie.
Are sens?
Da?
PUBLIC: De ce
contează dacă arborele AVL setat
are chei unice sau nu?
JASON KU: Va conta
aici pentru că am oferte.
Și ofertele ar putea
fi neunice.
Două persoane ar putea
avea aceeași ofertă.
Și, după definiția noastră
a unei structuri de date set,
trebuia să aibă chei unice.
Deci, dacă m-am blocat în toate
aceste lucruri introduse de ofertant,
ai o problemă.
Acum, de fapt,
putem scăpa
de asta prin stocarea,
practic, a unei
liste legate de toate lucrurile cu
acea cheie și ne-ar fi bine.
Și apoi, ori de câte ori vreau să
returnez unul, aș putea să o fac.
Dar, de fapt, un
arbore binar
este de fapt suficient de flexibil încât,
în majoritatea implementărilor,
puteți doar să stocați o
grămadă de acele lucruri.
Dar, de fapt,
timpul nostru de rulare merge mai rău.
Ce înseamnă a
găsi-next în secvența mea?
Ce înseamnă să
returnezi următorul lucru mai mare
deasupra acestei chei?
Nu prea are
sens, pentru că
ar putea fi mai multe.  Pe care il
intorc?
Și dacă fac în mod repetat find-next
pe această structură de date, s-
ar putea să nu parcurg
toate lucrurile.
Așa că unele lucruri se
defectează în interfața noastră.
Așa că aș prefera să utilizați
chei unice în acest tip de situație.
Marțea viitoare, cred că,
cu grămezi binare, ne
vom ocupa de chei neunice.  Asta e
bine.
Dar dacă vei folosi
chei non-unice aici,
trebuie doar să
fii puțin
atent la semantică.
Da?
PUBLIC: [INAUDIBIL]?
JASON KU: Veți
obține același
timp de rulare - trebuie să
schimbați semantica
a ceea ce înțelegeți prin
„găsiți ceva”.
Vreau doar să returnez
orice cu această cheie.
PUBLIC: Ce se întâmplă dacă
totul are aceeași cheie.
Apoi...
JASON KU: Atunci este
nevoie de timp constant.
Eu doar returnez primul lucru.
Adică, acestea sunt
cazuri speciale la care
trebuie să te gândești, nu?
Nu-mi place să mă
gândesc la ei.
Așa că îmi place să
am chei unice.
Și dacă vreau o situație în
care am chei care nu sunt unice,
practic voi
pune coliziuni la acea cheie
într-o nouă structură de date.
Îmi este mai ușor
să mă despart
în mintea mea de ceea ce se întâmplă.
Pentru că, pentru toți
timpii de funcționare pe care i-am propus,
există definiții foarte puternice
pentru cheia unică.
Când aveți de-a face
cu un set multiplu,
este puțin
mai răspândit.
Alte intrebari?
Chiar trebuie să
mergem mai departe aici, nu?
Dicţionar keyed on bidder.
Încă nu am implementat
operațiuni dinamice.
Ofertă nouă.
Ce trebuie să fac?
De ce voi avea
nevoie pentru actualizarea mea?


În fiecare dintre aceste
structuri de date, va trebui să găsesc
unde este ofertantul respectiv.
Și dacă am un
lucru introdus pe oferta lor,
interfața nu
îmi spune care era vechea lor ofertă.
Îmi spune doar care
este ID-ul de ofertant.
Deci, dacă aș avea doar ID-ul ofertantului
și noua lor sumă licitată, cum naiba o să
aflu
care dintre aceste date-- unde sunt
în aceste
structuri de date?
Ceea ce pot face este, pot
stoca, în acest dicționar -- pe
care îl pot căuta într-o
anumită perioadă de timp --
un indicator spre locul în care
există în aceste lucruri.
Are sens?
Aceasta se numește cross-linking.  Este
posibil să fi făcut asta
puțin în
setul de probleme 2 sau ceva de genul ăsta.
Da?
PUBLIC: Restabilirea unui
indicator către un anumit ofertant?
JASON KU: Da, exact.
Invarianta pe care o
avem este că toți
ofertanții pe care i-am
procesat până acum
există în aceste structuri de date -
într-una dintre aceste
structuri de date -
pentru că am folosit
un arbore AVL setat.
În special,
există într-un nod al uneia
dintre aceste structuri de date.
Ceea ce putem face
este, în acest lucru, să
menținem indicatorii care mapează
fiecare dintre ID-urile ofertantului
la locația lor în
aceste structuri de date.
Și de ce va
fi un lucru util?  Să
zicem că cartografiaz acest dicționar.
Ce aș putea folosi
pentru acest dicționar
pentru a obține
timpul de funcționare pe care îl căutăm?
Aș putea folosi un
tabel hash sau un set AVL.
Dacă este un AVL setat, voi
obține timp logaritmic, în cel mai rău
caz.
Cu un tabel hash,
primesc timp constant,
dar este de așteptat.
Deci ar putea fi
timp liniar în cel mai rău caz.
Vom folosi un
arbore AVL setat, pentru că asta
facem chiar acum.
Și asta
ne va oferi cel mai rău caz.
Ceea ce voi face este că, pentru
fiecare dintre aceste lucruri,
voi stoca acel indicator.
Ceea ce o să
fac este, mai întâi, să
fac acea
operație pe care am avut-o.
Dacă adaug un nou ofertant,
voi lua D și B--
aceste două valori, acel
obiect, acel obiect ofertant
sau orice altceva-- Mă
voi uita la cel
mai mic lucru din această
structură de date  , vezi dacă oferta sa
este mai mare decât lucrul pe care îl
introduc.
Dacă este, atunci nu voi
atinge această structură de date.
O să-l
introduc aici.
Și acum, după ce
inserez aici,
știu exact unde se află
în structura de date.
Tocmai l-am introdus.
Așa că acum, ținând
asta în mână--
nodul-- pot să mă duc și să
introduc acel ofertant aici
cu ID-ul ofertei.
Deci va
dura timp de logaritm.
Și acum pot stoca, cu
acel nod, indicatorul meu
către această structură de date.
Are sens?
Și în celălalt caz, eu
cam același lucru.
Dacă este mai mare decât cel mai mic
lucru de aici, scot acel lucru mai mic
afară, îl bag acolo
și îl bag pe noul meu tip aici,
încrucișând fiecare dintre acești
indicatori pe parcurs.
Are sens, sperăm?
Cam?
Cam?
BINE.
Și pentru actualizare, foarte asemănătoare.
Dacă vreau să actualizez
un anumit ofertant,
mă uit în această
structură de date, găsesc ofertantul,
parcurg acel
indicator către oriunde
se află în unul dintre acești
arbori AVL, nu?
Dacă este în acesta,
îl scot doar din arbore,
sau îl scot din
arbore și apoi
îl reintroduc cu
oricare ar fi noua ofertă.
Și dacă este în
acesta, din nou,
îl scot din arbore,
reintroduc oricare
dintre aceste lucruri,
și atunci ar putea
fi nevoit să schimb un
număr constant de lucruri înainte
și înapoi aici pentru a menține
că acesta are k cel mai mare.  .
Și când fac acele
operații dinamice,
elimin întotdeauna
un număr constant
de noduri din fiecare dintre acești
copaci și adaug înapoi
un număr constant de lucruri.
Și în timp ce fac asta, mă
asigur că actualizez acest total
pe măsură ce merg.
Acest total a fost suma
tuturor ofertelor de aici.
Și dacă introduc o
nouă ofertă aici,
trebuie să adaug la acel total.
Și dacă elimin unul, trebuie să
elimin din acel total.
Dar, din nou, este un
număr constant de lucruri pe care le
mut în și din
aceste structuri de date
și, astfel, le pot actualiza
în timp constant.
Are sens?
Acum, căutarea aici și
inserarea și ștergerea
aici, fiecare a luat
timp logaritmic, în cel mai rău caz.
Dar am făcut un
număr constant de ele.
Deci din nou, timp logaritm.
Are sens?
Aceasta este, în esență,
această problemă.
E greu, nu?
Sunt o mulțime de
părți mobile aici.
Dar dacă doar o
despărțiți și să-mi descrii,
cum ar fi, faci o
treabă bună în această parte,
descrie-mi bine ce
are structura ta de date, atunci
acele descrieri
ale acelor algoritmi
pot fi destul de scurte, de fapt.
În aceasta, îmi spuneți
aceste trei structuri de date, îmi
spuneți că acest tip a
mapat la locația sa
și aceste lucruri, eu îl
întrețin pe acest tip,
apoi mențineți acele
lucruri cu operații dinamice
și apoi utilizați acele lucruri
pentru operațiuni de interogare.  .
Are sens?
Wow, mai avem 10 minute?
O să fac pe scurt
4-4 pentru tine.
Lista receptorilor.
Avem un antrenor.  Are
o grămadă de
jucători de fotbal...
receptori.
Și dorind să
înceapă în echipa ei,
un număr de jucători care
au cea mai mare performanță.
Și prin performanță, ne
referim la numărul mediu
de puncte pe care le-au jucat
în jocurile pe care le-
au conectat în sistemul lor.
Dar, de fapt,
datele lor sunt incomplete.
Ei nu știu ce jocuri
și cât de mult au marcat
și toate aceste lucruri.
Pot exista erori.
Așadar, acești stagiari

actualizează în mod constant această bază de date cu
interogări de genul, oh, nu contează,
această persoană nu a
jucat în acest joc,
sau de fapt, a făcut-o și au
marcat acest număr de puncte.
Acesta este... clarifică
și înregistrează lucrurile.
Și apoi, la un moment dat
, ca
atunci când vrem să
jucăm un joc, vreau să
pot returna
tricoul cu cea mai mare
performanță a k-a în timp de log n.
Aceasta este un fel de
interogare de rang, nu?  Al
k-lea cel mai înalt.
Acum, de fapt, s-ar putea să vreau
să returnez toți cei mai înalți k jucători,
astfel încât aceasta să fie lista mea.
Dar aceasta este o
interogare mai generalizată.
Este mai specific, mai mult...
nu este chiar comparabil.
Dar vă faceți o idee de ce ar
putea fi util antrenorului.  Nu
știu.
Poate nu.
Deci care este ideea aici?
Avem o mulțime de
lucruri diferite care plutesc în jur.
Avem jocuri.
Au ID-uri unice.
Avem receptori.
Au ID-uri unice.
Și fiecare receptor ar putea
juca în multe jocuri.
Oh, e cam îngrijorător.
Și mulți receptori ar putea
juca în același joc.
Acest tip de
mapări multi-la-unu
sunt puțin confuze.
Și apoi avem fiecare jucător --
receptor -- având un anumit
număr de puncte per joc.
Și încercăm să le sortăm,
oarecum, după performanța lor,
care este un număr rațional.
Uf, nu?
Care are legătură cu
numărul de jocuri pe care le-au jucat
și cu numărul total de puncte.
Acum, văd un număr rațional,
nu pot să calculez asta.  Despre
asta vorbim
ultima sesiune cu probleme, nu?
Dar ceea ce pot face
este să pot stoca
numărul total de
jocuri pe care le-au jucat
și numărul total
de puncte pe care le au.
Și vă puteți imagina,
prin augmentare
similară cu aceasta, de fiecare
dată când adaug un joc, una
dintre aceste mici operațiuni,
pot actualiza acele informații
pentru fiecare jucător.
Dacă una dintre aceste
operații dinamice
afectează
un singur receptor,
pot actualiza orice
este în timp constant,
probabil, dacă doar stochez
cu jucătorul care este
numărul total de jocuri
înregistrat de baza de date
și câte puncte
au avut.  marcat.
Apoi, dacă am o
structură de date care
trebuie să sorteze receptorii în funcție de
performanța lor,
astfel încât s-ar putea să-l
găsesc pe cel de-al-lea -- cel
mai mare -- atunci nu pot
calcula acea performanță.
Dar ce pot face?
Pot compara doi jucători în funcție
de performanța lor folosind
multiplicarea încrucișată.
Pentru că am
numărătorul și numitorul
fiecăruia dintre aceste
raționale și pot să înmulțesc
încrucișat și să îmi dau
seama dacă unul este
mai mare sau mai mic.
Și atâta timp cât
am un comparator,
pot face chestii de setare AVL.
Are sens?
BINE.
Voi sublinia un fel
de componente ale acestei
structuri de date.
Ei bine, în primul rând, va
trebui să înregistrez un receptor.
Și un receptor ar putea
avea o mulțime de jocuri.
Dar importanta... aceasta este
un fel
de problemă centrată pe receptor.
Are
sens pentru voi?
Nu vreau niciodată să
filtrez pe toți receptorii care
joacă un joc.  Nu
elimin niciodată un
joc din sistem,
elimin un
receptor din a
juca vreodată într-un anumit joc.
Are sens?
Deci, dacă stochez un
receptor și fiecare receptor
are câteva jocuri
asociate cu ele, este logic,
aș
dori să am o structură de date imbricată
în care...
poate am un
dicționar despre receptori.
Și pentru fiecare,
stochez toate jocurile pe
care le-au jucat într-
o altă structură de date.
Cu fiecare receptor, stochez
altul... propria sa
structură de date care conține
toate jocurile sale.
Are sens?
OK, deci asta e ideea.
Avem un fel de...
Trebuie să pot
căuta receptori,
pentru că le șterg
sau le înregistrez.
Așa că am de gând să am
un dicționar sau...
aici, caut
timp de înregistrare în cel mai rău caz.
Deci, voi sări peste
abstracția dicționarului
și voi merge direct la setul AVL.
AVL tastat pe receptoare.
I înainte de E, cu excepția
după C. Este I--
E-I?
Această regulă nu funcționează niciodată.
BINE.
Setați arborele AVL pe receptoare
și fiecare dintre acele noduri
cu fiecare dintre acele
receptoare, voi stoca--
pentru fiecare, stocați un
set AVL pe jocuri.
De ce stochez un
set AVL pe jocuri?
De ce nu stochez o
listă cu toate jocurile?
Pentru că dacă vreau să elimin
acest joc de pe un receptor,
trebuie să fac asta în log n time.
Și aici, ceea ce spunem este
că n este numărul de jocuri,
dar că numărul de
receptori din echipă
este întotdeauna mai mic decât
numărul de jocuri.
Dacă caut în acest arbore AVL
și caut în arborele său AVL,
pot fi sigur că acele două
căutări au fost doar log n timp.
Pentru că trebuie să
elimin jocul, nu?
Deci iată.
Atunci ce fac?
Întorc cea
mai mare performanță a k-a.
Ei bine, am nevoie de-- cu fiecare
dintre acești tipi, de asemenea, păstrez--
ce a fost această augmentare?
Suma punctelor
stocate în aceste jocuri.
Suma punctelor și...
ce a fost... numărul de jocuri.
Pentru că dacă stochez ambele
lucruri în timp constant,
voi putea să le
calculez performanța,
unde voi
putea avea datele de care am
nevoie pentru a compara performanțele.
PUBLIC: [INAUDIBIL]?
JASON KU: Da, este.
Doar numere.
Acestea sunt structuri de date.
Aceasta este o structură de date.
Acestea sunt doar numere.
Și îl stochez
cu fiecare receptor.
Dar asta nu
mă va ajuta să găsesc al-lea cel mai înalt jucător.
Niciunul dintre aceste lucruri nu este
sortat în funcție de performanță.
Deci am nevoie de o ultimă structură de date.
Cinci, trebuie să stochez
ceva sortat dinamic în funcție
de performanță.
PUBLIC: Setați AVL?
JASON KU: Setează AVL, da.
Setați AVL să stocheze receptoarele
în funcție de performanță.
Acum, când spun
performanță,
vrei să menționezi
ceva despre
înmulțirea încrucișată.
De exemplu, stochez, cu
fiecare dintre aceste lucruri,
această augmentare, iar când
compar două lucruri,
folosesc multiplicarea încrucișată.
Dar în afară de asta, atunci o
putem abstrage, nu?
Am abstras
acel apel de funcție.
Și îmi pot imagina că
compar două chei.
Pot sa fac asta.
Acesta este o chestie de teorie.
Nu vă cer
să implementați asta.
Dar asta e suficient pentru mine,
ca cititor al soluției tale, să
pot spune, da,
știi despre ce vorbești.  În
regulă.
Cum conectez aceste lucruri?
Chestia este că va trebui să
fiu...
Trebuie să actualizez aceste lucruri
atunci când inserez sau elimin un joc.
Deci, de unde știu unde sunt acești
receptori în chestia asta?
Stochez un pointer în
această structură de date, nu?
Deci, sus, stochez
un pointer către locul în care se
află în structura de date.
Din nou, stochez
toate receptoarele.
Acesta are aceeași dimensiune
ca structura de date numărul 1
de acolo -- are
același număr de receptoare.
Dar încă nu am terminat
, pentru că nu
vreau să știu cine are
cea mai bună performanță.
Vreau să știu cine are cea
mai bună performanță.
Uf.
Cum găsesc cel
mai bun lucru din acest copac?
Am un copac.
Setați arborele AVL.
Este mapat pe performanță.
Știu unde este ultimul.
Dar dacă vreau să-l găsesc
pe cel de-al-lea de la final,
cum fac asta?
Este un arbore AVL--
un arbore AVL stabilit.
Tot ce păstrez sunt înălțimi.
Există vreo operație la
care te-ai gândit?
PUBLIC: [INAUDIBIL]
nu stocați dimensiunea fiecăruia.
JASON KU: Un arbore AVL setat
, în mod implicit,
nu stochează dimensiuni, nu?
Asta face o secvență.
Dar crezi că poate ar
fi de ajutor în această situație?
Da.
Deci, de fapt, dacă aș decide
să măresc și cu dimensiuni,
aș putea face exact același tip
de operație de secvență find_at
și aș putea să
caut elementul n minus k-lea
aici folosind exact aceeași
funcție pentru subarborele la care am  a
avut în secvența
AVL tree stuff.
De fapt, în CLRS,
ei nici măcar nu
se deranjează cu arbori AVL secvenți.
Ei merg direct la, dacă aș dori
această funcționalitate de găsire a rangului
într-o ordine sortată
a lucrurilor, atunci
aș putea mări
dimensiunile subarborelui.
Dar este de fapt o
proprietate generală mult mai utilă,
așa că am decis să ți-o prezentăm
în contextul
arborilor AVL de secvență, pentru că atunci mă
pot reduce
la ea când ajung aici.
Deci, aceasta este un fel de
structură a unei structuri de date
care funcționează la această problemă.  Vă
las pe seama dvs. ca
exercițiu să implementați
toate aceste operațiuni
pentru dvs.
sau să aruncați o privire asupra soluțiilor.
Ultimul va
fi pus online -
soluția.
E destul de complicat.
Este ceea ce se numește -- vă puteți
gândi la
rangul de găsire a măririi dimensiunii ca la o
interogare unilaterală.
Practic, câte lucruri
sunt la dreapta acestei valori?
Ceea ce face ultima problemă
este să vă ghideze
printr-o interogare cu două fețe
, unde
vreau să știu câte noduri
sunt între aceste două valori.
Deci este o trecere în revistă.  În
regulă.
Multumesc baieti.
PUBLIC: Mulțumesc.