"Hej, Amigo!"
"Hej, Rishi!"
"Jeg fandt mine gamle notater derovre og forberedte noget interessant materiale til dig. Jeg tror, du vil være interesseret i at høre det."
"Lad os høre det. Du finder altid noget interessant, som senere viser sig at være meget nyttigt."
"OK. I dag vil jeg fortælle dig om træer , så jeg vil begynde med grafer ."
" En graf er et system af punkter og linjer, der forbinder dem. Punkterne kaldes grafens toppunkter, og linjerne kaldes grafens kanter. For eksempel:"
"En graf er meget praktisk at bruge som en matematisk model til forskellige processer og opgaver i den virkelige verden. Mange forskellige opgaver og algoritmer er blevet opfundet til grafer, så de bruges ret ofte."
" Antag for eksempel, at toppunkter er byer, og kanter er veje. Så bliver søgning efter den korteste vej mellem byer: «med en graf, find den korteste vej mellem to hjørner».
"Men stien fra A til B er ikke altid den samme som stien fra B til A. Så nogle gange foretrækkes det at have to forskellige linjer. For at gøre dette erstattes linjerne (kanterne af grafen) med pile. I med andre ord kan grafen have to pile: en fra A til B og en anden fra B til A."
"Hvis grafen bruger pile, så kaldes den en rettet graf ; hvis den kun har linjer, så kaldes den en urettet graf ."
"Hvert toppunkt kan have sit eget antal kanter. Et toppunkt kan heller ikke have nogen kanter overhovedet. Omvendt kan et toppunkt være forbundet med kanter til hvert andet toppunkt. Hvis hvert par af toppunkter i en graf er forbundet med en kant, så det kaldes en komplet graf. "
"Hvis du kan bruge kanter til at nå hvert knudepunkt i en graf, så kaldes det en forbundet graf. En graf, der har tre separate hjørner og ingen kanter, er stadig en graf, men vi kalder det en afbrudt graf."
"For at danne en forbundet graf ud fra N hjørner skal du have mindst N-1 kanter. Denne type graf kaldes et træ."
"Desuden vælges normalt ét toppunkt til at være træets rod , og resten erklæres for at være grene. Trægrene, der ikke har deres egne grene, kaldes blade . For eksempel:"
"Hvis hvert element i træet har to børn, så kaldes det et binært træ . Med andre ord kan der være enten 0 eller 2 grene. Du kan se et binært træ øverst til højre."
" Et træ kaldes et komplet binært træ, når hver gren har 2 børn, og alle bladene (hjørnepunkter uden børn) er på samme række."
"For eksempel:"
"Hvorfor er der brug for disse træer?"
"Åh, træer bruges mange steder. Generelt er binære træer sorterede strukturerede data."
"Hvad er det?"
"Ja, det er meget simpelt. Vi gemmer en bestemt værdi i hvert toppunkt. Og hvert element følger en regel: værdien lagret i højre barn skal være større end værdien lagret i toppunktet, og værdien lagret i venstre barn skal være mindre end værdien gemt i toppunktet. Denne rækkefølge gør det muligt hurtigt at finde de elementer i træet, du har brug for."
"Kan du præcisere, hvad det betyder?"
"Træelementer sorteres normalt ved at tilføje. Antag, at vi har 7 elementer: 13, 5, 4, 16, 8, 11, 10"
"Her er, hvordan elementerne føjes til træet."
"Hvis vi leder efter tallet 7 i dette træ, så er det sådan, søgningen vil gå"
"0) Start ved roden."
"1a) Er 7 lig med 13? Nej"
"1b) Er 7 større end 13? Nej, så vi flytter til venstre undertræ."
"2a) Er 7 lig med 5? Nej."
"2b) Er 7 større end 5? Ja, så vi flytter til højre undertræ."
"3a) Er 7 lig med 8? Nej"
"3b) Er 7 større end 8? Nej, så vi flytter til venstre undertræ."
"4a) Der er intet venstre undertræ, hvilket betyder, at tallet 7 ikke er i træet."
"Ah. Med andre ord, vi behøver kun at kontrollere hjørnerne på stien fra roden til den ønskede placering af det ønskede tal. Ja, det er virkelig hurtigt."
"Hvis mere er, hvis træet er afbalanceret, så behøver du kun at passere gennem omkring 20 hjørner for at søge en million elementer."
"Jeg er enig - det er ikke ret mange."
"Hvad mener du med balanceret træ?"
"Et træ, der ikke er forvrænget, dvs. som ikke har lange grene. Hvis elementerne f.eks. allerede var sorteret, da vi byggede træet, så ville vi have lavet et meget langt træ bestående af én gren. "
"Hmm. Du har ret. Hvad gør vi så?"
"Som du sikkert allerede har gættet, har det mest effektive træ grene, der er omtrent lige lange. Så kasserer hver sammenligning den største del af det resterende undertræ."
"Så vi skal genopbygge træet?"
"Jep. Det skal være "afbalanceret" - for at blive lavet så tæt som muligt på et komplet binært træ."
"For at løse dette problem blev selvbalancerende træer opfundet. Hvis træet bliver forvrænget efter tilføjelse af et element, omorganiserer det elementerne lidt for at gøre alt OK. Her er et eksempel på balancering:"
"Nogle af disse træer er kendt som rød -sorte træer."
"Hvorfor kaldes de rød-sorte?"
"Deres opfinder tegnede alle hjørnerne ved hjælp af to farver. Den ene farve var rød, og den anden var sort. De forskellige hjørner adlyder forskellige regler. Dette danner hele grundlaget for afbalanceringsproceduren."
"For eksempel:"
"Så hvad er disse regler?"
"1) Et rødt toppunkt kan ikke være barnet af et rødt toppunkt."
"2) Den sorte dybde af hvert blad er den samme (sort dybde refererer til antallet af sorte hjørner på stien fra roden)."
"3) Træets rod er sort."
"Jeg vil ikke forklare, hvordan det her virker - dit hoved eksploderer sandsynligvis allerede."
"Ja. Min processor afgiver lidt røg."
"Her er et link til dig. Hvis du vil, kan du læse mere om det her."
"Og nu, tag en pause."
GO TO FULL VERSION