Dator
 |  Startsida |  Hårdvara |  Nätverk |  Programmering |  Programvara |  Felsökning |  System |   
Programmering
  • C /C + + -programmering
  • Computer Programspråk
  • Delphi Programmering
  • Java Programming
  • JavaScript programmering
  • PHP /MySQL Programmering
  • perl Programmering
  • python Programming
  • Ruby programmering
  • Visual Basics Programmering
  • * Dator Kunskap >> Programmering >> Computer Programspråk >> Content

    Frekventa Mönster i Tree Algoritmer

    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 .

    Tidigare:

    nästa:
    relaterade artiklar
    ·Hur man skriver ett Shell Script bort filer
    ·Hur Serialisera ett objekt med Enum
    ·Hur du ändrar markören i en textruta
    ·CFG Filtyp
    ·JavaScript Vs. Java Applets
    ·Hur man skapar en enkel seriell UART sändare i Verilog…
    ·DIY Stegdrivare
    ·Hur man använder standardiserade Namnkonventioner i Mu…
    ·Hur man använder data på ett flödesschema
    ·Fördelar med Fortran
    Utvalda artiklarna
    ·Hur man kan öka storleken på HTML knappen Skicka
    ·Vad är skillnaden mellan låg - nivå programmering & …
    ·Hur Infoga PHP i WordPress
    ·Hur Rotera Vittnesmål på en webbplats
    ·Hur man skriver en egen enkel Java Message Queue
    ·Exempel på Python XML Processing
    ·Hur man skapar en App för Evo
    ·Hur man installerar Java Utan administratörsbehörighe…
    ·Hur Integrera Android Med Eclipse
    ·Korrekt Case Funktion för PHP Strings
    Copyright © Dator Kunskap http://www.dator.xyz