Binärt träd

Ett märkt binärt träd av storlek 9 och höjd 3, med en rotnod vars värde är 1. Ovanstående träd är obalanserat och inte sorterat.

Inom datavetenskap är ett binärt träd en k-ary $k=2$ träddatastruktur där varje nod har högst två barn , som kallas det vänstra barnet och det högra barnet . En rekursiv definition som använder bara mängdteoretiska begrepp är att ett (icke-tomt) binärt träd är en tupel ( L , S , R ), där L och R är binära träd eller den tomma mängden och S är en singleton-mängd som innehåller roten. Vissa författare tillåter att det binära trädet också är den tomma uppsättningen.

Ur ett grafteoretiskt perspektiv är binära (och K-ary) träd som de definieras här arborescenser . Ett binärt träd kan därför också kallas en bifurcating arborescence - en term som förekommer i några mycket gamla programmeringsböcker, innan den moderna datavetenskapliga terminologin rådde. Det är också möjligt att tolka ett binärt träd som en oriktad , snarare än en riktad graf , i vilket fall ett binärt träd är ett ordnat , rotat träd . Vissa författare använder rotat binärt träd istället för binärt träd för att betona det faktum att trädet är rotat, men enligt definitionen ovan är ett binärt träd alltid rotat. Ett binärt träd är ett specialfall av ett ordnat K-ärt träd , där K är 2.

I matematik kan det som kallas binärt träd variera avsevärt från författare till författare. Vissa använder den definition som vanligtvis används inom datavetenskap, men andra definierar det som att varje icke-blad har exakt två barn och beställer inte nödvändigtvis (som vänster/höger) barnen heller.

I datoranvändning används binära träd på två mycket olika sätt:

Först, som ett sätt att komma åt noder baserat på något värde eller etikett som är associerad med varje nod. Binära träd märkta på detta sätt används för att implementera binära sökträd och binära högar , och används för effektiv sökning och sortering . Beteckningen av icke-rotnoder som vänster eller höger barn, även när det bara finns ett barn, spelar roll i vissa av dessa applikationer, i synnerhet är det signifikant i binära sökträd. Arrangemanget av särskilda noder i trädet är dock inte en del av den konceptuella informationen. Till exempel, i ett normalt binärt sökträd beror placeringen av noder nästan helt på i vilken ordning de lades till, och kan omarrangeras (till exempel genom att balansera ) utan att ändra innebörden.
För det andra, som en representation av data med en relevant förgrenad struktur. I sådana fall är det speciella arrangemanget av noder under och/eller till vänster eller höger om andra noder en del av informationen (det vill säga att ändra den skulle ändra innebörden). Vanliga exempel förekommer med Huffman-kodning och kladogram . Den dagliga uppdelningen av dokument i kapitel, avsnitt, stycken och så vidare är ett analogt exempel med n-ary snarare än binära träd.

Definitioner

Rekursiv definition

För att definiera ett binärt träd måste möjligheten att endast ett av barnen kan vara tomt bekräftas. En artefakt , som i vissa läroböcker kallas ett utökat binärt träd, behövs för det ändamålet. Ett utökat binärt träd definieras således rekursivt som:

den tomma uppsättningen är ett utökat binärt träd
om T ₁ och T ₂ är utökade binära träd, beteckna då med T ₁ • T ₂ det utökade binära trädet som erhålls genom att lägga till en rot r kopplad till vänster till T ₁ och till höger till T ₂^{[ förtydligande behövs var gjorde ' r' gå in i 'T ₁ • T ₂ '-symbolen ]} genom att lägga till kanter när dessa underträd inte är tomma.

Ett annat sätt att föreställa sig denna konstruktion (och förstå terminologin) är att istället för den tomma mängden överväga en annan typ av noder – till exempel kvadratiska noder om de vanliga är cirklar.

Använda grafteoretiska begrepp

Ett binärt träd är ett rotat träd som också är ett ordnat träd (alias platan) där varje nod har högst två barn. Ett rotat träd ger naturligtvis en föreställning om nivåer (avstånd från roten), så för varje nod kan en föreställning om barn definieras som de noder som är kopplade till den en nivå under. Beställning av dessa barn (t.ex. genom att rita dem på ett plan) gör det möjligt att skilja ett vänster barn från ett höger barn. Men detta skiljer fortfarande inte mellan en nod med vänster men inte höger barn från en med höger men inget vänster barn.

Den nödvändiga distinktionen kan göras genom att först partitionera kanterna, dvs definiera det binära trädet som triplett (V, E 1 , _E 2 ₎ , där (V, E ₁ ∪ E ₂ ) är ett rotat träd (motsvarande arborescens) och E ₁ ∩ E ₂ är tom, och kräver också att för alla j ∈ { 1, 2 } har varje nod högst ett E _j -barn. Ett mer informellt sätt att göra skillnaden är att säga, med citat från Encyclopedia of Mathematics , att "varje nod har ett vänsterbarn, ett högerbarn, ingetdera eller båda" och att specificera att dessa "alla är olika" binära träd.

Typer av binära träd

Trädterminologin är inte välstandardiserad och varierar därför i litteraturen.

Ett rotat binärt träd har en rotnod och varje nod har högst två barn.

Ett helt binärt träd

Ett anordiagram som kan mappas till ett perfekt 4-nivå binärt träd.

Ett fullständigt binärt träd (ibland kallat ett korrekt eller plant eller strikt binärt träd) är ett träd där varje nod har antingen 0 eller 2 barn. Ett annat sätt att definiera ett fullständigt binärt träd är en rekursiv definition . Ett fullständigt binärt träd är antingen:
- En enda vertex.
- Ett träd vars rotnod har två underträd, som båda är fullständiga binära träd.
Ett perfekt binärt träd är ett binärt träd där alla inre noder har två barn och alla löv har samma djup eller samma nivå . Ett exempel på ett perfekt binärt träd är det (icke-incestuösa) anordiagrammet för en person till ett givet djup, eftersom varje person har exakt två biologiska föräldrar (en mor och en far). Förutsatt att anordiagrammet alltid visar modern och fadern på samma sida för en given nod, kan deras kön ses som en analogi av vänster och höger barn, där barn förstås här som en algoritmisk term.
Ett komplett binärt träd är ett binärt träd där varje nivå, utom möjligen den sista , är helt fylld, och alla noder i den sista nivån är så långt till vänster som möjligt. Den kan ha mellan 1 och 2 ^h noder på den sista nivån h . Ett perfekt träd är därför alltid komplett men ett komplett träd är inte nödvändigtvis perfekt. En alternativ definition är ett perfekt träd vars löv längst till höger (kanske alla) har tagits bort. Vissa författare använder termen komplett för att istället hänvisa till ett perfekt binärt träd enligt definitionen ovan, i vilket fall de kallar denna typ av träd (med en möjligen inte fylld sista nivå) för ett nästan komplett binärt träd eller nästan komplett binärt träd. Ett komplett binärt träd kan effektivt representeras med hjälp av en array.

Ett komplett binärt träd (som inte är fullt)

I det oändliga kompletta binära trädet har varje nod två barn (och så uppsättningen av nivåer är uträkneligt oändlig ). Uppsättningen av alla noder är uträkneligt oändlig, men uppsättningen av alla oändliga banor från roten är oräknelig och har kontinuumets kardinalitet . Det beror på att dessa banor genom en ordningsbevarande bijektion motsvarar punkterna i Cantor-mängden , eller (med exemplet med ett Stern-Brocot-träd ) till uppsättningen positiva irrationella tal .
Ett balanserat binärt träd är en binär trädstruktur där de vänstra och högra underträden i varje nod skiljer sig i höjd med högst 1. Man kan också överväga binära träd där inget blad är mycket längre bort från roten än något annat löv. (Olika balanseringssystem tillåter olika definitioner av "mycket längre".)
Ett degenererat (eller patologiskt ) träd är där varje föräldernod bara har en associerad undernod. Detta betyder att trädet kommer att bete sig som en länkad listdatastruktur.

Egenskaper för binära träd

Antalet noder $n$ i ett helt binärt träd är minst $2h+1$ och högst $2^{h+1}-1$ , där $h$ är trädets höjd . Ett träd som bara består av en rotnod har en höjd på 0.
Antalet lövnoder $l$ i ett perfekt binärt träd är $l=(n+1)/2$ eftersom antalet icke-blad (aka interna ) knutpunkter $nl=\summa _{k=0}^{\log _{ 2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ .
Detta betyder att ett helt binärt träd med $l$ -blad har $n=2l-1$ noder.
I ett balanserat fullt binärt träd, $h=\lceil \log _ {2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ (se takfunktion ). ^{[ citat behövs ]}
I ett perfekt helt binärt träd är $l=2^{h}$ alltså $n=2^{h+1}-1$ .
Antalet nolllänkar (dvs. frånvarande barn till noderna) i ett binärt träd med n noder är ( n +1).
Antalet interna noder i ett komplett binärt träd med n noder är $\lfloor n/2\rfloor$ .
₀₀ För alla icke-tomma binära träd med n lövnoder och n ₂ noder av grad 2, n = n ₂ + 1.

Kombinatorik

Inom kombinatorik överväger man problemet med att räkna antalet fulla binära träd av en given storlek. Här har träden inga värden kopplade till sina noder (detta skulle bara multiplicera antalet möjliga träd med en lättbestämd faktor), och träd särskiljs endast genom sin struktur; men det vänstra och högra underordnade underordnade av någon nod särskiljs (om de är olika träd, kommer utbyte av dem att producera ett träd som skiljer sig från det ursprungliga). Storleken på trädet antas vara antalet n av interna noder (de med två barn); de andra noderna är bladnoder och det finns $n + 1$ av dem. Antalet sådana binära träd av storlek n är lika med antalet sätt att helt inom parentes placera en sträng av $n + 1$ symboler (som representerar löv) åtskilda av n binära operatorer (som representerar interna noder), för att bestämma argumentunderuttrycken för varje operator. Till exempel för $n = 3$ måste man placera inom parentes en sträng som ${\displaystyle X*X*X*X} ,$ vilket är möjligt på fem sätt:

((X*X)*X)*X,\qquad (X*(X*X))*X,\qquad (X*X)*(X*X),\qquad X*((X) *X)*X),\qquad X*(X*(X*X)).

Överensstämmelsen med binära träd bör vara uppenbar, och tillägget av redundanta parenteser (runt ett uttryck som redan har parentes eller runt hela uttrycket) är inte tillåtet (eller räknas åtminstone inte som att skapa en ny möjlighet).

Det finns ett unikt binärt träd av storlek 0 (som består av ett enda blad), och vilket annat binärt träd som helst kännetecknas av paret av dess vänstra och högra barn; om dessa har storlekarna i respektive j , har hela trädet storleken $i + j 1$ + . Därför har antalet $C_{n}$ av binära träd av storlek n följande rekursiva beskrivning $C_{0}=1$ och ${\displaystyle \textstyle C_{n}=\summa _{i=0}^{n-1}C_{i}C_{n-1-i}} för ett positivt$ heltal n . Det följer att $C_{n}$ är det katalanska numret för index n .

Ovanstående parentessträngar ska inte förväxlas med orduppsättningen med längden 2 n i språket Dyck , som endast består av parenteser på ett sådant sätt att de är korrekt balanserade. Antalet sådana strängar uppfyller samma rekursiva beskrivning (varje Dyck-ord med längden 2 n bestäms av Dyck-underordet omgivet av initialen '(' och dess matchande ')' tillsammans med Dyck-underordet som finns kvar efter den avslutande parentesen, vars längder 2i och 2j uppfyller i $+ j + 1 = n$ ) ; detta nummer är därför också det katalanska talet $C_{n}$ . Så det finns också fem Dyck-ord med längd 6:

()()(), ()(()), (())(), (()()), ((()))

Dessa Dyck-ord motsvarar inte binära träd på samma sätt. Istället är de relaterade av följande rekursivt definierade bijektion: Dyck-ordet lika med den tomma strängen motsvarar det binära trädet av storlek 0 med bara ett blad. Alla andra Dyck-ord kan skrivas som ( $w_{1}$ ) $w_{2}$ , där $w_{1}$ , $w_{ 2}$ är själva (möjligen tomma) Dyck-ord och där de två skrivna parenteserna matchas. Bijektionen definieras sedan genom att låta orden $w_{1}$ och $w_{2}$ motsvara de binära träden som är rotens vänstra och högra barn.

En bijektiv överensstämmelse kan också definieras på följande sätt: omslut Dyck-ordet inom ett extra par parenteser, så att resultatet kan tolkas som ett Lisp- listuttryck (med den tomma listan () som endast förekommande atom); då är det prickade paruttrycket för den riktiga listan ett uttryck i fullständig parentes (med NIL som symbol och '.' som operator) som beskriver det motsvarande binära trädet (som i själva verket är den interna representationen av den korrekta listan).

Möjligheten att representera binära träd som strängar av symboler och parenteser innebär att binära träd kan representera elementen i en fri magma på en singleton-uppsättning.

Metoder för att lagra binära träd

Binära träd kan konstrueras från programmeringsspråksprimitiver på flera sätt.

Noder och referenser

I ett språk med poster och referenser är binära träd vanligtvis konstruerade genom att ha en trädnodstruktur som innehåller vissa data och referenser till dess vänstra underordnade och dess högra underordnade. Ibland innehåller den också en hänvisning till sin unika förälder. Om en nod har färre än två underordnade, kan några av underordnade pekare ställas in på ett speciellt nollvärde eller till en speciell sentinelnod .

Denna metod att lagra binära träd slösar bort en hel del minne, eftersom pekarna kommer att vara noll (eller peka på vaktposten) mer än halva tiden; ett mer konservativt representationsalternativ är gängade binära träd .

I språk med taggade fackföreningar som ML , är en trädnod ofta en taggad förening av två typer av noder, varav en är en 3-tuppel av data, vänster underordnad och höger underordnad, och den andra är ett "blad " nod, som inte innehåller några data och fungerar ungefär som nollvärdet i ett språk med pekare. Till exempel definierar följande kodrad i OCaml (en ML-dialekt) ett binärt träd som lagrar ett tecken i varje nod.

            typ  chr_tree  =  Tom  |  Nod  för  char  *  chr_tree  *  chr_tree

Matriser

Binära träd kan också lagras i bredd-första ordning som en implicit datastruktur i arrayer , och om trädet är ett komplett binärt träd, slösar den här metoden inget utrymme. I detta kompakta arrangemang, om en nod har ett index i , hittas dess barn vid index $2i+1$ (för det vänstra barnet) och $2i+2$ (för höger), medan dess överordnade (om någon) finns vid index ${\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor } ($ förutsatt att roten har index noll). Alternativt, med en 1-indexerad array, förenklas implementeringen med barn som finns vid $2i$ och $2i+1$ , och förälder hittas vid $\ lfloor i/2\rfloor$ . Denna metod drar nytta av mer kompakt lagring och bättre referenslokalitet, särskilt under en förbeställningsgenomgång. Det är dock dyrt att odla ^{[ citat behövs ]} och slösar utrymme proportionellt ^{[ citat behövs ]} till 2 ^h - n för ett träd med djup h med n noder.

Denna lagringsmetod används ofta för binära högar . ^{[ citat behövs ]}

Kodningar

Kortfattade kodningar

En kortfattad datastruktur är en som upptar nära minsta möjliga utrymme, vilket fastställts av informationsteoretiska nedre gränser. Antalet olika binära träd på $n$ noder är $\mathrm {C} _{n}$ , det ${\displaystyle n}:$ e katalanska talet (om vi antar att vi ser träd med identisk struktur som identisk). För stora $n$ är detta ungefär $4^{n}$ ; därför behöver vi åtminstone ca $\log _{2}4^{n}=2n$ bitar för att koda den. Ett kortfattat binärt träd skulle därför uppta $2n+o(n)$ bitar.

En enkel representation som möter denna gräns är att besöka trädets noder i förbeställning och mata ut "1" för en intern nod och "0" för ett löv. Om trädet innehåller data kan vi helt enkelt samtidigt lagra det i en på varandra följande array i förbeställning. Denna funktion åstadkommer detta:

  funktion  EncodeSuccinct(  nod  n,  bitsträngstruktur  ,  arraydata  ) {  om  n =  noll ,   lägg  till 0 till strukturen;  annat  tillägg 1 till strukturen; bifoga n.data till data;  EncodeSuccinct(n.vänster, struktur, data);  EncodeSuccinct(n.höger, struktur, data);  }

Strängstrukturen har endast $2n+1$ bitar i slutet, där ${\displaystyle n} är$ antalet (interna) noder; vi behöver inte ens lagra dess längd. För att visa att ingen information går förlorad kan vi konvertera utdata tillbaka till det ursprungliga trädet så här:

    
         funktion  DecodeSuccinct(  bitsträngsstruktur  ,  matrisdata  ) { ta bort första bit av  struktur  och lägg den i  b  om  b = 1 skapa   sedan  en ny nod  n  ta bort första dataelement och lägg det i n.data n.left = DecodeSuccinct(struktur, data) n.right = DecodeSuccinct(struktur, data)  return  n  else  return  noll }

Mer sofistikerade kortfattade representationer tillåter inte bara kompakt lagring av träd utan även användbara operationer på dessa träd direkt medan de fortfarande är i sin korta form.

Kodar allmänna träd som binära träd

Det finns en en-till-en-mappning mellan generellt ordnade träd och binära träd, som i synnerhet används av Lisp för att representera allmänt ordnade träd som binära träd. För att konvertera ett allmänt ordnat träd till ett binärt träd behöver vi bara representera det allmänna trädet på vänster-barn höger-syskon sätt. Resultatet av denna representation blir automatiskt ett binärt träd om det ses från ett annat perspektiv. Varje nod N i det ordnade trädet motsvarar en nod N' i det binära trädet; det vänstra barnet till N' är noden som motsvarar det första barnet till N , och det högra barnet till N' är noden som motsvarar Ns nästa syskon --- det vill säga nästa nod i ordningen bland barnen i förälder till N . Denna binära trädrepresentation av ett allmänt ordningsträd kallas ibland också för ett vänsterbarn höger-syskon binärt träd (även känt som LCRS-träd, dubbelkedjat träd, filial-arvingskedja).

Ett sätt att tänka på detta är att varje nods barn finns i en länkad lista , kedjade samman med sina högra fält, och noden har bara en pekare till början eller huvudet av denna lista, genom dess vänstra fält.

Till exempel, i trädet till vänster har A de 6 barnen {B,C,D,E,F,G}. Det kan konverteras till det binära trädet till höger.

Det binära trädet kan ses som det ursprungliga trädet lutat i sidled, där de svarta vänstra kanterna representerar första barnet och de blå högra kanterna representerar nästa syskon . Bladen på trädet till vänster skulle skrivas i Lisp som:

(((NO) IJ) CD ((P) (Q)) F (M))

som skulle implementeras i minnet som det binära trädet till höger, utan några bokstäver på de noder som har ett vänsterbarn.

Vanliga operationer

Trädrotationer är mycket vanliga interna operationer på självbalanserande binära träd .

Det finns en mängd olika operationer som kan utföras på binära träd. Vissa är mutatoroperationer , medan andra helt enkelt returnerar användbar information om trädet.

Införande

Noder kan infogas i binära träd mellan två andra noder eller läggas till efter en lövnod . I binära träd anges en nod som infogas om vems underordnade den ska vara.

Bladnoder

För att lägga till en ny nod efter lövnod A, tilldelar A den nya noden som ett av dess underordnade och den nya noden tilldelar nod A som sin förälder.

Interna noder

Processen att infoga en nod i ett binärt träd

Insättning på interna noder är något mer komplex än på bladnoder. Säg att den interna noden är nod A och att nod B är A:s underordnade. (Om infogningen är för att infoga ett höger underordnat, då är B A:s högra underordnade, och på samma sätt med en vänstra underordnad insättning.) A tilldelar dess barn till den nya noden och den nya noden tilldelar sin förälder till A. Sedan tilldelar den nya noden sitt barn till B och B tilldelar sin förälder som den nya noden.

Radering

Borttagning är den process där en nod tas bort från trädet. Endast vissa noder i ett binärt träd kan tas bort entydigt.

Nod med noll eller ett barn

Processen att ta bort en intern nod i ett binärt träd

Antag att noden som ska raderas är nod A. Om A inte har några barn, utförs raderingen genom att ställa in barnet till A:s förälder till null . Om A har ett barn, ställ in föräldern till A:s barn till A:s förälder och ställ in barnet till A:s förälder till A:s barn.

Nod med två barn

I ett binärt träd kan en nod med två barn inte tas bort entydigt. Men i vissa binära träd (inklusive binära sökträd ) kan dessa noder tas bort, dock med en omarrangering av trädstrukturen.

Traversering

Genomgång av förbeställning, i ordning och efter beställning besöker varje nod i ett träd genom att rekursivt besöka varje nod i rotens vänstra och högra underträd.

Djup-första beställning

I djupet-första ordningen försöker vi alltid besöka den nod som är längst bort från rotnoden som vi kan, men med förbehållet att det måste vara ett barn till en nod som vi redan har besökt. Till skillnad från en djup-först-sökning på grafer, finns det ingen anledning att komma ihåg alla noder vi har besökt, eftersom ett träd inte kan innehålla cykler. Förbeställning är ett specialfall av detta. Se djup-först-sökning för mer information.

Bredd-första beställning

Att kontrastera med djup-första ordningen är bredd-första ordningen, som alltid försöker besöka noden närmast roten som den inte redan har besökt. Se bredd-första sökning för mer information. Kallas även en nivåordningsövergång .

0 I ett komplett binärt träd kan en nods breddindex ( i − (2 ^d − 1)) användas som genomgångsinstruktioner från roten. Läser bitvis från vänster till höger, med början på bit d − 1, där d är nodens avstånd från roten ( d = ⌊log ₂ ( i +1) ⌋) och noden i fråga är inte själva roten ( d > 0 ). När breddindexet är maskerat vid bit d − 1 betyder bitvärdena och 1 att gå antingen åt vänster eller höger. Processen fortsätter genom att successivt kontrollera nästa bit till höger tills det inte finns fler. Biten längst till höger indikerar den slutliga genomgången från den önskade nodens förälder till själva noden. Det finns en kompromiss mellan tid och rum mellan att iterera ett komplett binärt träd på detta sätt kontra att varje nod har pekare till sina syskon.

Se även

Citat

Bibliografi

Donald Knuth . The Art of Computer Programming vol 1. Fundamental Algorithms , tredje upplagan. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Avsnitt 2.3, särskilt underavsnitt 2.3.1–2.3.2 (s. 318–348).

externa länkar

Träddatastrukturer
Sökträd ( dynamiska uppsättningar / associativa arrayer )	2–3 2–3–4 AA (a,b) AVL B B+ B* B ^x ( Optimal ) Binär sökning Dans HTree Intervall Beställningsstatistik ( Vänsterlutad ) Röd–svart Syndabock Splay T Treap DU ÄR Viktbalanserad
Högar	Binär Binom Brodal Fibonacci Vänsterman Parning Skev van Emde Boas Svag
Försöker	Ctrie C-trie (komprimerad ADT) Hash Radix Ändelse Ternär sökning X-snabb Y-snabb
Rumsliga datapartitioneringsträd	Boll BK BSP kartesiska Hilbert R k -d ( implicit k -d ) M Metrisk MVP Octree PH Prioritet R Quad R R+ R* Segmentet VP X
Andra träd	Omslag Exponentiell Fenwick Finger Fraktalträdindex Fusion Hash kalender iDistance K-ary Vänster-barn höger-syskon Länka/klippa Loggstrukturerad sammanslagning Merkle PQ Räckvidd SPQR Topp