"Hei, Amigo!"
"Hei, Rishi!"
"Jeg fant mine gamle notater der borte og forberedte noe interessant materiale for deg. Jeg tror du vil være interessert i å høre det."
"La oss høre det. Du finner alltid noe interessant som senere viser seg å være veldig nyttig."
"OK. I dag vil jeg fortelle deg om trær , så jeg begynner med grafer ."
" En graf er et system av punkter og linjer som forbinder dem. Punktene kalles toppunktene på grafen, og linjene kalles kantene på grafen. For eksempel:"
"En graf er veldig praktisk å bruke som en matematisk modell for ulike prosesser og oppgaver i den virkelige verden. Mange forskjellige oppgaver og algoritmer er oppfunnet for grafer, så de brukes ganske ofte."
" Anta for eksempel at toppunkter er byer, og kanter er veier. Da blir søk etter den korteste veien mellom byer: «gitt en graf, finn den korteste veien mellom to hjørner».
"Men banen fra A til B er ikke alltid den samme som banen fra B til A. Så noen ganger er det å foretrekke å ha to forskjellige linjer. For å gjøre dette erstattes linjene (kantene på grafen) med piler. I med andre ord, grafen kan ha to piler: en fra A til B, og en annen fra B til A."
"Hvis grafen bruker piler, kalles den en rettet graf ; hvis den bare har linjer, kalles den en urettet graf ."
"Hvert toppunkt kan ha sitt eget antall kanter. Et toppunkt kan heller ikke ha noen kanter i det hele tatt. Omvendt kan et toppunkt være forbundet med kanter til annenhver toppunkt. Hvis hvert par av toppunkter i en graf er forbundet med en kant, så det kalles en fullstendig graf. "
"Hvis du kan bruke kanter for å nå hvert toppunkt i en graf, kalles det en koblet graf. En graf som har tre separate hjørner og ingen kanter er fortsatt en graf, men vi kaller det en frakoblet graf."
"For å danne en sammenkoblet graf fra N toppunkter trenger du minst N-1 kanter. Denne typen grafer kalles et tre."
"Dessuten velges vanligvis ett toppunkt for å være treets rot , og resten erklæres for å være grener. Tregrener som ikke har egne grener kalles blader . For eksempel:"
"Hvis hvert element i treet har to barn, kalles det et binært tre . Med andre ord kan det være enten 0 eller 2 grener. Du kan se et binært tre øverst til høyre."
" Et tre kalles et komplett binært tre når hver gren har 2 barn, og alle bladene (vertekser uten barn) er på samme rad."
"For eksempel:"
"Hvorfor trengs disse trærne?"
"Å, trær brukes mange steder. Generelt er binære trær sorterte strukturerte data."
"Hva er det?"
"Ja, det er veldig enkelt. Vi lagrer en viss verdi i hvert toppunkt. Og hvert element følger en regel: verdien som er lagret i høyre barn må være større enn verdien som er lagret i toppunktet, og verdien som er lagret i venstre barn må være mindre enn verdien som er lagret i toppunktet. Denne rekkefølgen gjør det mulig å raskt finne elementene i treet du trenger."
"Kan du avklare hva det betyr?"
"Treelementer sorteres vanligvis ved å legge til. Anta at vi har 7 elementer: 13, 5, 4, 16, 8, 11, 10"
"Her er hvordan elementene legges til treet."
"Hvis vi leter etter tallet 7 i dette treet, så er dette hvordan søket vil gå"
"0) Start ved roten."
"1a) Er 7 lik 13? Nei"
"1b) Er 7 større enn 13? Nei, så vi flytter til venstre undertre."
"2a) Er 7 lik 5? Nei."
"2b) Er 7 større enn 5? Ja, så vi flytter til høyre undertre."
"3a) Er 7 lik 8? Nei"
"3b) Er 7 større enn 8? Nei, så vi flytter til venstre undertre."
"4a) Det er ikke noe venstre undertre, noe som betyr at tallet 7 ikke er i treet."
"Ah. Med andre ord, vi trenger bare å sjekke toppunktene på banen fra roten til ønsket plassering av ønsket nummer. Ja, det er virkelig raskt."
"I tillegg, hvis treet er balansert, trenger du bare å passere rundt 20 hjørner for å søke etter en million elementer."
"Jeg er enig - det er ikke veldig mange."
"Hva mener du med balansert tre?"
"Et tre som ikke er forvrengt, dvs. som ikke har lange greiner. Hvis for eksempel elementene allerede var sortert da vi bygde treet, ville vi ha laget et veldig langt tre som består av én gren. "
"Hmm. Du har rett. Så hva gjør vi?"
"Som du sikkert allerede har gjettet, har det mest effektive treet grener som er omtrent like lange. Da forkaster hver sammenligning den største delen av det gjenværende undertreet."
"Så vi må bygge treet på nytt?"
"Jepp. Det må være «balansert» - for å gjøres så nært som mulig et komplett binært tre."
"For å løse dette problemet ble selvbalanserende trær oppfunnet. Hvis treet blir forvrengt etter å ha lagt til et element, omorganiserer det elementene litt for å gjøre alt OK. Her er et eksempel på balansering:"
"Noen av disse trærne er kjent som rød -svarte trær."
"Hvorfor kalles de rød-svarte?"
"Deres oppfinner tegnet alle hjørnene ved hjelp av to farger. Den ene fargen var rød, og den andre var svart. De forskjellige hjørnene følger forskjellige regler. Dette danner hele grunnlaget for balanseringsprosedyren."
"For eksempel:"
"Så hva er disse reglene?"
"1) Et rødt toppunkt kan ikke være barnet til et rødt toppunkt."
"2) Den svarte dybden til hvert blad er den samme (svart dybde refererer til antall svarte hjørner på banen fra roten)."
"3) Roten til treet er svart."
"Jeg vil ikke forklare hvordan dette fungerer - hodet ditt eksploderer sannsynligvis allerede."
"Ja. Prosessoren min avgir litt røyk."
"Her er en link til deg. Hvis du vil, kan du lese mer om det her."
"Og nå, ta en pause."
GO TO FULL VERSION