[SCRÂTÂND]
[FOȘTIT] [CLIC]
ERIK DEMAINE: Bine, bine ați
revenit pe terenul structurilor de date.
Astăzi continuăm și completăm
segmentul nostru pe arbori binari.
Deci aceasta este partea a doua.
Dacă ați ratat partea întâi,
întoarceți-vă și vizionați partea întâi.
Ultima dată, am vorbit despre
arbori binari în general.
Fiecare nod a stocat câte un
element și, de asemenea, un pointer stânga
și un indicator din dreapta
către alte noduri
și un pointer părinte
către un alt nod.
Acesta a fost un exemplu de copac.
B și C sunt copiii lui A.
A este părintele lui B
și C și, de asemenea, rădăcina
întregului arbore.
Am definit înălțimea unui nod.
Nu l-am folosit încă prea mult.
Dar
îl vom folosi mult astăzi.
Așa că nu uitați, înălțimea
este așa cum este desenată cu roșu aici.
Înălțimea nodului este lungimea celor
mai lungi
margini de numărare a căii în jos.
Deci B, de exemplu,
are o lungime de 2 căi.
Deci scriem un 2 aici.  De
asemenea, vă puteți gândi
la asta ca și cum ați
trăi doar în subarborele
înrădăcinat la subarborele B, B,
atunci care este
adâncimea maximă a acelor noduri,
dacă preferați să vă gândiți
la asta în acest fel.
Ambele sunt ok.
Și, în special,
am distins
h, înălțimea
nodului rădăcină, ca înălțimea
întregului copac.
Și ceea ce am realizat
data trecută a fost că
toate operațiunile noastre
au derulat în ordinea timpului.
Deci am avut subtree insert,
subtree delete, subtree primul
și ultimul.
Am putea calcula
predecesorul și succesorul
unui nod, totul în ordinea timpului.
Deci, atâta timp cât h era
mic, eram fericiți.
Și amintiți-vă, ce
înseamnă predecesor și succesor?  Este
vorba despre o
ordine implicită în arbore, care
este ceea ce numim ordine de traversare,
care este definită recursiv
ca traversarea recursiv
subarborele din stânga, apoi scoaterea rădăcinii,
apoi traversarea recursiv
subarborele din dreapta.
Deci, în acest exemplu,
ordinea de traversare este F este --
dacă mergeți până la
stânga, acesta a fost primul
în ordinea de traversare.
Atunci avem... corect, îmi voi
face puțin spațiu aici.
Apoi avem D,
apoi avem B. Apoi
facem
subarborele din dreapta lui B, care
este E. Apoi avem
rădăcina, pentru că am terminat
subarborele din stânga al rădăcinii.
Deci, acesta este A. Și apoi avem C.
Deci există o ordine liniară implicită
codificată de acest arbore.
Și scopul
arborilor binari
este că putem
actualiza eficient arborele mult mai repede
decât am putea scrie în mod explicit
o ordine într-o matrice
sau ceva de genul acesta.
Deci, copacii binari ne permit repede...
acum, rapid nu este
atât de rapid acum.
Pentru că totul este ordine h.
Și în cel mai rău
caz, h este liniar.
Pentru că putem avea
un copac ca acesta.
Dar astăzi, vom
face-- vom
garanta că h este log n.
Și astfel, scopul de
astăzi este să luăm
toate aceste operațiuni
care rulează în ordinea h timp
și să le facem să ruleze un
jurnal de comenzi n timp, doar
prin modificarea
structurii de date pe care am văzut-o deja.
Așa că am făcut multă
muncă grea, doar puțin
mai multă muncă pe care trebuie să o facem
astăzi pe ceva numit
arbori AVL sau echilibru înălțime.
Dar înainte de a ajunge acolo, vreau
să vorbesc puțin mai mult --
la sfârșitul
ultimei prelegeri, am
vorbit despre odată ce aveți
aceste operațiuni în subarborele --
ca să pot insera și
șterge în subarborele --
cum fac  De fapt, folosim asta pentru a
rezolva problemele care ne
pasă în această clasă, care sunt
structura de date secvență și
structura de date setată?
Așa că am vorbit mai ales despre
structura de date setată data trecută.
Deci, în general, vom
defini ce ordine de traversare
menținem printr-un arbore binar.
Și așa pentru un set, pentru că
pentru interfața set,
suntem interesați să facem
interogări precum find_next
și find_previous, având în vedere
o cheie, dacă nu este acolo,
spuneți-mi pe
cea anterioară sau pe următoarea,
acesta este ceva cu care am putea
face  căutare binară.
Așadar, lucrul mare și grozav
pe care ni-l permit arborii binari,
dacă lăsăm ca ordinea de traversare să
fie întotdeauna toate elementele
stocate în
ordine crescătoare a cheilor, atunci
menținem efectiv
elementele în ordine -
în sensul ordinii de traversare.
Din nou, nu
le menținem în mod explicit în ordine.
Dar aici sus,
menținem un arbore care
reprezintă elementele în ordinea cheie.
Și astfel, aceasta ne permite să facem o
operație subtree_find - pe
care o puteți
utiliza cu ușurință pentru a implementa find,
și find_previous și așa mai departe -
după cum urmează.
Începem de la
rădăcina copacului.
Deci putem spune,
inițial, nodul este egal cu rădăcina.
Și apoi putem
căuta recursiv o cheie k după cum urmează.
Verificăm, ei bine, dacă
elementul de la rădăcină
are o cheie mai mare decât k-- să
fac o mică imagine.
Deci suntem la un nod aici.
Acesta este un nod.
Și are subarborele din stânga
și un subarborele din dreapta.
Și există un
articol cu ​​o cheie.
Deci, dacă cheia pe care o căutăm
este mai mică decât elementul nodului, înseamnă că se află

aici, în subarborele din stânga.
Și astfel recurgem pe node.left.
Dacă sunt egale,
înseamnă că acest articol
este articolul pe care îl căutăm.
Așa că îl putem returna
sau doar nodul,
în funcție de ceea ce
cauți.
Și dacă cheia de aici
este mai mare decât cheia pe care o
căutăm, atunci
vom recurge la dreapta.
Dacă vă gândiți
puțin la asta,
aceasta este exact
căutare binară pe o matrice.
Se întâmplă să
fie pe un copac.
Dacă te gândești la o
matrice ca aceasta,
ce face căutarea binară?  Se
uită mai întâi la
cheia din mijloc.
Voi desena
asta ca rădăcină.
Și apoi, se recurge
fie pe fragmentul din stânga, pe
care îl voi desena recursiv,
fie pe fragmentul din dreapta.
Și așadar, dacă se întâmplă să
aveți un arbore binar perfect
ca acesta, acesta
simulează exact
căutarea binară în această matrice.
Dar asta o vom putea
menține dinamic... nu
mai este perfect, ci aproape.
În timp ce acest lucru nu l-am putut
menține în ordine sortată.
Deci, aceasta este ca o
generalizare a căutării binare
pentru a funcționa pe copaci
în loc de pe matrice.
Și din acest motiv, arborii binari setați
se numesc arbori de căutare binari
, deoarece sunt
versiunea arborescentă a căutării binare.
Deci există multe
nume echivalente.
Deci, arborele de căutare binar este un alt
nume pentru arborele binar set.
Și lucrul cheie care
face ca acest algoritm să funcționeze este
așa-numita
proprietate a arborelui de căutare binar, care
este că toate cheile din
subarborele din stânga unui nod
sunt mai mici decât
rădăcina sau acelui nod
și acea cheie este mai mică decât
toate  cheile din subarborele din dreapta.
Și acest lucru este adevărat recursiv
până la capăt.
Și așa demonstrezi
că acest algoritm este
corect prin această proprietate.
De ce este acest lucru adevărat?
Pentru că dacă putem
menține ordinea de traversare
pentru a fi
cheie crescătoare, atunci exact asta

înseamnă ordinea de traversare.
Vă spune că toate lucrurile
din subarborele din stânga vin
înaintea rădăcinii, care
vin înaintea tuturor lucrurilor
din subarborele din dreapta.
Deci această proprietate o
implică pe aceasta.
Și cum mențineți lucrurile
într-o ordine crescătoare a cheilor?
Este destul de ușor.
Dacă doriți să introduceți un
articol, unde îi aparține?
Ei bine, faci această
căutare pentru a găsi unde
ar fi locul dacă ar fi acolo.
Dacă este acolo, puteți suprascrie
valoarea stocată cu acea cheie.
Dacă nu este, această
căutare va cădea din
arbore la un
moment dat și
acolo inserați un
nou nod în arborele dvs.
Asta a fost tratat în recitare,
așa că nu vreau să mă opresc asupra ei.
Pe ce vreau să mă concentrez astăzi
este cealaltă aplicație.
Cum facem... asta pentru a
reprezenta un set, care
este relativ ușor.
O provocare pentru care să
ne pregătim,
dar avem nevoie de
ceva mai multă muncă, este
să facem arbori binari secvenți.
Deci, să presupunem că am un
arbore binar și ce mi-aș dori --
am menționat la
sfârșitul ultimei oară --
este că vreau ca
ordinea de traversare a arborelui meu
să fie
ordinea secvenței, ordinea pe care
încerc să o reprezint.  care este
schimbat de operațiuni
precum insert_at.
Așa că aș vrea să
fac același lucru.
Dar acum, trebuie să mă gândesc
cum fac o căutare,
cum fac o insert_at,
așa ceva.
Și iată un algoritm pentru
ceea ce aș dori să lucrez.
Dar
încă nu va funcționa prea bine.
Deci, să presupunem că vă dau un
subarboresc, așa specificat de un nod.
Deci sunt toți
descendenții acelui nod.
Și aș dori să știu ce
este în ordinea traversării
acelui subarbor, care
începe aici și se termină aici,
iar rădăcina va fi
undeva la mijloc.
Dă-mi nodul i-lea.
Deci, dacă întreb i este egal cu
0, vreau să obțin
acest descendent din stânga.
Dacă cer că i este egal cu
dimensiunea arborelui minus 1,
vreau să obțin
descendentul din dreapta.
Acesta a fost primul și
ultimul din subarborele despre
care am vorbit.
Dar știm cum să găsim
primul și ultimul.
Mergeți doar la stânga sau la dreapta.
Dar nu știm cum
să găsim nodul i--
în ordinea h timpul este
scopul în acest moment, nu log n.
Și ideea este că se
pare că dimensiunea contează.
[Chicote] Îmi pare rău dacă
ați auzit altfel.
Deci, în special,
am menționat dimensiunea
când vorbeam despre
ultimul nod din secvență.
Indicele acelui nod este
dimensiunea subarborelui minus 1.
Deci, să definim
dimensiunea unui nod
ca fiind numărul de
noduri din subarborele său --
numiam
acel subarboresc (nodul) --
inclusiv nodul însuși.
Deci, dacă știam
cumva dimensiunea, aceasta
pare importantă pentru
înțelegerea indicilor.  Să
presupunem că am
știut asta magic
în timp constant.
Apoi, susțin că
dimensiunea subarborelui din stânga--
așa că de ce nu extind
puțin această diagramă?
Deci avem nod ca înainte.
Dar avem subarborele din stânga
și un subarborele din dreapta.
Deci, acest nod de aici este node.left.
Acest nod aici este node.right.  S-ar
putea să nu existe, dar să
ignorăm acele cazuri excepționale
deocamdată.  Să
presupunem că nu știm
doar dimensiunea nodului,
ci și
dimensiunea node.left,
deci aceasta este dimensiunea
acestui arbore din stânga.  O să-l
numesc nL.
Deci, să presupunem că
aici există nL noduri.
Pretind că asta îmi permite să fac
echivalentul unei căutări binare.
Pentru că caut
ceva index i.
Și dacă i este mai mic decât nL, atunci
știu că trebuie să fie aici jos.
De exemplu, dacă i este
egal cu 0, va
fi în subarborele din stânga, atâta timp
cât nL este mai mare decât 0,
nu?
Deci exact aceasta este verificarea.
Dacă i este mai mic decât nL,
voi recurge
la stânga, apelez subarborele
la node.left, i.
Asta scrie aici.
Dacă i este egal cu nL, dacă te gândești
la asta pentru o secundă - deci nL
este numărul de noduri de aici.
Și asta înseamnă că acest
nod are indexul nL.
Indicele acestui nod este nL.
Și deci, dacă i este egal cu -- dacă
singurul index pe care îl căutăm
este acela, atunci pur și
simplu returnăm acest nod.  Au fost
efectuate.
Și în caz contrar, i
este mai mare decât nL.
Și asta înseamnă că
nodul pe care îl căutăm
este în subarborele potrivit,
deoarece vine după rădăcină.
Din nou, asta înseamnă.
Asta
înseamnă ordinea traversării.
Deci, dacă definim că
este ordinea secvenței,
atunci știm că toate lucrurile
care vin după acest nod, care
este indicele nL, trebuie să fie aici.
Acum, când recurgem aici jos,
sistemul nostru de numerotare se schimbă.
Pentru că pentru nod, 0 este aici.
Și apoi pentru node.right este aici.
Așa că trebuie să facem puțină
scădere aici, atunci când
recurgem
la dreapta,
luăm i minus nL minus 1--
minus nL pentru acești tipi,
minus 1 pentru nodul rădăcină.
Și asta ne va oferi
indexul pe care îl căutăm
în acest subarbore.
Deci ideea mea este că acest
algoritm este practic
același cu acest algoritm.
Dar acesta folosește chei, pentru că
avem de-a face cu un set,
iar în seturi presupunem că
articolele au chei.
Aici, articolele nu
trebuie să aibă chei.
De fapt, nu ne
atingem deloc de articole.
Întrebăm doar, care este al-
lea element din secvența mea, care
este același lucru cu al-lea
element din ordinea mea de traversare,
care este același lucru
cu a întreba care este al-lea
nod în ordinea de traversare?
Și acest algoritm îți
dă
exact același
mod în ordinea timpului.
Acum, nu am de gând să-
ți arăt toate operațiunile.
Dar puteți folosi subtree_at
pentru a implementa get_at set_at.
Doar găsiți
nodul corespunzător și returnați articolul
sau modificați articolul.
Sau îl puteți folosi pentru a--
cel mai important, îl puteți folosi
pentru a face insert_at delete_at.
Acesta este un lucru nou pe care
nu l-am putut face niciodată până acum.
Ce faci?  La fel ca
aici, dacă
încerc să inserez un articol, îl
caut
aici.
Deci, dacă încerc să inserez la
i, de exemplu, caut i.
Și apoi pentru insert_at i,
doriți să adăugați un articol nou chiar
înainte de acesta.
Și, în mod convenabil,
avem deja...
N-am menționat, dar
avem o inserție sub-arbore.
Aveam două versiuni -
înainte și după.
Cred că am acoperit după, pe
care îl folosesc succesor
înainte de a folosi predecesor.
Dar putem
apela doar inserarea subarborelui
înainte la acel nod și
boom, vom fi adăugat
un element nou chiar înaintea lui.
Și grozav, atât de
magic, cumva, l-am
introdus în
mijlocul acestei secvențe.
Și toți indicii se actualizează,
pentru că nu stochez
indici.
În schimb, pentru a căuta
un articol la indexul i,
folosesc algoritmul de căutare.
Dar există o problemă.
Care este problema?
Acest lucru pare puțin prea
frumos pentru a fi adevărat.
Inserez în
mijlocul acestui arbore
și apoi, cumva, pot să
caut magic și să
găsesc încă al i-lea element, chiar dacă
toți indicii din dreapta
acelui articol au crescut cu 1.
Este aproape adevărat.
Răspuns?
Da?
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: Pentru că trebuie să
actualizăm dimensiunile, corect.
Nu am spus, cum calculez
dimensiunea subarborelui din stânga?
Deci acesta este următorul subiect.
Aproape am terminat.
Acest lucru chiar va funcționa.
Este cu adevărat grozav.
Dar pentru ca acesta să funcționeze,
avem nevoie de ceva
numit subtree
augmentation, despre care
voi vorbi în general.
Și apoi,
îl vom aplica la dimensiune.
Deci, ideea cu
creșterea subarborelui
este că fiecare nod
din arborele nostru binar
poate stoca un
număr constant de câmpuri suplimentare.
De ce nu?
Și în special,
dacă aceste câmpuri
sunt de un anumit tip,
poate le voi numi proprietăți.
Voi defini
o proprietate subarbore
ca fiind ceva
ce poate fi calculat
din proprietățile
copiilor nodurilor.
Deci ar trebui să spun că
este vorba despre un nod.
Deci copiii sunt
nod.left și node.right.  De
asemenea, puteți accesa o
cantitate constantă de alte lucruri,
de exemplu nodul în sine.
Dar scopul
unei proprietăți sub-arbore
este că arată în jos.
Dacă am un nod
aici și vreau
să calculez o
proprietate despre el --
numiți asta, vrem să
stocăm P al nodului --
și să presupunem că
știm deja P aici,
proprietatea calculată
pentru subarborele din stânga
sau pentru
nodul stâng și știm deja
proprietatea
nodului din dreapta, atunci ceea ce aș dori
este ca aceasta să fie
calculată în timp constant.
Deci pot calcula P al acestui
nod având în vedere P al nodului stâng
și P al nodului drept.
Aceasta este o proprietate subarbore.
Acum, în special, dimensiunea
este o proprietate a substratului.
De ce?
Pentru că pot scrie
acest tip de recurență,
node.size este egal cu
node.left.size--
este foarte obositor de scris--
plus node.right.size, plus?
1, multumesc.
Mărimea întregului
subarbore de aici, numit nod,
este dimensiunea subarborelui din stânga
plus dimensiunea subarborelui din dreapta,
plus 1 pentru acel nod în sine.
Deci aceasta este o regulă de actualizare.
Este nevoie de
timp constant pentru a evalua.
Sunt două ediții.  Îmi
pare rău, T-ul meu arată cam ca
semne plus.
O să fac plusurile
puțin mai mari.
Deci doar însumăm
aceste trei lucruri.
Boom, putem obține node.size.
Așa că susțin că atâta timp cât
proprietatea mea are această caracteristică,
o pot menține dinamic
în timp ce schimb arborele.
Acum, aceasta este un pic
de referință înainte,
pentru că încă nu am
spus exact cum vom
schimba arborele.
Dar întrebare?
PUBLIC: Dacă node.size
este recursiv,
atunci cum se întâmplă
în timp constant?
Nu s-ar
întâmpla [INAUDIBIL]?
ERIK DEMAINE: De ce este asta...
OK, bună întrebare.
Deci, într-un
mod natural, vă puteți gândi
la aceasta ca la o recursivitate,
care vă oferă
un algoritm recursiv.
Așa că am scris... dar
nu am scris.
Dar aș fi putut scrie
dimensiunea nodului este egală cu aceasta -
dimensiunea nodului.left
plus - și asta ți-
ar oferi un algoritm de timp liniar
pentru a număra dimensiunea.
Și dacă nu
ai nicio informație,
asta ai face.
Și asta ar fi foarte dureros.
Deci asta ar face acest
algoritm cu adevărat lent.
Dacă apelez la dimensiune ca o
funcție recursivă, este rău.
În schimb, ceea ce fac
este să stochez dimensiunile
pe fiecare nod
și să precalculez acest lucru.
Deci, de fapt, voi
defini dimensiunea nodului în--
deci aceasta este definiția
matematică.
Dar algoritmul
pentru această funcție va
fi
return node.size.
Deci este timpul constant.
Așa că provocarea acum este că
trebuie să țin aceste dimensiuni
la zi, indiferent de ce
i-aș face copacului.
Și ai putea să te uiți
înapoi la ultima prelegere
și să vezi, OK, care au fost toate
schimbările pe care le-am făcut într-un copac?  Am
făcut modificări doar
în timpul inserării și ștergerii.
Și vă voi pretinde că,
când am inserat și șters,
ceea ce au ajuns să
facă în cele din urmă,
ei adaugă sau scot
o frunză a copacului.
Amintiți-vă, o frunză era un
nod fără copii.
Deci, să ne gândim dacă
adaug o nouă frunză într-un copac -
iată un copac, să presupunem că
adaug o frunză aici -
care subarbori se schimbă?  Ei
bine, ce subarbori
conțin acel nod?
Este propriul său nou subarbore.
Apoi este în subarborele părinte
și subarborele bunic
și subarborele general.
În general, aceste noduri
sunt numite strămoșii
acestui nod pe care l-am adăugat.
Și acestea sunt
cele care se actualizează.
Acest subarbore de
aici nu s-a schimbat.
Nu s-a schimbat dimensiunea.
Și pentru că este o
proprietate subarboresc,
nicio proprietate nu se
va schimba aici,
deoarece subarborele
a fost neatins.
Deci, când ating acest
tip, trebuie doar să
actualizez
proprietatea subarboresc aici, să
actualizez
proprietatea subarbore aici, să
actualizez proprietatea subarbore aici.
Câte dintre acestea sunt?
Da?
h-- Voi spune ordin h pentru a fi în siguranță.
Dar cred că este exact h.  La fel, de asemenea,
când elimin
o frunză, același lucru--
dacă elimin această frunză,
atunci subarborii
care se schimbă sunt exact foștii
săi strămoși.
Cool, așa că vom
actualiza acei strămoși de ordine h
în ordinea în sus.
Deci, ce vreau să spun prin actualizare?
Adică aplică această regulă.
Pentru dimensiune, aceasta este regula.
Dar, în general,
proprietatea subarbore
îmi oferă o regulă de actualizare
care necesită timp constant.
Și așa voi
aplica acea regulă de actualizare
acestui nod, care va repara
orice proprietate este stocată
acolo.
Poate că există mai
multe proprietăți.
Și apoi îl voi aplica
acestui nod.
Și pentru că acest lucru este deja
corect prin inducție
și acest lucru este deja corect
pentru că nu am atins acest
subarboresc -- este neschimbat --
atunci pot actualiza
valoarea la acest nod --
proprietatea acestui
nod în timp constant.
Apoi îl actualizez pe acesta.
Și pentru că acesta este
deja corect prin inducție,
iar acesta este deja
corect pentru că acest subarbore este
neschimbat, pot actualiza
proprietatea corect aici
în timp constant.
Deci, când fac o
schimbare în ordinea h timp,
deoarece fac h apeluri la
acest algoritm de timp constant,
pot actualiza un
număr constant de proprietăți ale subarborelui.
Acest lucru este foarte puternic.
Mărirea structurii datelor
este super utilă.
Îl vei folosi pe
setul de probleme.  Îl vom
folosi din nou astăzi.
Permiteți-mi să vă dau câteva exemple
de proprietăți ale subarborescului.
Ele ar putea fi... cele obișnuite sunt,
cum ar fi, suma sau produsul, sau
minul, sau
maximul, sau suma pătratelor,
sau tot felul de
lucruri, a unei caracteristici
a fiecărui nod din subarborele.
De fapt, dimensiunea subarborelui este
un exemplu de așa ceva.
Este suma peste toate nodurile
din subarborele valorii 1.
Este un alt mod de a spune
numărați numărul de noduri.
Dar ai putea
spune, de asemenea, care este suma
cheilor din aceste noduri?
Sau ați putea spune, care este
cheia maximă în aceste noduri?
Sau ați putea spune, care este
valoarea maximă în aceste noduri?
Puteți lua orice proprietate.
Nu trebuie să fie cheie.
Nu trebuie să fie
ceva anume.
Este foarte puternic.
Puteți lua toate sumele,
produsele și le puteți menține
atâta timp cât sunt în
jos,
atâta timp cât vă
gândiți doar la subarborele.
Câteva exemple de lucruri pe care nu le
puteți menține sunt --
nu un index de noduri.
Deci, dacă ești puțin prea
entuziasmat de mărire, s-ar
putea să te gândești, oh,
aș putea face totul.
Trebuia să suport
subtree_at, sau să
spunem, get_at la
nivel global, am vrut
să știu care este
nodul i-lea din arborele meu?  Ei
bine, voi folosi doar
creșterea structurii de date
și voi stoca în fiecare nod care este
indexul său, de la 0 la n minus 1.
Nu pot să mențin
asta eficient.
Pentru că dacă inserez
la începutul
ordinii mele de traversare, atunci
toți indicii se schimbă.
Deci acesta este un exemplu de editare.
Deci, dacă inserez un
nod nou aici,
deci indicele acestui tip
era 0, acum este 1.
Indicele acestui tip
era 1, acum este 2.
Acesta era 2, acum
este 3 și așa mai departe.
Fiecare nod își schimbă indexul.
Indexul nu este o
proprietate subarbore și de aceea
nu îl putem menține.
Pentru că depinde de toate
nodurile din arbore.
Sau depinde de toate
nodurile din stânga sa - de
toți predecesorii.
Deci, de exemplu,
indexul acestui tip depinde
de câte noduri sunt
aici în stânga, care nu se află
în subarborele acelui nod.
Deci acolo
trebuie să fii atent.
Nu utilizați
proprietățile globale ale arborelui.
Puteți utiliza numai
proprietățile subarborescului.  Un
alt exemplu este profunzimea.
Adâncimea Este enervant de menținut,
dar încă nu este evident de ce.
Vom vedea asta într-o clipă.
Restul zilei de astăzi este despre
trecerea de la ordinea h jurnalul de ordine
n, ceea ce
ne arată acest slide.
Deci, în acest moment, ar trebui să
credeți că putem face toate operațiunile cu structura de
date secvențe
în ordinea h timp --
cu excepția construirii și iterației,
care necesită timp liniar -
și că putem face toate
operațiunile setate în ordinea h  timp,
cu excepția construirii și
iterației, care iau
n log n și respectiv n.
Și scopul nostru este să
legăm acum h de log n.
Știm că este posibil
la un anumit nivel,
pentru că există copaci care
au înălțime logaritmică.
Este ca acest
copac perfect aici.
Dar știm și că
trebuie să fim atenți,
pentru că sunt niște
copaci răi, ca acest lanț.
Deci, dacă h este egal cu log n, numim
acest arbore binar echilibrat.
Există mulți
arbori binari echilibrați
în lume, poate
o duzină sau două --
o mulțime de
structuri de date diferite.
Întrebare?
PUBLIC: [INAUDIBIL]
ai spus să nu te
gândești la lucruri
la nivel global,
așa că ne vom gândi la
ele [INAUDIBIL]..
Poți explica mai
mult ce înseamnă asta?
ERIK DEMAINE: OK,
ce înseamnă
ca o proprietate să fie locală
unui subarboresc versus global?  Cel
mai bun răspuns este
această definiție.
Dar poate că nu este cea
mai intuitivă definiție.
Asta vreau să spun.
Ceva care poate fi calculat
doar cunoscând informații
despre copiii tăi stângi
și drepti,
acesta este sensul
unei astfel de proprietăți.
Și acestea sunt singurele lucruri pe care
ai voie să le întreții.
Pentru că acestea sunt
singurele lucruri
care sunt ușor de actualizat
mergând pe această cale.
Și contrastul este că
proprietatea globală, cum ar fi indexul,
este globală, în
special, pentru că
pot face o schimbare, pot adăuga un
nod și toate
proprietățile nodului se schimbă.
Deci acesta este un
exemplu extrem de global.  Ne
dorim această
noțiune foarte particulară de local,
pentru că asta ne putem
permite de fapt să recalculăm.
Sa speram ca se va clarifica.
Da?
PUBLIC: Dimensiunea nu
funcționează cu acea [INAUDIBILĂ]?
ERIK DEMAINE: Ai
dreptate că dacă am adăugat...
oh, nu.
OK, să ne gândim la asta.
Dacă am adăugat un nou
părinte în copac,
acesta nu este ceva
ce am făcut vreodată.
Dar chiar dacă am face asta,
ce subarbori se schimbă?
Doar acesta.
Acest nod, este un
subarboresc complet nou.
Dar subarborele acestui nod
este complet neschimbat.
Deoarece subarborii sunt
întotdeauna orientați în jos,
dacă am adăugat o nouă rădăcină,
nu am schimbat niciun subarboresc, cu
excepția unuia.
Deci dimensiunea este o proprietate subarbore.
Acum, sunt...
Adică, aș putea
redesena complet copacul.
Și aceasta este o operațiune
care necesită ca totul
să fie recalculat.
Deci este limitat exact ceea ce
am voie să fac în copac.
Dar pretind tot ce
vom face, ultima clasă
și astăzi, ne putem permite
această creștere.
Deci este o caracteristică, nu a
tuturor arborilor binari neapărat,
ci a celor pe
care i-am acoperi.
Da?
PUBLIC: Ce este un min?
ERIK DEMAINE: Ce este un min?
PUBLIC: [INAUDIBIL]
ERIK DEMAINE: Arbore binar, da.
OK, asta va avea un pic
mai mult sens într-un moment
în care voi spune ce vom face de fapt
cu copacii.
Avem nevoie de un nou instrument pentru
manipularea unui copac.
Ce am făcut până acum, am
făcut unele schimburi de articole.
Și am adăugat
și scos o frunză.
Nu este de ajuns.  Vom avea
nevoie de
altceva care să ne permită să
garantăm înălțimea logaritmică.
Și acel altceva se
numește rotație.
Ce
trebuie să facă acest altceva?
Acesta este doar un instrument pentru
reechilibrarea copacului.
Deci nu ar trebui să modifice datele
reprezentate de arbore.
Care sunt datele
reprezentate de arbore?
Ordine de traversare.
Ordinea transversală este sacrosantă.
Nu avem voie să-l atingem.
Este deja definite
două moduri diferite,
în funcție de dacă
utilizați un set sau o secvență.
Deci vrem să modificăm
arborele într-un mod care să nu
modifice ordinea de traversare.
Deci exploatăm redundanța.
Dacă ați notat
ordinea de traversare într-o matrice,
există exact o
reprezentare
a unei anumite ordine.
Dar într-un copac, există
multe reprezentări.
Ar putea fi o coadă lungă.
Ar putea fi o chestie de echilibru.
Ele ar putea reprezenta
exact aceeași ordine pe noduri
dacă le etichetați corect.
De fapt, există exponențial
multe reprezentări diferite
ale aceluiași lucru.
Și vom exploata asta,
aceeași ordine și vom defini...
acesta este doar un lucru pe care
trebuie să-l știi.
Permiteți-mi să etichetez, A, X, B,
Y, C. Vă puteți da seama că am
desenat această diagramă
înainte de multe, de multe ori.
Acesta este un instrument foarte puternic
în toate structurile de date arborescente,
care sunt majoritatea
structurilor de date.
Și se numesc rotire la dreapta
a lui y și rotire la stânga a lui x.
Deci, dacă am acest copac... pe
care doar îl
pun negru pe unii dintre subarbori
în triunghiuri mici.
Dacă am un nod și
are un copil stâng,
atunci am voie să rotesc la dreapta
această margine, ceea ce înseamnă să iau
această margine și să merg așa...
90 de grade, cam.
Sau ai putea să te gândești la
asta ca la o rescrie în acest fel.
Acum, s-ar putea să aveți și
urmărirea indicatorului părinte.
Indicatorul părinte se mișcă.
Înainte, acesta a fost
părintele lui y.
Acum este părintele lui x.
Deci, x și y își schimbă locurile.
Dar nu am putea doar să
schimbăm aceste elemente,
pentru că asta ar
schimba ordinea traversării.
În această imagine,
x vine înaintea lui y,
deoarece x este în
subarborele din stânga al lui y în ordinea traversării.
Și aici, acum y este
în subarborele din dreapta al lui x.
Deci vine după x.
Deci, în ambele cazuri,
x vine înaintea lui y.
Și într-adevăr, în toate aceste
imagini, ordinea de traversare --
vreau să spun, nu doar pentru x și
y, ci și pentru A, B și C,
ordinea de traversare
este consecventă.
Este A, X, B, y, C, unde,
când scriu un triunghi,
mă refer recursiv la
ordinea de parcurgere a tuturor
lucrurilor din triunghi.
Deci, dacă doar aplicați
algoritmul de ordine de traversare aici
versus aici,
obțineți aceeași ieșire,
ceea ce înseamnă că aceste operațiuni
păstrează ordinea de traversare.
Grozav, deci acesta este
un lucru pe care îl
putem face într-un copac care nu va
afecta nimic din lucrurile pe care le-am
făcut până acum.
Este un instrument pe care îl
putem folosi pentru a reechilibra.
Observați cât de adânc
sunt lucrurile în schimbările copacului.
Problema noastră cu
acest arbore liniar
este că există unele
noduri de adâncime liniară.
Vrem să scăpăm de acestea.
Cum?  Ei
bine, am putea lua aceste margini
și să începem să le rotim în sus.
Dacă te uiți la adâncimi,
în această imagine,
A și B sunt mai adânci decât
C. Și în această imagine,
B și C sunt mai adânci decât
A. Deci este un compromis.
Acesta s-a mutat în sus.
Acesta s-a mutat în jos.
Acesta a rămas
la aceeași adâncime.
Așa că, sperăm, dacă A este prea
adânc și C este prea puțin adânc, se
pot schimba astfel.
Poate suna dificil,
dar, de fapt, există
o modalitate destul de simplă,
numită arbori AVL, care
menține echilibrul într-un
mod special numit echilibru înălțime.
Asta dacă luăm
înălțimea lui node.left--
de fapt, aș prefera să--
node.right, minus
înălțimea node.left,
așa că acest lucru se numește
skew of the node.
Vreau ca acesta să fie întotdeauna
minus 1, 0 sau plus 1.
Deci, asta înseamnă că,
dacă am vreun nod
și mă uit dacă subarborele său din stânga
și subarborele din dreapta, le
măsor
înălțimile -- țineți minte,
aceasta este distanța în jos,
distanța maximă până la o frunză--
Măsurez înălțimea
acestui copac--
înălțimea maximă-- și
măsoară înălțimea maximă
a acestui subarbore, vreau ca acestea
să fie la o distanță de 1 unul de celălalt.  În
mod ideal, sunt egali.
Acesta ar fi cazul perfect.
Dar să le lăsăm să difere cu 1.
Deci, poate că acesta este k
și acesta este k plus 1.
Sau poate că acesta este k
și acesta este k minus 1.
În această imagine, care este
înălțimea acestui nod?
Este o practică bună.
k plus 2, bine.
Care este cea mai lungă cale
de la acest nod la o frunză?
Ei bine, ar putea trece
prin acest subarbore.
Și aceasta ar fi lungimea k
plus 1, pentru că este k aici
plus 1 pentru această margine.
Sau ar putea fi prin aici,
și asta este k plus 1 plus 1.
Deci cel mai mare este
să mergi la dreapta.
Deci, înălțimea... dacă ți-am spus
înălțimea acestor subarbori,
putem deduce
înălțimea acestui nod.
Vom folosi
asta mult într-un moment.
Deci, prima afirmație
este că, dacă aș putea
menține
echilibrul înălțimii, atunci voi
garanta că h este egal cu log n.
Deci, cu alte cuvinte,
echilibrul înălțimii implică echilibru.
Deci haideți să demonstrăm
mai întâi acest lucru rapid.
Și apoi, partea interesantă
este cum demonstrăm de fapt...
sau cum menținem de fapt
proprietatea echilibrului?
Vom face
asta folosind rotații.
Dar cum este o mare întrebare.
Deci, de ce
echilibrul înălțimii implică echilibru?
Deci, ceea ce se spune este
că toți copacii echilibrați în înălțime
au înălțime logaritmică.
Așadar, la ce aș vrea
să mă gândesc este
un fel de copac cel mai puțin echilibrat pe
înălțime.
Cel mai puțin echilibrat va
avea fiecare nod o nepotrivire.  Să
presupunem că
subarborele din stânga este mai puțin adânc
decât subarborele din dreapta cu 1 și
recursiv până în jos.
Deci, fiecare nod are
un decalaj aici, a--
cum îl numim--
o oblică de 1, pe care o
voi scrie--
voi introduce
o notație.
Voi scrie o
săgeată disidentă spre dreapta a acesteia
este mai mare decât subarborele din stânga.
Deci, cel mai ușor mod de a ne
gândi la asta
este că acesta este un fel
de cel mai rău caz al nostru.
Acestea vor fi cele mai puține
noduri pentru adâncimea maximă.  Să
numărăm doar câte
noduri sunt în acest arbore.
Voi scrie asta
ca o recurență, care
este numărul de noduri
dintr-un arbore de înălțime h.
Deci, dacă tot acest copac are înălțimea
h, așa cum am spus în această imagine,
dacă doar scad 2
din toate aceste numere,
atunci acesta are
înălțimea h minus 2,
iar acesta are
înălțimea h minus 1.
Deci câte noduri sunt în  Aici?  Ei
bine, aceasta este o recurență pe care o voi
scrie.
Deci, acesta va fi N sub h minus 2.
Acesta va fi N sub h minus 1.
Și apoi număr doar câte
noduri sunt în această imagine.
Este Nh minus 1 plus Nh
minus 2 plus 1, sau acest nod.
Acum ați putea să vă întrebați,
pentru ce este Nh o recurență?
Dar este numărul de noduri
în acest tip de cel mai rău caz
dacă cel mai rău caz
are înălțimea totală h.
Deci, vă puteți
gândi, de asemenea, la asta, care
este numărul minim
de noduri pe care l-aș putea
avea într-un arbore AVL, care este
un arbore echilibrat în înălțime, care
are o înălțime h într-un
arbore echilibrat în înălțime?
OK, așa că acum trebuie doar să
rezolv această recurență.
Această recidivă
pare familiară?
Este ca numerele Fibonacci.
Dacă scot plusul
1, este Fibonacci.
Și dacă se întâmplă să știți că
numerele Fibonacci cresc
ca o
proporție de aur față de n,
atunci știm că
aceasta este exponențială,
ceea ce ne dorim.
Pentru că dacă Nh este
exponențial în h,
înseamnă că h este
logaritmic în N,
deoarece log este invers
exponențial.
Dar poate că nu știți
despre numerele Fibonacci.
Și astfel putem încă
arăta cu ușurință că acest lucru este exponențial,
după cum urmează.
Vreau să demonstrez că este
cel puțin un exponențial,
pentru că asta îmi dă că
h este cel mult logaritmic.
Deci avem nevoie de o limită inferioară.
Și așa avem acești doi termeni
care sunt greu de comparat--
Nh minus 1 și Nh minus 2.
E cam urât.
Dar dacă ni se permite
să fim neglijenți -
și vom vedea dacă
nu suntem prea neglijenți -
și primim totuși un
răspuns exponențial,
să-i facem
egali așa.
Deci aceasta este o afirmație adevărată,
de fapt, strict mai mare decât.
De ce?
Pentru că am eliminat plusul 1.
Asta ar trebui să facă doar
ceva mai mic.
Și am înlocuit Nh minus
1 cu Nh minus 2.
Aici, implicit
folosesc un fapt,
care este evident prin inducție,
că acest copac pe înălțime -
dacă iau acest copac
față de acest copac,
acesta are mai multe
noduri decât acesta.  unu.
Dacă am înălțime mai mare,
această construcție
va construi un copac mai mare
, cel puțin la fel de mare.  Nici
măcar nu trebuie
să fie strict mai mare.
Deci, cu siguranță, Nh minus 1
este mai mare sau egal
cu Nh minus 2.
Acum, acesta este de 2 ori Nh minus 2.
Și aceasta este o recurență ușoară.
Acestea sunt doar puteri ale lui 2.
Continui să înmulțesc cu 2
și să scad 2 din h.
Deci asta se rezolvă la
2 la h peste 2,
poate cu un etaj sau ceva.
Dar folosesc un caz de bază aici,
care este N sub 0 este egal cu 1.
Poate că atunci este un plafon.
Dar ideea este că
acest lucru este exponențial.
Deci, acest lucru implică faptul că înălțimea
este întotdeauna, de cel mult, de 2 ori
log n.
Acest 2 corespunde acestui 2.
Dacă doar inversați
această formulă, acesta a
fost un număr de noduri va
fi cel puțin 2
la h peste 2.
Și astfel h este, cel mult, 2 log n.
Deci nu este log n.
Ar fi perfect.
Dar se află într-un
factor de 2 din log n.
Deci arborii AVL sunt
întotdeauna destul de echilibrați.
Numărul de niveluri
este cel mult dublu față de cel de care
aveți nevoie pentru a stoca n noduri.
Grozav.
Rămânem cu magia principală,
nu cu magia domeniului.
Asta e diferit.
Și să vedem, vom
folosi creșterea subarbore.
Ține asta.
Marea
provocare rămasă este cum
menținem această proprietate de echilibru ridicat
folosind rotații?
Avem toate ingredientele
pregătite pentru noi.
Avem mărirea subarborelui.
Ce mă lasă asta să fac?
Este relevant pentru arborii AVL.  Ei
bine, îmi permite să păstrez înălțimea.
Trebuie să pot calcula
înălțimea unui nod.
Asta, în general,
necesită timp liniar,
pentru că trebuie să mă uit la
toate căile în jos --
toate frunzele
din acel subarbor.
Dar înălțimea este o
proprietate subarbore--
deci, da-- înălțime.
De ce?
Pentru că-- permiteți-mi să-l
scriu aici--
node.height este egal cu 1 plus
max de node.left.height
și node.right.height
și de max.
Lasă-mă să pun asta într-o cutie.
Această ecuație, sau presupun că
este o operațiune de atribuire--
acesta este un 1--
este lucrul pe care l-am
făcut iar și iar.
Când am spus care este
înălțimea acestui nod,
tocmai v-ați dat seama
, nu?
Ați luat înălțimea
subarborelui din stânga maximă
cu înălțimea
subarborelui din dreapta
și ați adăugat 1 pentru a ține cont
de aceste margini.
Deci aceasta este o
regulă generală de actualizare.  Se
potrivește cu acest
model de proprietate subarboresc.
Dacă am proprietatea
stânga și dreapta,
o pot calcula pentru nod.
Și acest lucru necesită
timp constant pentru a face acest lucru.
Și deci este o proprietate subarbore.
Și astfel pot menține, prin
toate lucrurile pe care le fac,
înălțimea fiecărui nod.
Apropo, de fiecare dată când
fac o rotație,
va trebui și să-mi
actualizez proprietățile subarborelui.
Când rotesc această margine, A
nu se schimbă, B nu se schimbă,
C nu se schimbă.
Deci e bine.
Dar subarborele lui x se schimbă.
Acum are y.
Nu a fost înainte.
Așa că va trebui să
actualizăm și creșterea aici
în y.
Și va trebui să
actualizăm creșterea în x.
Și va
trebui să actualizăm

în cele din urmă creșterea tuturor strămoșilor lui x.
Deci rotația este
doar schimbarea locală a
unui număr constant de pointeri.
Așa că de obicei mă gândesc la rotații
ca având timp constant.
Dar în cele din urmă,
va trebui să facem...
acesta este un timp constant la nivel local.
Dar va trebui să actualizăm
strămoșii h pentru
a stoca toate... menține toate
creșterile noastre la zi.  Ne
vom face griji pentru asta mai târziu.
În regulă, atât de grozav.
Acum avem înălțimea
tuturor nodurilor.
Putem calcula deformarea
tuturor nodurilor, cool.
Avem această operație de rotație.
Și vrem să menținem această
proprietate de echilibrare a înălțimii.
Înălțimea nodului stâng -- la stânga
și la dreapta fiecărui nod --
este plus sau minus 1, sau 0.
Cool, așa că am spus aici
undeva, ori de câte ori noi--
deci singurele lucruri
care schimbă arborele
sunt atunci când inserăm
sau ștergem  un nou nod.
Și modul în care
le-am implementat până acum
este să adăugați sau să eliminați o frunză.
Așa că ar trebui să ne gândim în continuare
la adăugarea sau eliminarea
unei frunze.
Problema este că, atunci când
adaug o frunză nouă,
acum poate că acest copac este
mai înalt decât înainte.
Deci, un nod de aici poate să nu
mai fie echilibrat pe înălțime.
Dar, deoarece înălțimea este
o proprietate subarbore,
singurele noduri pe care
trebuie să le verificăm sunt
cele de pe această cale strămoșilor.
Și există doar log n dintre ele,
pentru că acum înălțimea este log n.
Asta tocmai am dovedit atâta
timp cât avem această proprietate.
Acum, acum nu o
avem pentru, cum ar fi,
poate aceste câteva noduri.
Dar a fost cu mult n înainte.
Este cel mult log n--
2 log n plus 1 chiar acum,
pentru că tocmai am adăugat un nod.
Deci, ceea ce vreau să fac este
să verific toate aceste
noduri strămoși în succesiune de
jos în sus și să găsesc
unul care nu este echilibrat.
Deci, să luăm cel mai mic
nod dezechilibrat.  O să-l
numesc x.
Acum, pentru că doar inserăm
sau ștergem o singură frunză,
este dezechilibrat doar
cu 1, pentru că am
schimbat doar înălțimea--
o înălțime a crescut cu 1 sau
o înălțime a scăzut cu 1.
Și înainte, toate declinurile noastre
erau  plus sau minus 1, sau 0.
Așa că acum, este-- cazul rău
este când este plus sau minus 2.
Dacă se întâmplă să fie încă în
acest interval pentru toate nodurile,
suntem fericiți.
Dar dacă se află în afara acestui interval,
va fi doar cu 1.
Deci, aceasta înseamnă că declinarea
este n plus 2 sau minus 2.
Și să presupunem că
este 2 prin simetrie.
Deci imaginea mea este...
Voi desena o
săgeată dublă dreapta
pentru a spune că acest subarboresc este cu
2 mai mare decât acest subarbor.
OK, așa că e rău și
vrem să o reparăm.
Lucrul evident de făcut
este să rotiți această margine.
Pentru că asta va face ca asta...
aceasta este prea mare
și aceasta este prea scăzută.
Deci, dacă ne rotim, aceasta
ar trebui să scadă cu 1
și aceasta ar trebui să crească cu 1.
Și asta funcționează de cele mai multe ori.
Deci cazul unu este declinul lui y.
Ce este y?
Vreau ca y să fie
copilul potrivit al lui x.
Pentru că avem o înclinație pozitivă,
știm că există un copil potrivit.
Acum, pentru că acesta a fost cel
mai jos nod rău,
știm că y este de fapt bun.
Fie este greu --
sau chiar cei doi subarbori
au aceeași înălțime --
sau lasă greu.
Cazurile ușoare
sunt când declinarea lui y
este fie 1, fie 0,
pe care le voi desena.
Așadar, o săgeată dublă la dreapta, să
spunem o singură săgeată la dreapta--
așa că voi
adăuga câteva etichete aici
pentru a face această
imagine consistentă--
k plus 1, k plus 2.
Călăresc pe înălțimi.
Deci acesta este un exemplu în
care C este mai înalt
decât B. A și B au
aceeași înălțime.
Și apoi, dacă calculezi
înălțimile aici sus,
într-adevăr, acesta
se înclină corect.
Acesta este înclinat de două ori
drept.
Pentru că acesta
are înălțimea k plus 1.
Acesta are înălțimea k minus 1.
Asta e rău.
Dar dacă facem această
rotație corectă pe x,
obținem exact ceea ce ne dorim.
Deci voi copia doar
etichetele pe A, B, C--
avem k minus 1,
k minus 1 și k--
și apoi recalculam.
Asta înseamnă că acest
tip are înălțimea k,
acesta are înălțimea k plus 1.
Și acum, toate nodurile din această
imagine pe care le-am evidențiat--
A, B și C nu s-au schimbat.

Înainte erau echilibrate pe înălțime.
Încă sunt.
Dar acum, x și y--
x nu era
echilibrat pe înălțime înainte, y era.
Acum, atât x cât și y
sunt echilibrate pe înălțime.
Acesta este cazul unu.
În cazul doi,
declinarea lui y este plată,
ceea ce înseamnă că acesta
este un k și acesta este un k și
acesta este un k plus 1
și acesta este un k plus 2.
Dar totuși, toate
nodurile sunt echilibrate--
înălțime echilibrată.
Sunt încă plus sau minus 1.
Deci acestea sunt cazurile ușoare.
Din păcate,
există un caz greu -
cazul trei.
Dar există doar unul și
nu este cu atât mai greu.
Deci este atunci când declinarea
lui y este minus 1.
În acest caz, trebuie să ne
uităm la copilul stâng al lui y.
Și pentru a fi alfabetic, voi
redenumi asta în z.
Deci, aceasta, din nou,
este dublă săgeată dreapta.
Acesta este acum săgeata stângă.
Și aceasta este litera y.
Și astfel avem potențiali subarbori A, B, C și D care
atârnă
de ei.
Și voi eticheta
culmile acestor lucruri.
Acestea sunt fiecare k
minus 1 sau k minus 2.
Acesta este k minus 1.
Și acum, calculați interiorul.
Deci aceasta va ajunge la înălțimea k
pentru ca aceasta să fie lăsată înclinată.
Deci, acesta este k plus 1
și acesta este k plus 2.
Dar problema este că acesta
este cu 2 mai mare decât acesta.
Înălțimea lui z este cu 2 mai mare
decât înălțimea lui A. În
acest caz, dacă
fac această rotație,
lucrurile se înrăutățesc, de fapt.
Îți voi spune doar că ceea ce
trebuie să faci este...
acesta este singurul lucru pe care
trebuie să-l memorezi.
Și lasă-mă să trag rezultatele.  De
asemenea, vă puteți gândi la asta
ca la redesenarea arborelui astfel.
Dar este mai ușor din
perspectiva analizei
să te gândești la asta
ca două rotații.
Atunci putem doar reduce.
Atâta timp cât știm
cum funcționează rotațiile,
atunci știm că
acest lucru funcționează -- „
funcționează”, adică
păstrează ordinea de traversare
și putem menține
toate creșterile.
Deci acum, dacă copiez peste aceste
etichete-- etichetele de înălțime--
am k minus 1.
Am, pentru acești doi tipi,
k minus 1 sau k minus 2. Cel
mai mare este k minus 1.
Acesta este k minus  1.
Și așa va fi k.
Acesta va fi k.
Acesta va fi k plus 1.
Și iată, avem
un arbore frumos, echilibrat în înălțime
în toate cele trei cazuri
pentru acest nod.
Acum, acesta a fost cel mai de jos nod.
Odată ce îl actualizăm pe
acesta, s-ar putea să
am schimbat
înălțimea rădăcinii.
Înainte era k plus
2, acum este k plus 1.
Sau uneori, îl păstrăm la
fel, ca peste în acest caz.
Și acum, trebuie să
verificăm părintele.
Poate că părintele
este dezechilibrat.
Și continuăm să
urcăm nodul
și, de asemenea, menținem toate
creșterile pe măsură ce mergem.
Apoi, vom ține evidența
înălțimii și a dimensiunii subarborelui,
dacă le dorim, sau orice
alte creșteri.
Și după operațiunile de ordin h
, vom
avea restaurat
proprietatea de echilibrare a înălțimii, ceea ce
înseamnă că până la capăt,
h este egal cu jurnalul de ordine n.
Și astfel, toate operațiunile noastre
acum sunt în mod magic jurnalul de comenzi n.