bine, hai să începem. Bine ați revenit la double06 astăzi, facem unele dintre cele mai tari structuri de date pe care le vom vedea în această clasă, poate unele dintre cele mai tari structuri de date vreodată arbori binari, uh, cu siguranță ați văzut copaci în multe forme în trecut, inclusiv în această clasă am vorbit să folosim arbori ca instrument de limitare inferioară pentru uh în modelul arborelui de decizie, dar această prelegere și următoarea prelegere vom construi o structură de date care este aproape superioară tuturor structurilor de date pe care le-am văzut și poate face aproape orice cu adevărat rapid, mai întâi reamintim toate structurile de date pe care le-am văzut până acum tablouri legate liste matrice dinamice matrice sortate tabele hash și cele două seturi de operații pe care suntem interesați să sprijinim cele două interfețe una a fost secvențele în care menținem articole într-o ordine specificată, dorim să putem insera un articol imediat după un alt articol sau să ștergem un articol din mijlocul listei și să putem accesa întotdeauna al-lea articol. Nu am văzut nicio structură de date bună pentru problema respectivă. ne pricepem foarte bine la inserarea și ștergerea la începutul sau la sfârșitul secvenței, dar nu am văzut nimic care să fie eficient la inserarea în mijlocul listei sau la ștergerea în mijlocul listei, lista legată nu puteți chiar și să ajungi la mijloc într-un timp mai puțin liniar, uh, poți ajunge la mijloc, dar dacă faci modificări, trebuie să faci această schimbare, care este foarte scumpă, așa că astăzi sau scuze următoarea prelegere pentru prima dată, le vom vedea pe toate. operațiuni eficiente Voi menționa obiectivul nostru unde eficient înseamnă logaritmic, așa că nu suntem la fel de buni ca listele legate și matricele dinamice la inserarea și ștergerea la sfârșit a celor de acolo pe care le obținem timp amortizat constant sau constant, dar până la acest factor de log vom obține tot ce este mai bun din toate lumile în care putem rezolva toate lucrurile, toate operațiunile care nu construiesc sau repetă prin întreaga structură, care desigur necesită timp liniar, dar le putem face pe toate celelalte în timp logaritmic pentru seturi de seturi. au fost menținute menținând o grămadă de articole care au chei intrinseci și dorim să căutăm după cheie, astfel încât tabelele hash sunt grozave dacă faceți căutări exacte doar dacă doriți să găsiți o cheie și să obțineți da sau nu, este acolo și dacă este acolo, dă-mi elementul care este ceea ce fac dicționarele Python și sunt grozave la inserarea și ștergerea, dar sunt foarte proaste la găsirea anterioară și la găsirea următoare, acesta este cazul nereușit dacă caut o cheie și nu este în structura mea aș dori să știu mai mult decât răspunsul nu, aș dori să știu care sunt elementele anterioare și următoare care sunt de fapt în structură, deci care sunt cele mai apropiate potriviri ale mele atunci când caut după cheie, aceasta este o interogare naturală și singura structură de date pe care o avem este bun la ea este o matrice sortată, deoarece căutarea binară ne oferă acest lucru dacă căutăm o cheie după căutare binară și nu găsim că poziția în care ajungem este chiar între cea anterioară și următoarea, dar bineînțeles tablourile sortate sunt groaznice pentru operațiunile dinamice pe care nu știm cum să le întreținem. în general, o ordine a elementelor în mod dinamic și ne permite totuși să facem lucruri foarte rapide, cum ar fi să ieșim din i și să găsim cheia anterioară, așa că acesta este obiectivul nostru, nu vom ajunge foarte bine la acest obiectiv astăzi, vom obține un lucru incomparabil numit înălțimea copacului și apoi, joi, vom putea termina și atinge acest obiectiv astăzi este doar în serviciul acestui obiectiv, așa că ceea ce este un arbore binar, permiteți-mi să trag un exemplu și apoi să-l definesc mai precis matematicienii Numiți asta un arbore binar înrădăcinat pentru că, în cazul în care ați văzut că în o42 spuneți că aici este o imagine, deci acesta este un exemplu de arbore binar, are o grămadă de noduri pe care le desenăm în cercuri, are elemente în noduri care dacă scriu ca litere aici, deci acesta este elementul a elementul b elementul c și are aceste legături între ele, este ca niște liste legate, dar, în general, un nod x va avea un pointer părinte, un indicator stânga și unul la dreapta cursorul drept copil și are, de asemenea, un element în interior, așa că voi vorbi despre node.left este un pointer la stânga nodul de aici jos node.right node.parent node.item îmi oferă, așa că dacă mă uit la nodul a elementul său este un, așa că permiteți-mi să vă desenez câteva exemple, bine, părintele unui nu este nimic, așa că numim un nod rădăcină, va fi un nod unic care nu are părinte, este trist să nu aveți părinți, dar gata atunci avem nodul b al cărui părinte este un nod c este părinte aparent este un nod d părintele său este nodul b e părintele său este b și nodul f părintele este d ordine alfabetică aici se întâmplă să fie ordonat după părinte, apoi am lăsat indicatori Voi face doar câteva dintre ele, așa că indicatorul din stânga al lui a este b indicatorul din dreapta al a Îmi pare rău b nodul uh, toate acestea ar trebui să fie note. sunt lucruri diferite uh indicatorul drept pentru a este c indicatorul stânga pentru b este d indicatorul drept pentru b este e și așa mai departe bine, cu alte cuvinte, fiecare dintre aceste linii este un indicator bidirecțional uh în această direcție este direcția părinte în această direcție este lăsată în acest caz, deoarece este bidirecțională, nu desenăm săgețile, doar desenăm linii nedirecționate, bine, acesta este, în general, cum arată un arbore binar, un invariant cheie este că dacă luați un nod și spuneți mergeți la indicatorul său din stânga copilul din stânga și apoi mergeți la părintele nodului respectiv, acesta ar trebui să fie același cu nodul din dreapta, așa că doar a spune că acestea sunt în părinte este întotdeauna inversul unei operații la stânga sau la dreapta, acest lucru este valabil și pentru scrieți bine și acesta este un arbore binar acum intuiția din ceea ce se întâmplă aici este că ai putea spune că suntem inspirați de o listă legată. Lista legată a avut o structură foarte asemănătoare, poate un articol sau există un nod, avea un element în el și avea un indicator următor și avea un indicatorul anterior, deci, într-un anumit sens, ceea ce suntem dacă este dublu legat, am avut un indicator anterior, a fost legat individual, aveam doar un indicator următor și dacă vă gândiți la limitele listelor legate, în special listele legate individual, dacă aveți doar un indicator pe fiecare nod puteți construi doar o listă și astfel rezultatul este uh, știți că acest nod va avea adâncime adâncime liniară înseamnă câți indicatori trebuie să urmez pentru a ajunge aici de la rădăcina structurii care pentru listele legate era capul a fost dublu legat, bine, pot avea un cap și o coadă și pot pune bidirecții aici, dar apoi elementul din mijloc are adâncime liniară, așa că nu există nicio modalitate de a ajunge acolo în mai puțin de timp liniar cu arbori binari, deoarece folosim doi Tipuri de indicatori următori la stânga și la dreapta putem construi un copac și știm că copacii în general au logaritmi pot avea înălțime logaritmică și astfel este posibil într-un arbore să ajungeți la orice nod pornind de la rădăcină în doar log n traversări, așa că aceasta este intuiția ce se întâmplă acum astăzi vom vorbi despre înălțimea unui copac, așa că permiteți-mi să definesc că voi avea nevoie de câteva definiții aici subarborele și înălțimea unui nod uh, așa că un copac se descompune în subarbori, de exemplu, subarborele înrădăcinat la b sau subarborele lui b este această porțiune a arborelui, deci este acel nod și toți descendenții acestui nod, astfel încât, pentru că avem părinți și copii, putem generaliza în sensul arborelui familial, putem vorbi despre strămoșii unui nod, deci strămoșii lui f sunt părinții săi bunicii săi străbunicii săi și așa mai departe împreună, toți aceștia se numesc strămoși, este a nu prea corespunde copacilor familiari, deoarece copacii familiali aveți doi părinți aici aveți doar un părinte unic sau săracii rădăcină nu are părinte și despre care vorbim este ca metaforele mixte frunzele copacului aceștia sunt oameni fără copii părinții se vor plânge de asta, dar mulți ca mulți dintre noi în această cameră nu avem încă copii, așa că ni s-au numit frunze, vă puteți spune părinți, hei, sunt doar o frunză, știi că suflă în vânt, așa că știi așa că sunt atât de multe metafore amestecate, dar întotdeauna desenăm copacii în jos, ca structura rădăcină a unui copac, totuși numim capetele rădăcinilor frunze care sunt pe sus jos oricum, asta sunt copaci pentru tine o mulțime de analogii distractive, bine, dar strămoșii sunt utili, descendenții sunt de asemenea utili, deci descendenții lui b sunt toți copiii săi și toți nepoții săi și până în jos, dar doar în subarborele, deci subarborele lui x este format din x și descendenții săi și ne gândim că x este rădăcina acelui subarbore, așa că uităm într-un fel de tot ce este în afara arborelui secundar atunci când vorbim despre arborele secundar al lui x, să vorbim despre adâncimea unui nod adâncimea nodului este Bănuiesc că numărul strămoșilor săi este corect, dar modul în care mă gândesc de obicei la el este numărul de muchii și în calea de la x până la rădăcină, astfel încât fiecare nod are o cale unică care merge în sus până când nu poate merge în sus deci adâncimea lui e este de două pentru că există două margini uh una două în calea de la rădăcină a la e, așa că poate voi scrie niște adâncimi uh adâncimea lui e este două adâncimea acestor tipi este o adâncime a rădăcinii este zero doi trei, deci acestea sunt adâncimea, voi curăța puțin asta, astfel încât să ne putem concentra pe imagine la înălțimea potrivită, astfel încât adâncimea se măsoară în jos, deoarece știm că dacă vă imaginați adâncimea în apă, aceasta este suprafața apă și apoi măsuram cât de adânc sunteți de la înălțimea suprafeței este în direcția inversă pe care o vom măsura de la nivelul frunzei în sus, deoarece frunzele sunt partea de jos a copacului, așa că înălțimea unui nod va fi numărul de margini în cea mai lungă cale descendentă, bine, care este același lucru cu adâncimea maximă a unui nod din subarborele lui x, să facem înălțimea în roșu, deci uh, cât de lungă este calea cea mai lungă de la f la un puț de frunze f este o frunză, așa că toate frunzele au adâncimea zero scuze, înălțimea zero, dă-o înapoi um d aici este așa că există două moduri de a coborî, asta nu se duce la o frunză uh, aceasta merge la o frunză și înălțimea ei este zero, deci această înălțime este una, există o margine la o frunză aici b are două frunze la care poate ajunge o luăm pe cea mai lungă, deci aceasta este lungimea două a, în mod similar, are înălțimea trei bine, deci înălțimea măsurăm în sus adâncimea măsuram bine în jos. Un lucru care ne pasă este doar înălțimea copacului general înălțimea rădăcinii și o voi numi asta h pentru că o vom folosi foarte mult și ceea ce vom realiza astăzi este toți acești timpi de rulare în loc să fie log n ei vor fi comandă h, așa că astăzi scopul nostru este să obținem toate operațiunile care ne interesează în ordinea tastei h și apoi următoarea prelegere vom garanta că h este întotdeauna log n și apoi vom obține log n timp, așa că trebuie să facem o o grămadă de muncă pentru a realiza bușteni n astăzi vom face treaba care este toată manipularea copacului și atâta timp cât copacul tău este frumos și puțin adânc, nu are înălțime mare dacă are înălțime logaritmică, totul va fi buștean n desigur că există copaci care sunt cu adevărat rău, putem avea un copac un copac ca acesta, care este în principiu o listă legată în care folosim doar indicatori din dreapta și toți indicatori din stânga nu sunt niciunul, așa că există înălțime, există copaci care sunt foarte înalți au înălțime mare um noi Vrem să le evităm, dar nu ne vom îngrijora până la următoarea întrebare de curs care este înălțimea nodului c înălțimea nodului c este zero, deoarece lungimea celei mai lungi căi, numărul de muchii din cea mai lungă cale descendentă este zero, da, noi" Numărând muchiile, nu vârfurile, da, așa că înălțimea copacului este, desigur, doar adâncimea, adâncimea maximă, cred că este corect, așa că înălțimea aici este trei și adâncimea maximă este îngrozitor de trei, așa că acestea se întâmplă să corespundă în cazul maxim. dar folosim înălțimea pentru a însemna întotdeauna maxim și de aceea vorbim despre înălțimea copacului adâncimea copacului nu este definită doar adâncimea notelor bine, cum folosim acești copaci pentru a reprezenta fie o secvență, fie un set, uh pretind că există o ordine naturală în copaci numită ordine de traversare a nodurilor sau a elementelor și arborele, așa că voi defini o anumită ordine, uh spunem în acest exemplu, să facem mai întâi exemplul, ordinea de traversare va fi f d b e a c simt ca eu Sunt la cursul de muzică, aceasta este chitara mea sau ceva de genul ăsta, dar nu sper că este o coincidență, deci care este această ordine, ceea ce aș dori să fac este să definesc recursiv o ordine în care rădăcina arborelui este undeva în mijloc și totul din subarborele din stânga este lăsat mai devreme în ordinea rădăcinii și totul din subarborele din dreapta este mai târziu, așa că puteți vedea aici c vine după a și apoi toate celelalte noduri vin înaintea a și recursiv dacă mă uit la un nod b acest nod b care apare aici e este la dreapta lui, dar este totul la stânga lui a, deci e este între b și a ar fi în stânga și apoi f și d sunt la stânga acestuia și din nou f vine înaintea lui d deoarece f este în subarborele din stânga al lui d ok, așa că spunem pentru fiecare nod, nodurile din punctul x din stânga sunt înaintea lui x, iar nodurile din punctul x din dreapta vin după x și aceasta definește în mod unic o ordine numită ordine de traversare se mai numește și ordinea de traversare în ordine, se numește în ordine, deoarece este în ordinea de traversare, deci este foarte circulară, dar este posibil să fi văzut traversarea în ordine, acesta este același lucru, există un algoritm foarte simplu pentru a calcula acest lucru dacă vreau să repet uh, haideți Numiți asta, da dacă vreau să iterez toate nodurile dintr-un subarboresc x înrădăcinat de x, doar iterez pe toate nodurile din subarborele din stânga, apoi scot x însuși, apoi iterez pe toate nodurile din subarborele din dreapta, bine, poate le-ați văzut acel algoritm înainte de aceasta este doar o altă modalitate de a codifica același lucru, rezultatul este că toate nodurile dintr-un subarboresc apar continuu fără întreruperi și apoi părintele părinte va veni înainte după, în funcție de dacă este copilul stâng sau drept, bine, așa și acum este doar o chestiune de conectare a punctelor pentru că reprezentăm o ordine și pentru secvența care va fi ordinea secvenței, dacă dorim să stocăm n articole x0 până la x1, vom construi un fel de arbore pe care îl vom merge pentru a pune x0 aici x1 aici x2 aici x3 aici x4 aici x5 aici puteți vedea că sunt foarte obișnuit să mă ocup de ordinele de traversare durează puțin timp uh, puteți vedea și aici, vom pune x1 pe acest nod x2 scuze x0 aici x1 aici x2 aici și așa mai departe, aceasta este aceeași ordine pe care am dat-o. Bine, pentru secvențele pentru seturi, această ordine va fi doar ordinea sortată și vom reprezenta în mod eficient ordinea sortată a cheilor, spunem crescătoare, dar înainte de a ajunge la asta, să vorbim despre diferite operații pe care le putem face doar jucându-ne cu ordinea de traversare și apoi le vom folosi pentru a construi secvența și a seta operațiile care ne pasă, așa că prima operație pe care o voi numi mai întâi subarbore pare adecvată că se numește primul, este primul, așa că dat fiind un nod pe care îl voi numi nod, acesta definește un subarboresc pe care de obicei desenăm subarbori ca triunghiuri care atârnă de nod, așa că aici aș scrie x și apoi există un subarboresc al tuturor descendenților de x, deci cu subarborele mai întâi, aș dori să spun, printre toate nodurile din acest subarboresc, care este primul în ordinea traversării, deci doar limitându-mă la acel subarbore, deci arborele acela, deci unde este în acest arbore, nota face parte de fapt din mulți subarbori întrebare bună uh f f este în subarborele lui f uh f este și în subarborele lui d f este în subarborele lui b așa cum am desenat f este în subarborele lui a este în subarborele exact al strămoșilor săi, dar în această operație, când definim nodul, nodul nostru definește doar un sub-arbore, este rădăcina unui singur sub-arbore și acesta este sub-arborele despre care vorbim și apoi vreau să știu printre toate acele noduri care include nodul în sine și alte lucruri, uh, care este primul în această ordine de traversare, este ca o practică cu ordinele de traversare, așa că unde ar trebui să caut acest nod, da, frunza cea mai din stânga din imagine, este aici, dar imaginile pot fi înșelătoare, vrem doar să mergem la stânga cât mai mult posibil când spun să mergi la stânga, vreau să spun că acest nod de iterație este egal cu nodul. stânga, te uiți doar la definiția noastră, toate nodurile din stânga vin înaintea x și toate nodurile din dreapta, așa că trebuie să fie în subarborele din stânga dacă există unul uh bineînțeles că nu putem face asta pentru totdeauna, așa că spuneți până când vom cădea din copac, ceea ce înseamnă că nodul nu este în regulă, dar ne-am oprit înainte să se întâmple asta, așa că este ca uh direcțiile de genul oh, continuați să conduceți până când vedeți magazinul și este blocul de dinainte că e bine, că nu este foarte util, așa că continui să iterați nodul este egal cu niciun punct rămas până când nodul devine niciunul și apoi anulați un pas, bine, știți cu toții cum să programați că nu este greu, astfel încât să nu dureze. -nici un nod care ar putea fi de fapt rădăcina, ar putea fi un nod, poate că nu are copii din stânga, dar în acest caz susțin că nodul este primul în ordinea sa de traversare a subarborelui, deoarece dacă nu există noduri în stânga care vin înainte de x atunci x este de fapt primul în regulă și asta este, uh return nodul, așa că modific nodul pe loc aici și ultimul înainte de a nu atinge niciunul, acesta este minimul care este primul element în ordinea traversării, în mod similar, puteți defini subarborele ultimul bine. haideți să facem un nod succesor mai interesant, așa că, în acest caz, vreau să știu care este următorul nod după în ordinea generală de parcurgere a arborelui, bine aici, mă limitam la un singur sub arbore acum, mă gândesc la întregul arbore din Întreaga ordine de traversare și având un nod, vreau să știu care urmează să numesc succesorul. Simt că ar trebui să fac un fel de glumă cu familia regală acum, dar nu știu cum, um, așa că fiecare nod are un succesor unic, hai să facem, hai să facem. faceți câteva exemple, astfel încât să putem începe cu f succesorul lui f dacă doar indexăm în această listă succesorul este bine succesorul lui d este b succesorul b este ușor ok este foarte ușor să citesc succesorii off când am ordinea de traversare scrisă dar să ne gândim cum să o facem în arbore, bine, hai să vedem că vor fi două cazuri dacă mă uit la succesorul lui a are un copil potrivit și, în acest caz, copilul potrivit al lui a este succesorul, dar asta nu este întotdeauna este cazul, nu am un exemplu bun, dar dacă am avut un alt nod aici, să-l numim g uh, succesorul lui a este de fapt g dreapta, deoarece toate aceste elemente vin după a în ordine, dar care vine primul frunza cea mai din stânga bine, asta este problema pe care tocmai am rezolvat-o, așa că dacă a are un copil drept ceea ce ne dorim este frunza cea mai din stânga primul lucru din acel subarborel subarborele din dreapta subarborele din dreapta, deci acesta este cazul unu dacă uh node.right, deci dacă avem un drept copil, atunci ceea ce vrem este primul subarboresc al copilului potrivit. Grozav putem reduce la această altă operație, dar dacă nodul nu are un copil potrivit, de exemplu, ar putea fi o frunză, să spunem că luăm succesorul lui, adică nu trebuie să fie o frunză ar putea fi f care nu are copii ar putea fi d care are un singur copil, dar nu este un copil potrivit, deci care este succesorul lui f ei bine este d care în acest caz este părintele, dar nu este întotdeauna de exemplu dacă facem succesorul lui e, părintele său este de fapt mai devreme în ordine, deoarece e a fost un copil drept aici f a fost un copil stâng și deci părintele său a fost după ce succesorul lui d se întâmplă să fie b pentru că a fost copilul stâng al lui părinte bine, așa că pare a fi cazul ușor, dacă suntem copilul stâng al părintelui nostru, atunci succesorul nostru este părintele nostru, bine bazându-ne pe acest mic exemplu, dar putem argumenta în general într-o clipă care este succesorul lui e uh ei bine, nu este b pentru că asta vine mai devreme, de fapt, toate lucrurile din acest subarboresc în b vin mai devreme sau egale cu e um, așa că trebuie să continuăm să mergem în sus și apoi se dovedește că succesorul lui e este a deoarece acest subarbore a fost copilul stâng al lui a deoarece b a fost un copil stâng cu a, așa că strategia generală este să urcăm în copac până când suntem noi urcăm o traversare a cărei direcție inversă ar fi lăsată în regulă, așa că urcăm în copac când spun să merg sus, adică nodul este egal cu nodul.parent. iterație până când urcăm o ramură din stânga, așa că acest lucru ar însemna că nodul înainte de a face schimbarea nodul este egal cu node.parent node.parent.left bine, așa că putem verifica asta și apoi, după ce facem acea traversare, acel părinte este exact nodul pe care l-am" Caut bine de ce este adevărat în general, permiteți-mi să desenez o imagine mai generală, așa că începem de la un nod și să spunem că părintele lui este în dreapta, așa că vine mai târziu în ordine pentru o perioadă. facem succesor, așa că merge la stânga pentru un timp, așa că acestea sunt toate aceste noduri vor veni mai devreme în ordine, deoarece, prin definiție, totul din subarborele din dreapta vine după și la un moment dat avem un părinte care este la dreapta, ceea ce înseamnă că acest nod a fost copilul din stânga acestui părinte și acel nod, prin definiție, va veni după toate nodurile de aici și ar putea fi ceva între nod și acest strămoș bunic părinte numai dacă ar fi ceva în acest subarbore și suntem în cazul aici, unde nu există niciun subarboresc corect al nodului nostru original, deci aici ar fi toate nodurile dintre nod și aici, dar nu există și, prin urmare, acesta este succesorul, așa că acesta este un fel de argument general de ce văd asta funcționează o întrebare, da, plasată în ordinea traversării, astfel încât ordinea traversării nu este niciodată calculată în mod explicit ceea ce ni se învață este întotdeauna implicit că nu ne putem permite să menținem asta, cum spunem că o matrice este doar în capul nostru, poate o voi desena cu un nor în jurul lui, doar ne gândim că este în regulă, nu se află în computer în mod explicit în computer, tot ceea ce stocăm este acesta și motivul este că acest lucru este scump, nu putem menține o serie de lucruri și nu putem să le introducem în Mijloc, întrucât acest lucru este ieftin, îmi permit să mențin această structură și să fac toate aceste lucruri și, prin urmare, motivul pentru care vorbim despre aceste operațiuni este că ne lasă să manipulăm comanda sau, în acest caz, ne lasă să repetăm ​​comanda, așa că acesta a fost un algoritm pentru iterarea întregii comenzi, dar care durează timp liniar, acest lucru începea în ordine. Găsește-mă primul lucru în ordine și i s-a dat un nod Găsește-mă următorul cât timp durează aceste operațiuni cel mult la înălțime a întregului arbore, de fapt, va fi adâncimea primului nod, dar în cel mai rău caz, aceasta este înălțimea întregului arbore, în general, toate aceste operațiuni vor fi de ordinul h, trebuie să ne gândim la asta în fiecare caz, cu excepția pentru acesta, care este de ordinul n, deci repetarea prin tot, um, asta în acest caz, numim mai întâi subarborele, astfel încât să ia ordine h timp aici mergem în sus în copac în loc de jos, dar asta va costa exact înălțimea din nod se întâmplă să ne oprim devreme, dar în cel mai rău caz, ordinea h pentru toate acestea, toate operațiunile pe care le considerăm astăzi, vrem doar să obținem un ordin h legat și mai târziu vom lega h, așa că ideea este că acestea sunt rapide dacă h este mic ca log n acestea sunt aproape instantanee, în timp ce dacă ar trebui să actualizez ordinea de traversare explicită, să spunem ca o matrice, ar trebui să petrec timp liniar de fiecare dată când fac o schimbare și da, ar fi rapid să fac succesor dacă aș avea acest lucru stocat în mod explicit, dar menținându-l ar fi imposibil să-l menținem eficient ar fi imposibil întrebări întrebări da, bine, mișto, deci acestea au fost interogări pe care vreau să le urmăresc să văd ce urmează în secvența de traversare acum hai să vorbim despre schimbarea secvenței de traversare, deci acestea sunt operațiuni de inserare și ștergere, acestea vor fi corespund aproximativ cu inserarea la sau ștergerea la, dar ele nu sunt deloc, nu suntem chiar în lumea secvenței, în schimb, ne vom concentra pe inserarea sau ștergerea în mijlocul unui subarboresc, așa că voi avea două noduri, așa că în ordinea traversării, astfel încât nodul există deja în arbore, nou este un nod nou care nu există încă în arbore, de aceea îl numesc nou și ceea ce aș dori să fac este să insert nou imediat după nod și există o operație simetrică care este inserat înainte de a fi implementat aproape identic, așa că ne vom concentra doar după, așa că vreau să inserăm acest nou nod în ordinea traversării, care din nou este în capul nostru, totul este în balonul nostru de gânduri, asta este ceea ce vrem să realizăm și trebuie să o facem manipulând acest arbore și oricum schimbăm arborele, definește o nouă ordine de traversare, așa că poate să facem mai întâi un exemplu, de fapt, probabil că vreau ca această ordine universală să țină evidența asta, așa că hai să spunem primul lucru pe care vrem să-l facem uh este inserați g înainte de e vreau să ilustrez ambele operații inserați h după e a bine um deci inserați g înainte de e, așadar conceptual ceea ce vrem să facem este să inserăm g aici și modul, astfel încât ni se dă nodul e și avem având în vedere un fel de nod gol, mă refer la un nod care conține doar g, nu are încă nici un indicator și am dori să-l punem înaintea e unde ar trebui să-l pun copilul stâng, așa că acesta este un caz ușor dacă eu" Încerc să inserez înainte și nu există niciun copil stâng, inserați-l acolo dacă încerc să inserez după și nu există niciun copil din dreapta, inserați-l ușor acolo, așa că permiteți-mi să notez cazul unu, așa că aici îl inserăm după, deci dacă nu există uh right copilul a pus nou acolo bine, folosesc un limbaj informal aici pun acest nou nod acolo b în loc să scriu, de exemplu, node.write equals new, deoarece aceasta este o singură operație pe care trebuie să o faci este să setezi node.write equals to new dar trebuie, de asemenea, să setați părintele lui new să fie node.write, așa că, în loc să vă faceți griji cu privire la aceste două modificări ale pointerului, deoarece facem întotdeauna modificări bidirecționale ale pointerului, voi folosi doar pseudocod și apoi, în recitare, veți vedea codul python real asta face toate astea, uh, atunci există celălalt caz, așa că ar trebui să fie al doilea exemplu, inserați h după o inserare dreaptă h după a, deci avem deja un nod după a în copilul drept în acest subarboresc drept, deci unde vreau să pun h în raport cu o fântână ar trebui să fie la dreapta lui a, dar ar trebui să fie înainte de c ar trebui să fie la stânga lui c, așa că ar însemna că vrem să-l punem aici, bine în acest caz, a fost destul de ușor pentru că acest copac era mic unde vreau să-l pun în general bine oriunde subarborele îmi spune mai întâi să-l pun corect subarborele îmi va da succesorul acestea sunt toate un fel de paralele, um ne aflăm acum în cazul în care nodul nostru are un copil potrivit și apoi succesorul ne spune unde este succesorul este primul nod care este descendentul cel mai din stânga în subarborele din dreapta al nodului, bine, o mulțime de indicatoare de urmat în acea propoziție, dar este clar în imagine, așa că în acest caz am avut nod și nu a existat un copil potrivit, așa că doar am adăugat nou pentru a fi copilul potrivit, bine în celălalt caz, am avut un copil potrivit, așa că aici este nodul există uh, există acest nod aici node.right care acum presupunem că există și definește un întreg subarbore există acesta care este primul nod în ordinea traversării subarborelui, cunoscut și ca succesor al nodului, așa că voi numi acest succesor al nodului în ordinea traversării curente, dar bineînțeles că am dori să facem nou noul succesor a nodului, deci unde merge aici, vrem să-l adăugăm ca copil stâng la vechiul succesor, bine așa că puneți uh node ca deci luați succesorul și dacă vă uitați la codul pentru succesor suntem în acest caz, așa că știm va apela doar subtree primul din node.right și amintiți-vă că subtree a mers mai întâi la stânga cât de mult posibil, așa că ceea ce înseamnă că acest nod succesor este garantat să nu aibă un copil stâng dreapta, deoarece a fost definit mergând la dreapta o dată și apoi mergând. lăsat cât ai putea, așa că nu mai rămâne, ceea ce înseamnă că putem face încă unul rămas, doar adăugăm nou acolo și am terminat acum, dacă te uiți la ordinea de traversare, va fi nod, apoi nou, apoi vechiul succesor și apoi restul a acelui subarbore bine, e cam grozav în toate cazurile, vreau să spun că acesta a fost un timp constant aici, am petrecut timp constant după ce am sunat succesorul costuri succesorul costuri ordinul h timp deci aceasta este ordinea h nou nou bine pune nou acolo clar, bine, asta a fost inserarea hai să facem ștergerea corectă specificațiile și exemplul toate acestea vor avea două cazuri uh, așa că permiteți-mă oh, nu am actualizat, așa că acum h este după a, așa că ar trebui să fie așa, puteți verifica noua ordine de traversare a acestui arbore. exact în continuare, voi face câteva ștergeri, să ștergem mai întâi f și apoi vom face bine, acest lucru este confuz și apoi vom șterge a, deci unde este f presupunem că ni se dă un indicator pentru a face acest nod bine, este o frunză, așa că dacă vreau să-l șterg, doar îl șterg, frunzele sunt ușor de șters, nu mai este de lucru, așa că asta înseamnă că elimin indicatorul de la d la f bine, doar ștergem asta omule, bine, acum, aici este unul mai complicat să presupunem că vreau să șterg rădăcina copacului, acesta este cel mai greu caz, dar în general ar fi undeva între frunză și rădăcină, așa că dacă vreau să șterg un, dacă tocmai l-am șters atunci dintr-o dată apar aceste indicatoare către nicăieri și deconectez arborele în două părți, nu vreau să fac asta, trebuie să- mi țin copacul conectat, așa că o să joc acest truc, care este că uit dacă folosesc succesorul sau predecesorul predecesor deci mă voi uita la un succesor pe care l-am definit deja și acolo prin predecesor, așa că mă voi uita la predecesorul lui a care este e puteți verifica că aici cel dinaintea a este e acesta este în stânga subtree uh, găsește-mă cel mai potrivit articol, continuă până când nu pot, așa că acum tipii ăștia sunt adiacenți în ordine și sunt pe cale să elimin un din comandă, astfel încât să pot înșela momentan și să le schimb etichetele. să șterg a și e aici și să pun e după un de ce pentru că se mișcă în jos în copac și dacă ajung la frunză am terminat, așa că nu am terminat pentru că aceasta nu este o frunză, așa că din nou mă uit la a lui predecesorul este acum g predecesorul sperăm că este întotdeauna în uh mai jos în copac și apoi schimb a cu g bine am păstrat ordinea de traversare, cu excepția cazului în care a cade doar prin mutarea unui mai devreme în ordinea aici și acum a este o frunză și îl pot șterge bine, așa că asta vom urmări acum, în realitate, este puțin dificil, uneori, trebuie să folosim predecesori, uneori, trebuie să folosim succesorul, bine, deci cazurile sunt dacă nodul este o frunză, doar detașați-l de părinte ușor, acesta este un fel de cazul nostru de bază în recursivitate, altfel există două cazuri, dacă da, dacă nu suntem o frunză, înseamnă că avem un copil stâng sau un copil drept sau ambele vor fi cazul ușor, dar în general eu fie există un copil stâng, fie există un copil drept în oricare dintre cazuri, voi fi fericit, așa că nu am nevoie de ambele cazuri, bine, ce să fac dacă am un copil stâng care îmi garantează că dacă predecesorul nodului se află în interiorul acelui sub-arboresc din stânga, ceea ce înseamnă că este mai jos în arbore dacă nu aș avea un copil stâng, predecesorul ar fi de fapt mai sus în arbore și nu vreau să merg mai sus, bine, așa că dacă am un copil stânga știu că predecesorul este mai jos și așa că voi schimba articolul meu conținutul nodului meu cu elementul predecesorului meu și apoi voi șterge recursiv predecesorul, bine, acesta este cazul pe care l-am uitat în acest cod în acest exemplu pentru că întotdeauna am avut un copil stâng dacă avem un copil drept, dar niciun copil stâng, facem doar invers, schimbăm cu succesorii noștri și apoi ștergem succesorul în ambele cazuri, vom merge în jos și deci dacă începem de la un nodul ca traseul de fiecare dată când facem această operație, coborâm și apoi coborâm și, în general, vom continua să coborâm reluând de unde am rămas, ceea ce înseamnă că timpul total pe care îl petrecem este proporțional cu înălțimea Arborele în cel mai rău caz întrebarea corectă, așa că nu obișnuiam să aibă un copil potrivit, așa că schimbăm identitățile nodurilor atunci când facem asta pentru că nu am mutat acest cerc, cercul a rămas pe loc și ceea ce am schimbat a fost elementul care a fost stocat în acel cerc, așa că dacă numiți acest nod e sau a, nu contează cu adevărat, este doar nota rădăcină, în regulă, așa că vom juca o mulțime de aceste trucuri de a muta elementele în jur. Până acum nu am făcut asta, doar am creat noduri și le-am plasat undeva, dar acum suntem în această operație de ștergere este prima dată când schimbăm ceea ce este stocat în noduri, dar încă putem defini traversarea comandă corect, ordinea transversală a acestui arbore este dbgehc, care ar trebui să fie ceea ce vom obține aici dacă șterg f și a și îmi pare rău, arborii can f nu vor păstra conexiunile, acesta este doar numele jocului în care suntem, trebuie să permitem asta, altfel putem" nu fac nimic care este versiunea scurtă, bine, bine în ultimele minute, permiteți-mi să vorbesc despre cum luăm acești copaci și implementăm un set sau o secvență. Bine, am făcut deja aluzie la asta, așa că pentru o secvență facem doar ordinea de traversare egală cu ordinea în care încercăm să reprezentăm ordinea secvenței și dacă încercăm să sursăm elementele set cu chei, vom face ca ordinea de traversare să fie egală cu ordonată prin creșterea tastei, creșterea tastei elementului oarecum, asta este, dar atunci avem nevoie să ne gândim la cum implementăm toate aceste operațiuni, așa că poate cel mai lămuritor este pentru începători găsirea unei chei într-un arbore, așa că aceasta va corespunde căutării binare dacă caut o cheie, să spunem că caut g. cheie și știu că acest lucru poate fi greu în acest exemplu, poate le voi înlocui pe toate cu numere, astfel încât să mă pot gândi la valorile cheii, bine, deci să spunem 1 7 12 17 19 și 23. Acesta este acum în ordinea cheilor dacă vă gândiți la Ordinea de traversare, proprietatea este că toate cheile din subarborele din stânga al rădăcinii sunt mai mici decât rădăcina, iar rădăcina este mai mică decât toate cheile din subarborele din dreapta și recursiv până în jos, aceasta este ceva numit proprietatea arborelui de căutare binar bst proprietățile acestea aici le numim seturi de arbori binari sau seturi de arbori binari, dar sunt cunoscute și în literatură ca termen de arbori de căutare binari pe care poate l-ați auzit înainte, așa că acesta este un caz special a ceea ce facem acolo unde suntem stochează cheile în ordine și apoi dacă vreau să caut o cheie ca uh 13 compar acea cheie cu rădăcina, văd oh, nu este egală și este la stânga pentru că este mai mică de 17. deci 13 rămâne de aici 13 este dreptul de 7 13 este dreptul de 12 și așa că știu că aici ar aparține 13, dar nu există nici un copil potrivit acolo și așa că știu că în find nu am returnat nimic dacă făceam find anterior, aș returna această notă pentru că am încercat pentru a merge la dreapta ultima dată înainte de a cădea din copac, încercam să merg la dreapta și, prin urmare, ultima notă pe care o aveam a fost elementul anterior, dacă încercam să definesc în continuare ce aș face, aș lua doar acest nod și calculează succesorul său, ceea ce știm deja cum să-l facem și se întâmplă să fie rădăcina în regulă, așa că acum pot face aceste căutări inexacte când găsesc precedentul și găsesc următorul când cad din copac, găsesc fie anterior, fie următorul și apoi, cu predecesorul sau succesorul, îl pot găsi pe celălalt în regulă, așa că așa putem găsi și găsi anterior și găsim următor pentru a face secvențe avem nevoie de puțin mai multă muncă, o vom face data viitoare