[Powered by Google Translate] Hur skulle du representerar alla dina familjemedlemmar i en dator? Vi kan helt enkelt använda en lista, men det finns en tydlig hierarki här. 

Låt oss säga att vi börjar med din gammelmormor, Alice. Hon har 2 söner, Bob och din farfar, Charlie. Charlie har 3 barn, din farbror, Dave, din faster, Eve, och din far, Fred. Du är Freds enda barn. 

Varför skulle organisera dina familjemedlemmar på detta sätt vara bättre än den enkla listan representation? Ett skäl är att denna hierarkiska struktur, kallas "träd", innehåller mer information än en enkel lista. Vi vet att släktskap mellan alla bara genom att undersöka trädet. Det kan också påskynda look-up tid enormt, om träd data sorteras. 

Vi kan inte dra nytta av det här, men vi får se ett exempel på detta snart. Varje person representeras av en nod i trädet. Noder kan ha underordnade noder liksom en överordnad nod. Dessa är de tekniska termer, även om man använder träd för saker förutom familjer. Alice nod har 2 barn och inga föräldrar, medan Charlies nod har 3 barn och 1 förälder. 

Ett löv nod är en som inte har några barn på ytterkanten av trädet. Den översta nod i trädet, rotnoden, har ingen förälder. 

En binär träd är en specifik typ av träd, i vilket varje nod har, på sin höjd 2 barn. Här är struct av en nod i ett binärt träd i C. Varje nod har en del data i samband med det och 2 pekare till andra noder. 

I vårt släktträd, tillhörande data var varje persons namn. Här är det en int, men det kan vara vad som helst. Som det visar sig, ett binärt träd skulle inte vara en god representation för en familj, eftersom människor har ofta mer än 2 barn. 

En binär sökträdet är en speciell, ordnad typ av binära träd som tillåter oss att titta på värden snabbt. Du kanske har märkt att varje nod under roten av ett träd är roten till ett annat träd, en så kallad "underträd." Här, är roten av trädet 6, och dess barn, 2, är roten till ett underträd. 

I ett binärt sökträd alla värden i en nod rätt underträd är större än nodens värde. Här: 6. Tja, värdena i en nod vänstra underträd är mindre än nodens värde. Om vi ​​behöver för att hantera dubbletter, vi kan ändra någon av dem till en lös ojämlikhet, betyder identiska värden kan falla antingen på vänster eller höger, så länge vi är konsekventa om det hela. Detta träd är ett binärt sökträd eftersom den följer dessa regler. 

Detta är hur det skulle se ut om vi vände alla noder i C-structs. Notera att om ett barn saknas, pekaren är null. Hur kontrollerar vi att se om 7 finns i trädet? Vi börjar vid roten. Sju är större än 6, så om det är i trädet, måste det vara till höger. Då är det mindre än 8, så det måste vara kvar. Här, har vi funnit 7. Nu ska vi leta efter 5. Fem är mindre än 6, så det måste vara till vänster. Fem är större än 2, så det måste vara rätt, och det är också större än 4, så det måste vara rätt igen. Det finns dock inget barn här. Pekaren är null. Detta innebär att 5 är inte i vårt träd. 

Vi kan söka det binära trädet med följande kod: Vid varje nod kontrollerar vi att se om vi har hittat det värde vi söker. Om vi ​​inte hittar den, avgör vi om det skulle vara på vänster eller höger och kontrollera att underträd. Denna slinga fortsätter ned trädet tills ingen barnnod på antingen vänster eller höger. 

Kom ihåg att 5 inte var i trädet. Hur sätter vi den? Processen liknar söka. Vi upprepa ned trädet från 6, vänster till 2, rätt till 4, och höger igen, men 4 har inget barn på denna sida. Detta kommer att vara den nya positionen för 5, och det kommer att börja med inga barn. 

Hur snabb är operationer på ett binärt sökträd? Kom ihåg att Bigohnotation söker tillhandahålla en övre gräns. I värsta fall, vår träd kan helt enkelt vara en länkad lista vilket innebär att infogning, utelämning, och sök kan ta tid proportionell mot antalet noder i trädet. Detta är O (n). 

Till exempel är följande en giltig binärt sökträd. Men om vi försöker hitta 9, vi måste passera varje nod. Det är inte bättre än en länkad lista. Helst skulle vi vilja varje nod vår binära sökträd att ha 2 barn. På detta sätt, infogning, utelämning och sökning skulle ta i värsta fall O (log n) tid. Trädet från tidigare kunde vara mer balanserad, så här. Nu ser upp något värde tar som mest 3 steg. Detta träd är balanserad, mening som har en minimal djup förhållande till antalet noder. 

Letar du efter ett värde i en balanserad binärt sökträd liknar binär sökning på en sorterad array. Faktum är att om vi inte behöver infoga eller ta bort objekt, de beter exakt samma sätt. Emellertid är en trädstruktur bättre För hantering infogningar och borttagningar 

Mitt namn är Bannus Van der Kloot. Detta är CS50.