Träd, röd-svarta träd

"Hej, Amigo!"

"Hej Rishi!"

"Jag hittade mina gamla anteckningar där borta och förberedde en del intressant material åt dig. Jag tror att du kommer att vara intresserad av att höra det."

"Låt oss höra det. Du hittar alltid något intressant som senare visar sig vara väldigt användbart."

"OK. Idag vill jag berätta om träd , så jag börjar med grafer ."

" En graf är ett system av punkter och linjer som förbinder dem. Punkterna kallas grafens hörn, och linjerna kallas grafens kanter. Till exempel:"

"En graf är mycket bekväm att använda som en matematisk modell för olika verkliga processer och uppgifter. Många olika uppgifter och algoritmer har uppfunnits för grafer, så de används ganska ofta."

" Anta till exempel att hörn är städer och kanter är vägar. Att sedan söka efter den kortaste vägen mellan städer blir: " med en graf, hitta den kortaste vägen mellan två hörn".

"Men vägen från A till B är inte alltid densamma som vägen från B till A. Så ibland är det att föredra att ha två olika linjer. För att göra detta ersätts linjerna (kanterna på grafen) med pilar. I med andra ord, grafen kan ha två pilar: en från A till B och en annan från B till A."

"Om grafen använder pilar, kallas den en riktad graf ; om den bara har linjer, kallas den en oriktad graf ."

"Varje vertex kan ha sitt eget antal kanter. En vertex kan också inte ha några kanter alls. Omvänt kan en vertex vara ansluten med kanter till varannan vertex.  Om varje par av hörn i en graf är förbundna med en kant, då det kallas en komplett graf. "

"Om du kan använda kanter för att nå varje hörn i en graf, så kallas det en sammankopplad graf. En graf som har tre separata hörn och inga kanter är fortfarande en graf, men vi kallar det en frånkopplad graf."

"För att bilda en sammankopplad graf från N hörn behöver du minst N-1 kanter. Denna typ av graf kallas ett träd."

"Dessutom väljs vanligtvis en vertex som trädets rot , och resten förklaras vara grenar. Trädgrenar som inte har sina egna grenar kallas löv . Till exempel:"

"Om varje element i trädet har två barn, så kallas det ett binärt träd. Med andra ord kan det finnas antingen 0 eller 2 grenar. Du kan se ett binärt träd uppe till höger."

" Ett träd kallas ett komplett binärt träd när varje gren har 2 barn, och alla löv (topp utan barn) är på samma rad."

"Till exempel:"

"Varför behövs dessa träd?"

"Åh, träd används på många ställen. I allmänhet är binära träd sorterade strukturerade data."

"Vad är det?"

"Ja, det är väldigt enkelt. Vi lagrar ett visst värde i varje vertex. Och varje element följer en regel: värdet som lagras i det högra barnet måste vara större än värdet som lagras i vertexet, och värdet som lagras i det vänstra barnet måste vara mindre än värdet som lagras i vertexet.  Denna ordning gör det möjligt att snabbt hitta de element i trädet som du behöver."

"Kan du klargöra vad det betyder?"

"Trädelement sorteras vanligtvis genom att lägga till. Anta att vi har 7 element: 13, 5, 4, 16, 8, 11, 10"

"Så här läggs elementen till i trädet."

"Om vi ​​letar efter siffran 7 i det här trädet, så här kommer sökningen att gå"

"0) Börja vid roten."

"1a) Är 7 lika med 13? Nej"

"1b) Är 7 större än 13? Nej, så vi flyttar till vänster underträd."

"2a) Är 7 lika med 5? Nej."

"2b) Är 7 större än 5? Ja, så vi flyttar till höger underträd."

"3a) Är 7 lika med 8? Nej"

"3b) Är 7 större än 8? Nej, så vi flyttar till vänster underträd."

"4a) Det finns inget vänster underträd, vilket betyder att siffran 7 inte finns i trädet."

"Ah. Med andra ord, vi behöver bara kontrollera hörnen på vägen från roten till den blivande platsen för det önskade numret. Ja, det är verkligen snabbt."

"Dessutom, om trädet är balanserat behöver du bara passera cirka 20 hörn för att söka en miljon element."

"Jag håller med - det är inte särskilt många."

"Vad menar du med balanserat träd?"

"Ett träd som inte är förvrängt, det vill säga som inte har långa grenar. Om elementen till exempel redan var sorterade när vi byggde trädet, så skulle vi ha gjort ett väldigt långt träd som består av en gren. "

"Hmm. Du har rätt. Så vad gör vi?"

"Som du säkert redan har gissat har det mest effektiva trädet grenar som är ungefär lika långa. Sedan kastar varje jämförelse bort den största delen av det återstående underträdet."

"Så vi måste bygga om trädet?"

"Japp. Det måste vara "balanserat" - för att göras så nära ett komplett binärt träd som möjligt."

"För att lösa detta problem uppfanns självbalanserande träd.  Om trädet blir förvrängt efter att ha lagt till ett element, ändrar det elementen något för att göra allt OK.  Här är ett exempel på balansering:"

"Några av dessa träd är kända som rödsvarta träd ."

"Varför kallas de röd-svarta?"

"Deras uppfinnare ritade alla hörn med två färger. Den ena färgen var röd och den andra var svart. De olika hörnen lyder olika regler. Detta utgör hela grunden för balanseringsproceduren."

"Till exempel:"

"Så vad är dessa regler?"

"1) En röd vertex kan inte vara barnet till en röd vertex."

"2) Det svarta djupet för varje blad är detsamma (svart djup hänvisar till antalet svarta hörn på banan från roten)."

"3) Trädets rot är svart."

"Jag kommer inte att förklara hur det här fungerar - ditt huvud exploderar förmodligen redan."

"Ja. Min processor ger ifrån sig lite rök."

"Här är en länk till dig. Om du vill kan du läsa mer om det här."

Länk till ytterligare material

"Och nu, gå och ta en paus."