{"id":91741,"date":"2022-10-12T04:16:37","date_gmt":"2022-10-12T09:16:37","guid":{"rendered":"https:\/\/blogging-techies.com\/sw\/en-nyborjarguide-till-binara-trad\/"},"modified":"2022-10-12T04:16:37","modified_gmt":"2022-10-12T09:16:37","slug":"en-nyborjarguide-till-binara-trad","status":"publish","type":"post","link":"https:\/\/blogging-techies.com\/sw\/en-nyborjarguide-till-binara-trad\/","title":{"rendered":"En nyb\u00f6rjarguide till bin\u00e4ra tr\u00e4d"},"content":{"rendered":"
\n

Om du har g\u00e5tt en datastrukturkurs i din datavetenskapsexamen, eller \u00e4r en sj\u00e4lvl\u00e4rd programmerare, \u00e4r chansen stor att du har st\u00f6tt p\u00e5 termen \u201cbin\u00e4ra tr\u00e4d\u201d. \u00c4ven om de kan l\u00e5ta lite \u00f6verv\u00e4ldigande och komplexa, \u00e4r konceptet med ett bin\u00e4rt tr\u00e4d ganska enkelt.<\/p>\n

L\u00e4s vidare n\u00e4r vi dissekerar bin\u00e4ra tr\u00e4d och varf\u00f6r de \u00e4r ett n\u00f6dv\u00e4ndigt k\u00e4rnkoncept f\u00f6r programmerare.<\/p>\n

<\/span> Vad \u00e4r bin\u00e4ra tr\u00e4d?<\/span><\/h2>\n

Bin\u00e4ra tr\u00e4d \u00e4r bland en av de f\u00f6rsta datastrukturerna som eleverna f\u00e5r l\u00e4ra sig i en datastrukturkurs. Ett bin\u00e4rt tr\u00e4d best\u00e5r av m\u00e5nga noder, och varje nod i det bin\u00e4ra tr\u00e4det inneh\u00e5ller tv\u00e5 pekare som indikerar de v\u00e4nstra och h\u00f6gra underordnade datanoderna.<\/p>\n

Den f\u00f6rsta noden i ett bin\u00e4rt tr\u00e4d kallas \u201croten\u201d. Noder p\u00e5 den sista niv\u00e5n i ett tr\u00e4d kallas l\u00f6v.<\/p>\n

\n<\/figure>\n

Varje nod inneh\u00e5ller ett dataobjekt och tv\u00e5 nodpekare. Ett tomt bin\u00e4rt tr\u00e4d representeras av en nollpekare. Som du kanske redan har r\u00e4knat ut kan bin\u00e4ra tr\u00e4d bara ha tv\u00e5 barn (d\u00e4rav namnet).<\/p>\n

<\/span> Typer av bin\u00e4ra tr\u00e4dstrukturer<\/span><\/h2>\n

Det finns flera olika bin\u00e4ra tr\u00e4dstrukturer beroende p\u00e5 hur noderna \u00e4r placerade. Ett bin\u00e4rt tr\u00e4d kallas ett helt bin\u00e4rt tr\u00e4d n\u00e4r varje nod i tr\u00e4det har antingen noll eller tv\u00e5 barn. I ett perfekt bin\u00e4rt tr\u00e4d har alla noder tv\u00e5 barn och l\u00f6ven \u00e4r alla p\u00e5 samma djup.<\/p>\n

Ett komplett bin\u00e4rt tr\u00e4d har noder fyllda i varje niv\u00e5, med undantag f\u00f6r den sista niv\u00e5n. I kompletta bin\u00e4ra tr\u00e4d \u00e4r noder koncentrerade till v\u00e4nster sida av roten. En annan vanlig struktur \u00e4r ett balanserat bin\u00e4rt tr\u00e4d; i denna struktur m\u00e5ste h\u00f6jderna p\u00e5 h\u00f6ger och v\u00e4nster undertr\u00e4d skilja sig \u00e5t h\u00f6gst en. Det kr\u00e4vs ocks\u00e5 att de v\u00e4nstra och h\u00f6gra undertr\u00e4den m\u00e5ste balanseras ocks\u00e5.<\/p>\n

Det \u00e4r viktigt att notera att h\u00f6jden p\u00e5 det balanserade bin\u00e4ra tr\u00e4det \u00e4r O(logn), d\u00e4r n \u00e4r antalet noder i tr\u00e4det.<\/p>\n

I vissa fall, om varje nod bara har ett v\u00e4nster eller h\u00f6ger barn, kan det bin\u00e4ra tr\u00e4det bli ett skevt bin\u00e4rt tr\u00e4d. Det kommer d\u00e5 att bete sig som en l\u00e4nkad lista, s\u00e5dana tr\u00e4d kallas ocks\u00e5 f\u00f6r ett degenererat tr\u00e4d.<\/p>\n

<\/span> Vad \u00e4r bin\u00e4ra s\u00f6ktr\u00e4d?<\/span><\/h2>\n

Ett bin\u00e4rt s\u00f6ktr\u00e4d (BST) \u00e4r i huvudsak ett ordnat bin\u00e4rt tr\u00e4d med en speciell egenskap k\u00e4nd som egenskapen \u201cbin\u00e4rt s\u00f6ktr\u00e4d\u201d. BST-egenskapen inneb\u00e4r att noder med ett nyckelv\u00e4rde mindre \u00e4n roten placeras i det v\u00e4nstra undertr\u00e4det, och noder med ett nyckelv\u00e4rde st\u00f6rre \u00e4n roten \u00e4r en del av det h\u00f6gra undertr\u00e4det.<\/p>\n

BST-egenskapen m\u00e5ste vara sann f\u00f6r varje efterf\u00f6ljande \u00f6verordnad nod i tr\u00e4det.<\/p>\n

\n<\/figure>\n

Bin\u00e4ra s\u00f6ktr\u00e4d erbjuder snabb infogning och uppslagning. Ins\u00e4ttning, radering och s\u00f6koperationer har en tidskomplexitet i v\u00e4rsta fall av O(n), vilket liknar en l\u00e4nkad lista.<\/p>\n

<\/span> F\u00f6rdelarna med bin\u00e4ra tr\u00e4d<\/span><\/h2>\n

Bin\u00e4ra tr\u00e4d erbjuder m\u00e5nga f\u00f6rdelar och det \u00e4r d\u00e4rf\u00f6r de f\u00f6rblir en mycket anv\u00e4ndbar datastruktur. De kan anv\u00e4ndas f\u00f6r att visa strukturella samband och hierarkier i en datam\u00e4ngd. \u00c4nnu viktigare, bin\u00e4ra tr\u00e4d till\u00e5ter effektiv s\u00f6kning, radering och infogning.<\/p>\n

Det \u00e4r ocks\u00e5 mycket enkelt att implementera och underh\u00e5lla ett bin\u00e4rt tr\u00e4d. Ett bin\u00e4rt tr\u00e4d erbjuder programmerare f\u00f6rdelarna med en ordnad array och en l\u00e4nkad lista; s\u00f6kning i ett bin\u00e4rt tr\u00e4d \u00e4r lika snabbt som i en sorterad array och ins\u00e4ttnings- eller raderingsoperationer \u00e4r lika effektiva som i l\u00e4nkade listor.<\/p>\n

<\/span> Bin\u00e4ra tr\u00e4d \u00e4r viktiga datastrukturer<\/span><\/h2>\n

Bin\u00e4ra tr\u00e4d \u00e4r en mycket viktig datastruktur och det \u00e4r avg\u00f6rande att programmerare \u00e4r bekv\u00e4ma med att anv\u00e4nda dem i sina program. Ofta fr\u00e5gar intervjuare enkla bin\u00e4ra tr\u00e4dproblem som traverseringar, maximalt djup, spegling, etc.<\/p>\n

Vi rekommenderar starkt att du f\u00f6rst\u00e5r konceptet med bin\u00e4ra tr\u00e4d och att du \u00e4r bekant med typiska intervjuproblem.<\/p>\n

Om f\u00f6rfattaren<\/strong><\/p>\n

M. Fahad Khawaja (91 artiklar publicerade)
<\/strong><\/p>\n

Fahad \u00e4r f\u00f6rfattare p\u00e5 MakeUseOf och studerar f\u00f6r n\u00e4rvarande datavetenskap. Som en ivrig teknikskribent ser han till att han h\u00e5ller sig uppdaterad med den senaste tekniken. Han \u00e4r s\u00e4rskilt intresserad av fotboll och teknik.<\/p>\n

Mer fr\u00e5n M. Fahad Khawaja<\/p>\n

<\/span>Prenumerera p\u00e5 v\u00e5rt nyhetsbrev<\/span><\/h4>\n

G\u00e5 med i v\u00e5rt nyhetsbrev f\u00f6r tekniska tips, recensioner, free e-b\u00f6cker och exklusiva erbjudanden!<\/p>\n

Klicka h\u00e4r f\u00f6r att prenumerera<\/p>\n<\/p><\/div>\n

\n
\n

Table of Contents<\/p>\nToggle<\/span><\/path><\/svg><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n