Share
Hittills har vi tittat på datastrukturer som organiserar data linjärt. Länkade listor innehåller data från en enda startnod till en enda avslutande nod. Arrays håller data i angränsande, endimensionella block.
I det här avsnittet kommer vi att se hur det går att införa en ny datastruktur: trädet, om man lägger till en ytterligare dimension. Specifikt kommer vi att titta på en typ av träd som kallas ett binärt sökträd. Binära sökträd tar den allmänna trädstrukturen och tillämpar en uppsättning enkla regler som definierar trädets struktur.
Innan vi lär oss om dessa regler, låt oss lära oss vad ett träd är.
Ett träd är en datastruktur där varje nod har noll eller fler barn. Till exempel kan vi ha ett träd så här:
En organisatorisk trädstruktur I det här trädet kan vi se företagets organisationsstruktur. Blocken representerar personer eller divisioner inom företaget, och linjerna representerar rapporterande relationer. Ett träd är ett mycket effektivt, logiskt sätt att presentera och lagra denna information.
Träet som visas i föregående figur är ett generellt träd. Det representerar föräldra- / barnrelationer, men det finns inga regler för strukturen. VD har en direkt rapport men kan lika lätt ha ingen eller tjugo. I figuren visas försäljningen till vänster om marknadsföring, men den beställningen har ingen betydelse. Faktum är att den enda observerbara begränsningen är att varje nod har högst en förälder (och den högsta noden, styrelsen, har ingen förälder).
Ett binärt sökträd använder samma grundläggande struktur som det allmänna trädet som visas i sista siffra men med tillägg av några regler. Dessa regler är:
Låt oss titta på ett träd som är byggt med dessa regler:
Binärt sökträd Lägg märke till hur de begränsningar vi angivit verkställs i diagrammet. Varje värde till vänster om rotnoden (åtta) har ett värde mindre än åtta, och varje värde till höger är större än eller lika med rotnodet. Denna regel gäller rekursivt vid varje nod under vägen.
Med detta träd i åtanke, låt oss tänka på de steg som gick in i byggnaden. När processen startade var trädet tomt och sedan sattes ett värde, åtta. Eftersom det var det första värdet tillsattes, placerades det i rot (ultimata föräldra) positionen.
Vi vet inte exakt den ordning som resten av noderna lagts till, men jag presenterar en möjlig väg. Värden kommer att läggas till med en metod som heter Lägg till som accepterar värdet.
Binary Tree tree = nytt BinaryTree (); tree.Add (8); tree.Add (4); tree.Add (2); tree.Add (3); tree.Add (10); tree.Add (6); tree.Add (7);
Låt oss gå igenom de första punkterna.
Åtta tillsattes först och blev roten. Därefter tillsattes fyra. Eftersom fyra är mindre än åtta måste den gå åt vänster om åtta enligt regel nummer två. Eftersom åtta har inget barn till vänster blir fyra det omedelbara vänstra barnet på åtta.
Två läggs till nästa. två är mindre än åtta, så går det till vänster. Det finns redan en nod till vänster om åtta, så jämförelseslogiken utförs igen. två är mindre än fyra och fyra har inget kvar barn, så två blir det vänstra barnet på fyra.
Tre läggs till nästa och går till vänster om åtta och fyra. Jämfört med de två noderna är det större, så tre läggs till höger om två enligt regelnummer tre.
Denna cykel av att jämföra värden vid varje nod och sedan kontrollera varje barn om och om tills den korrekta spåret hittas upprepas för varje värde tills den slutliga trädstrukturen är skapad.
De BinaryTreeNode representerar en enda nod i trädet. Den innehåller referenser till vänster och höger barn (null om det inte finns), nodens värde och IComparable.CompareTo metod som gör det möjligt att jämföra nodvärdena för att bestämma om värdet ska gå till vänster eller höger om nuvarande nod. Detta är hela BinaryTreeNode klass - som du kan se är det väldigt enkelt.
klass BinaryTreeNode: IComparable där TNode: IComparable public BinaryTreeNode (TNode-värde) Value = value; offentliga BinaryTreeNode vänster get; uppsättning; offentliga BinaryTreeNode Right get; uppsättning; public TNode Value get; privat uppsättning /// /// Jämför nuvarande nod till det angivna värdet. /// /// Nodvärdet ska jämföras med /// 1 om instansvärdet är större än /// det angivna värdet, -1 om mindre eller 0 om lika. public int CompareTo (TNode other) returnera Value.CompareTo (andra);
De binary klassen ger de grundläggande metoderna du behöver för att manipulera trädet: Lägg till, Ta bort, en innehåller metod för att bestämma om ett föremål finns i trädet, flera travers- och uppräkningsmetoder (det här är metoder som tillåter oss att räkna upp noderna i trädet i olika väldefinierade order) och det normala Räkna och Klar metoder.
För att initiera trädet finns det en BinaryTreeNode referens som representerar trädets huvud (root) nod, och det finns ett heltal som håller reda på hur många saker som finns i trädet.
allmän klass BinaryTree: IEnumerable där T: IComparable private BinaryTreeNode _head; privat int _count; public void Add (T-värde) släng nytt NotImplementedException (); public bool Innehåller (T-värde) släng nytt NotImplementedException (); public bool Ta bort (T-värde) släng nytt NotImplementedException (); public void PreOrderTraversal (Åtgärdsåtgärd) kasta ny NotImplementedException (); public void PostOrderTraversal (Åtgärdsåtgärd) kasta ny NotImplementedException (); public void InOrderTraversal (Åtgärdsåtgärd) kasta ny NotImplementedException (); public IEnumerator GetEnumerator () kasta ny NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () kasta nya NotImplementedException (); public void Clear () kasta nya NotImplementedException (); public int count get;
| Beteende | Lägger till det angivna värdet på rätt plats inom trädet. |
| Prestanda | O (log n) i genomsnitt; O (n) i värsta fall. |
Att lägga till en nod till trädet är inte hemskt komplicerat och blir ännu enklare när problemet förenklas till en rekursiv algoritm. Det finns två fall som måste beaktas:
I det första fallet fördelar vi helt enkelt den nya noden och lägger den till trädet. I det andra fallet jämför vi värdet till nodens värde. Om värdet vi försöker lägga till är mindre än nodens värde upprepas algoritmen för nodens vänstra barn. Annars upprepas det för nodens rätt barn.
public void Lägg till (T-värde) // Fall 1: Trädet är tomt. Tilldel huvudet. om (_head == null) _head = nytt BinaryTreeNode (värde); // Fall 2: Trädet är inte tomt, så rekursivt // hitta rätt plats för att infoga noden. annars AddTo (_head, value); _count ++; // Rekursiv tilläggsalgoritm. privat tomt AddTo (BinaryTreeNode nod, T-värde) // Fall 1: Värdet är mindre än det nuvarande nodvärdet om (value.CompareTo (node.Value) < 0) // If there is no left child, make this the new left, if (node.Left == null) node.Left = new BinaryTreeNode(value); else // else add it to the left node. AddTo(node.Left, value); // Case 2: Value is equal to or greater than the current value. else // If there is no right, add it to the right, if (node.Right == null) node.Right = new BinaryTreeNode(value); else // else add it to the right node. AddTo(node.Right, value);
| Beteende | Ta bort den första noren som hittades med det angivna värdet. |
| Prestanda | O (log n) i genomsnitt; O (n) i värsta fall. |
Att ta bort ett värde från trädet är en konceptuellt enkel operation som blir överraskande komplex i praktiken.
På hög nivå är operationen enkel:
Det första steget är enkelt, och som vi ser är det uppnåtts med samma mekanism som Innehåller-metoden använder. När noden som ska tas bort identifieras kan operationen ta en av tre banor dikterade av trädets tillstånd runt noden som ska avlägsnas. De tre staterna beskrivs i följande tre fall.
Fall ett: noden som ska tas bort har inget rätt barn.
Fall 1 Den nod som ska tas bort har inget rätt barn I det här fallet kan borttagningsoperationen helt enkelt flytta det vänstra barnet, om det finns en, till platsen för den borttagna noden. Det resulterande trädet skulle se ut så här:
Fall 1 - Trädstatus efter borttagning Fall två: Den nod som ska tas bort har ett rätt barn som i sin tur inte har något kvarbarn.
Fall två Den nod som ska tas bort har ett rätt barn som inte har något vänster barn I det här fallet vill vi flytta den borttagna nodens rätt barn (sex) till platsen för den borttagna noden. Det resulterande trädet kommer att se ut så här:
Trädtillstånd efter borttagning Fall tre: Den nod som ska tas bort har ett rätt barn som i sin tur har ett vänsterbarn.
Fall 3 - Den nod som ska tas bort har ett rätt barn som har ett vänsterbarn I det här fallet måste det vänstra barnet på den borttagna nodens rätt barn placeras i den borttagna nodens kortplats.
Låt oss ta en minut att tänka på varför detta är sant. Det finns två fakta som vi vet om sub-trädet som börjar med att noden tas bort (till exempel sub-trädet vars rot är noden med värdet fem).
Vi måste placera ett värde i den borttagna nodens slits som är mindre än eller lika med varje nod till höger. För att göra det måste vi få det minsta värdet på höger sida. Därför behöver vi rätt barns vänstra knutpunkt.
Efter borttagningen av noden kommer trädet att se ut så här:
Fall 3 - Träd efter nodavlägsnande Nu när vi förstår de tre ta bort scenarierna, låt oss titta på koden för att få det att hända.
En sak att notera: The FindWithParent metod (se avsnittet Innehåller) returnerar noden som ska tas bort såväl som föräldern till noden som tas bort. Detta görs för att när noden tas bort måste vi uppdatera förälderns Vänster eller Höger egenskap att peka på den nya noden.
Vi kunde undvika att göra detta om alla noder höll en hänvisning till deras förälder, men det skulle introducera per-nod minnesutgifter och bokföringskostnader som bara behövs i det här fallet.
public bool Ta bort (T-värde) BinaryTreeNode ström, förälder; // Hitta noden att ta bort. current = FindWithParent (värde, förälder); om (nuvarande == null) return false; _count--; // Fall 1: Om nuvarande har inget rätt barn ersätter nuvarande vänster nuvarande. om (current.Right == null) om (förälder == null) _head = current.Left; annars int result = parent.CompareTo (current.Value); om (resultat> 0) // Om föräldravärdet är större än nuvärdet, // gör det nuvarande vänstra barnet ett vänsterbarn av föräldern. parent.Left = current.Left; annars om (resultat < 0) // If parent value is less than current value, // make the current left child a right child of parent. parent.Right = current.Left; // Case 2: If current's right child has no left child, current's right child // replaces current. else if (current.Right.Left == null) current.Right.Left = current.Left; if (parent == null) _head = current.Right; else int result = parent.CompareTo(current.Value); if (result > 0) // Om föräldravärdet är större än nuvärdet, // gör det nuvarande rättiga barnet ett vänsterbarn av föräldern. parent.Left = current.Right; annars om (resultat < 0) // If parent value is less than current value, // make the current right child a right child of parent. parent.Right = current.Right; // Case 3: If current's right child has a left child, replace current with current's // right child's left-most child. else // Find the right's left-most child. BinaryTreeNode leftmost = current.Right.Left; BinaryTreeNode leftmostParent = current.Right; while (leftmost.Left != null) leftmostParent = leftmost; leftmost = leftmost.Left; // The parent's left subtree becomes the leftmost's right subtree. leftmostParent.Left = leftmost.Right; // Assign leftmost's left and right to current's left and right children. leftmost.Left = current.Left; leftmost.Right = current.Right; if (parent == null) _head = leftmost; else int result = parent.CompareTo(current.Value); if (result > 0) // Om föräldervärdet är större än nuvärdet, // gör vänstermodellens vänstra barn. parent.Left = leftmost; annars om (resultat < 0) // If parent value is less than current value, // make leftmost the parent's right child. parent.Right = leftmost; return true;
| Beteende | Returnerar sant om trädet innehåller det angivna värdet. Annars returneras det falskt. |
| Prestanda | O (log n) i genomsnitt; O (n) i värsta fall. |
innehåller försvarar till FindWithParent, som utför en enkel trädvandringsalgoritm som utför följande steg, börjar vid huvudnodet:
Eftersom innehåller returnerar a Boolean, Det returnerade värdet bestäms av huruvida FindWithParent returnerar en icke-null BinaryTreeNode (sant) eller en noll en (falsk).
De FindWithParent Metoden används också av Remove-metoden. Ut parametern, förälder, används inte av innehåller.
public bool Innehåller (T-värde) // Fördröjning till nodsökningshjälpfunktionen. BinaryTreeNode förälder; returnera FindWithParent (värde, förälder)! = null; /// /// Hitta och returnerar den första noden som innehåller det angivna värdet. Om värdet /// inte hittas returneras det null. Returnerar också föräldern till den funna noden (eller null) /// som används i Ta bort. /// privat BinaryTreeNode FindWithParent (T-värde, ut BinaryTreeNode förälder) // Nu försök att hitta data i trädet. BinaryTreeNode current = _head; förälder = null; // Medan vi inte har en match ... medan (nuvarande! = Null) int result = current.CompareTo (value); om (resultat> 0) // Om värdet är mindre än nuvarande, gå till vänster. förälder = ström; nuvarande = nuvarande.Left; annars om (resultat < 0) // If the value is more than current, go right. parent = current; current = current.Right; else // We have a match! break; return current;
| Beteende | Returnerar antalet värden i trädet (0 om det är tomt). |
| Prestanda | O (1) |
Räknefältet ökas av Lägg till metod och minskat av Ta bort metod.
offentlig inträkning get return _count;
| Beteende | Tar bort alla noder från trädet. |
| Prestanda | O (1) |
public void Clear () _head = null; _count = 0;
Traverskikt är algoritmer som tillåter bearbetning av varje värde i trädet i en väldefinierad ordning. För var och en av de diskuterade algoritmerna kommer följande träd att användas som provingången.
De exempel som följer alla accepterar en Verkan parameter. Denna parameter definierar åtgärden som kommer att appliceras på varje nod som den behandlas av traversalen.
Ordningsdelen för varje traversal kommer att indikera den ordning i vilken följande träd skulle passera.
Provträdet för övergripande beställningsresultat | Beteende | Utför den angivna åtgärden för varje värde i förbeställning (se beskrivningen som följer). |
| Prestanda | På) |
| Ordning | 4, 2, 1, 3, 5, 7, 6, 8 |
Preorder-traversen behandlar nuvarande nod innan du flyttar till vänster och sedan rätt barn. Startar vid rotknuten, fyra, utförs åtgärden med värdet fyra. Då bearbetas vänster nod och alla sina barn följt av rätt nod och alla sina barn.
En vanlig användning av preorder-traversen skulle vara att skapa en kopia av trädet som innehöll inte bara samma nodvärden utan också samma hierarki.
public void PreOrderTraversal (Åtgärdsåtgärd) PreOrderTraversal (action, _head); privat void PreOrderTraversal (Action action, BinaryTreeNode nod) if (node! = null) action (node.Value); PreOrderTraversal (action, node.Left); PreOrderTraversal (action, node.Right);
| Beteende | Utför den angivna åtgärden för varje värde i postorder (se beskrivningen som följer). |
| Prestanda | På) |
| Ordning | 1, 3, 2, 6, 8, 7, 5, 4 |
Postorder-traversen besöker vänster och höger barn på noden rekursivt och utför sedan åtgärden på nuvarande nod när barnen är färdiga.
Postorder-traversaler används ofta för att radera ett helt träd, till exempel i programmeringsspråk där varje nod måste frigöras, eller för att radera subtre. Detta är fallet eftersom rotknutpunkten bearbetas (raderad) sist och dess barn bearbetas på ett sätt som minimerar mängden arbete de Ta bort algoritmen behöver utföras.
public void PostOrderTraversal (Action action) PostOrderTraversal (action, _head); privat tomt PostOrderTraversal (Åtgärdsåtgärd, BinaryTreeNode nod) if (node! = null) PostOrderTraversal (action, node.Left); PostOrderTraversal (action, node.Right); åtgärden (node.Value);
| Beteende | Utför den angivna åtgärden för varje värde i i ordning (se beskrivningen som följer). |
| Prestanda | På) |
| Ordning | 1, 2, 3, 4, 5, 6, 7, 8 |
Inorder-traversal bearbetar noderna i sorteringsordningen - i föregående exempel, kommer noderna att sorteras i numerisk ordning från minsta till största. Det gör det genom att hitta den minsta (vänster) noden och sedan bearbeta den innan du bearbetar de större (högra) noderna.
Inorder-traverser används närhelst noderna måste behandlas i sorteringsordning.
Exemplet som följer visar två olika metoder för att utföra en inorder-traversal. Den första implementerar ett rekursivt tillvägagångssätt som utför en återuppringning för varje traverserad nod. Den andra tar bort rekursionen genom att använda Stack-datastrukturen och returnerar en IEnumerator för att tillåta direkt uppräkning.
Offentligt ogiltigt InOderTraversal (Action action) InOrderTraversal (action, _head); privat tomt InOrderTraversal (Action action, BinaryTreeNode nod) if (node! = null) InOrderTraversal (action, node.Left); åtgärden (node.Value); InOrderTraversal (action, node.Right); public IEnumerator InOrderTraversal () // Detta är en icke-rekursiv algoritm med en stapel för att visa bort // recursion. om (_head! = null) // Spara de noder vi har hoppat över i den här stapeln (undviker rekursion). Stack> stack = new Stack> (); BinaryTreeNode current = _head; // När vi tar bort rekursion, måste vi hålla reda på om // vi ska gå till vänster nod eller de rätta noderna nästa. bool goLeftNext = true; // Börja med att trycka huvudet på stapeln. stack.Push (ström); medan (stack.Count> 0) // Om vi är på väg till vänster ... om (goLeftNext) // Tryck på allt utom den vänstra noden till stapeln. // Vi ger mest efter det här blocket. medan (nuvarande.Left! = null) stack.Push (nuvarande); nuvarande = nuvarande.Left; // Inorder är kvar-> yield-> right. avkastningsströmmen.Value; // Om vi kan gå rätt, gör så. om (current.Right! = null) current = current.Right; // När vi har gått rätt gång, måste vi börja // gå till vänster igen. goLeftNext = true; else // Om vi inte kan gå rätt, måste vi springa av parentnoden // så att vi kan bearbeta det och sedan gå till sin högra nod. nuvarande = stack.Pop (); goLeftNext = false;
| Beteende | Returnerar en uppräknare som summerar med InOrder-traversalgoritmen. |
| Prestanda | O (1) för att returnera uppräknaren. Att räkna upp alla objekt är O (n). |
offentlig IEnumerator GetEnumerator () returnera InOrderTraversal (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return GetEnumerator ();
Accentsconagua