Data vanligen lagras i binära trädstrukturer med specialiserade algoritmer . Många fördelar kommer från att lagra data i en trädstruktur . T.ex. söker en beställd binärt träd är mycket snabbare än att sortera en sekventiell datastruktur såsom en array. En träddatastruktur kan anta många typer av mönster under dataåtkomst och modifiering. Att förstå dessa mönster kan hjälpa dig att designa bättre algoritmer för att optimera ett träd algoritm . Grundläggande delar av ett binärt träd
ett binärt träd består av noder , vilka data butik eller på andra noder i trädet . Rotnoden är utgångspunkten av trädet och upptar den översta nivån. Det kan ha upp till två underordnade noder . Dessa underordnade noder kan också ha upp till två underordnade noder . Antalet underordnade noder av en given nod kallas graden av noden. En nod utan några barn och en grad av noll kallas ett löv. Längden i noder från rotnoden till längst lövnod är höjden av trädet. Djupet för en nod är avståndet från rotnoden till den. Varje nod som har samma djup sägs vara på samma nivå .
Full Binary Tree
En fullständig binärt träd är ett träd där varje nod har exakt två eller noll barn . Med andra ord har varje nod antingen två barn eller är ett löv. Ett exempel på en komplett binärt träd är den binära beslut Diagram , eller BDD .
Perfect Binary Tree
En perfekt binärt träd har samma egenskaper fullständig binärt träd , men alla lövnoder är på samma nivå , vilket innebär att djupet för alla bladen är densamma i en perfekt binärt träd . Eftersom det är också en komplett binärt träd , alla noder utom lövnoderna har en grad av 2 .
Balanserad Binary Tree
En balanserad binärt träd är en där djupet av varje lövnod är antingen samma eller skiljer sig med ett värde på ett . Lägga till och ta bort noder från ett balanserat binärt träd kan obalans det , så en rad justeringar kallas rotationer måste ske för att balansera trädet . Att hålla ett träd balanserad säkerställer att den genomsnittliga söktiden till alla noder är optimal . Betydande overhead som krävs för att upprätthålla balansen i ett träd . Degenerate Binary Tree
En degenererad binärt träd är en där varje nod utom bladnoden har exakt en barn nod . Det har samma egenskaper hos en länkad lista , vilket ökar söktiden för någon nod med ett betydande belopp . Till exempel , betrakta ett fall där den nod som söks är bladnoden . Hela träd måste passeras för att finna denna nod . Med en balanserad binärt träd , att hitta en lövnod endast kräver ett antal nod traversals lika med djupet av bladet noden. Med stora träd , kan skillnaden i prestanda vara betydande .
