De gegevens worden meestal opgeslagen in binaire boomstructuren met behulp van gespecialiseerde algoritmen . Vele voordelen uit het opslaan van gegevens in een boomstructuur . Bijvoorbeeld zoekt een geordende binaire boom is veel sneller dan het sorteren van een sequentiële gegevensstructuur zoals een array . Een boom datastructuur verschillende soorten patronen aannemen tijdens toegangsgegevens en modificatie. Inzicht in deze patronen kunnen helpen bij het ontwerpen betere algoritmen om een boom algoritme te optimaliseren . Basis Onderdelen van een Binary Tree
Een binaire boom
bestaat uit knooppunten , welke winkel de gegevens en wijzen op andere knooppunten in de boom . Het hoofdknooppunt is het startpunt van de boom en neemt de bovenste niveau . Het kan maximaal twee onderliggende knooppunten . Deze onderliggende nodes kunnen ook maximaal twee onderliggende knooppunten . Het aantal onderliggende knooppunten een gegeven knooppunt wordt de mate van het knooppunt . Een knooppunt zonder kind en een graad nul wordt een blad. De lengte in knooppunten van de wortel knooppunt naar de verste leaf node is de hoogte van de boom . De diepte van een knooppunt is de afstand van het hoofdknooppunt aan. Elk knooppunt dat dezelfde diepte heeft schijt op hetzelfde niveau .
Volledige Binary Tree
Een volledige binaire boom is een boom, waarin elke knoop heeft precies twee of nul kinderen . Met andere woorden , elk knooppunt ofwel twee kinderen of een blad . Een voorbeeld van een volledige binaire boom is de Binary Besluit Diagram , of BDD .
Perfect Binary Tree
Een perfecte binaire boom heeft dezelfde eigenschappen van de volledige binaire boom , maar alle eindknooppunten op hetzelfde niveau , waardoor de diepte van bladeren is hetzelfde in een perfecte binaire boom . Omdat het ook een volledige binaire boom , alle knooppunten behalve de leaf nodes hebben een zekere mate van 2 .
Balanced Binary Tree
Een evenwichtige binaire boom is er een waarin de diepte van elk blad knooppunt gelijk of verschilt de waarde een . Het toevoegen en verwijderen van knooppunten van een evenwichtige binaire boom kan onbalans , dus een reeks van aanpassingen genoemd rotaties moet plaatsvinden om de boom in evenwicht te brengen . Het bijhouden van een boom evenwichtig zorgt ervoor dat de gemiddelde zoektijd voor een knooppunt is optimaal . Significante overhead nodig is om het evenwicht van een boom te behouden .
Degenerate Binary Tree
Een ontaarde binaire boom is er een waarin elke knoop , behalve de leaf node heeft precies een kind knooppunt . Het heeft dezelfde prestatiekenmerken van een gelinkte lijst , die de zoektijd voor een knooppunt toe met een aanzienlijk bedrag . Beschouw bijvoorbeeld een geval waarin het knooppunt wordt gezocht is de leaf node . De gehele boom moet worden verplaatst om dit knooppunt zijn. Met een gebalanceerde binaire boom , het vinden van een eindknooppunt vereist slechts een enkele knoop traversals gelijk aan de diepte van het blad knooppunt . Met grote bomen , kan het verschil in prestaties significant zijn.
|
