Binära hål och binära sökträd används i algoritmer - dummies

En särskild typ av trädstruktur är binärhöga, som placerar var och en av nodelementen i en särskild ordning. Sök träd gör att du snabbt kan leta efter data. Att skaffa dataobjekt, placera dem i sorterad ordning i ett träd, och sedan söka det träd är ett av de snabbare sätten att hitta information.

I en binär hög innehåller roddnoden alltid det minsta värdet. När du tittar på grenarna ser du att övre grenar alltid är ett mindre värde än grenar och löv på lägre nivåer. Effekten är att hålla trädet balanserat och i en förutsägbar ordning så att sökningen blir extremt effektiv. Kostnaden är att hålla trädet balanserat.

Av alla uppgifter som applikationer gör, är sökning mer tidskrävande och den som krävde mest. Även om du lägger till data (och sorterar det senare) kräver lite tid, kommer fördelen att skapa och behålla en dataset från att använda den för att utföra användbart arbete, vilket innebär att du söker efter viktig information. Följaktligen kan du ibland klara av med mindre effektiv CRUD-funktionalitet och till och med en mindre än optimal sortrutin, men sökningar måste gå så effektivt som möjligt. Det enda problemet är att ingen sökning utför varje uppgift med absolut effektivitet, så du måste väga dina alternativ baserat på vad du förväntar dig att göra som en del av sökrutinerna.

Två av de mer effektiva sökmetoderna innefattar användningen av binärt sökträd (BST) och binärt hål. Båda sökteknikerna är beroende av en trädliknande struktur för att hålla nycklarna som används för att få tillgång till dataelement. Arrangemanget av de två metoderna är emellertid annorlunda, varför man har fördelar över den andra när man utför vissa uppgifter. Denna figur visar arrangemanget för en BST.

Arrangemang av nycklar när du använder en BST.

Observera hur tangenterna följer en ordning i vilka färre tal visas till vänster och större siffror visas till höger. Rotenoden innehåller ett värde som ligger i mitten av nivån av nycklar, vilket ger BST ett lätt förstått balanserat sätt att lagra nycklarna. Kontrastera detta arrangemang till den binära höjden som visas här.

Arrangemang av nycklar när man använder en binär hög.

Varje nivå innehåller värden som är mindre än föregående nivå, och roten innehåller det högsta nyckelvärdet för trädet. Dessutom, i det här fallet visas de mindre värdena till vänster och ju större till höger (även om denna order inte är strikt tillämpad). Figuren visar faktiskt en binär maxhöga. Du kan även skapa en binär minhögdjup, där roten innehåller lägsta nyckelvärde och varje nivå bygger till högre värden, med de högsta värdena som visas i bladet.

Som tidigare nämnts har BST några fördelar jämfört med binärhöga när den används för att utföra en sökning. Följande lista ger några av höjdpunkterna i dessa fördelar:

• Sökning efter ett element kräver O (log n) tid, i motsats till O (n) tid för ett binärt hål.
• Skriv ut elementen i ordning kräver endast O (log n) tid, i motsats till O (n log n) tid för en binär hög.
• Att hitta golvet och taket kräver O (log n) tid.
• Att hitta Kth minsta / största elementet kräver O (log n) tid när trädet är korrekt konfigurerat.

Om dessa tider är viktiga beror på din ansökan. BST tenderar att fungera bäst i situationer där du spenderar mer tid på att söka och mindre tid att bygga trädet. En binär hög har en tendens att fungera bäst i dynamiska situationer där nycklarna ändras regelbundet. Binärhöget erbjuder också fördelar, som beskrivs i följande lista:

• Skapa de nödvändiga strukturerna kräver färre resurser eftersom binära hällor är beroende av arrays, vilket gör dem också cachevänligare.
• Att bygga ett binärt hål kräver O (n) tid, i motsats till BST, vilket kräver O (n log n) tid.
• Det är inte nödvändigt att använda pekare för att implementera trädet.
• Beroende på binära höjdsvariationer (till exempel Fibonacci Heap) erbjuder fördelar som ökning och minskning av viktiga tider av O (1) tid.