Share
Tot nu toe hebben we gekeken naar datastructuren die data op een lineaire manier ordenen. Gekoppelde lijsten bevatten gegevens van een enkel startknooppunt tot een enkel aansluitknooppunt. Arrays bevatten gegevens in aaneengesloten, eendimensionale blokken.
In deze sectie zullen we zien hoe het toevoegen van nog een dimensie ons in staat zal stellen een nieuwe gegevensstructuur te introduceren: de boom. In het bijzonder zullen we kijken naar een soort boom die bekend staat als een binaire zoekboom. Binaire zoekbomen nemen de algemene boomstructuur en passen een reeks eenvoudige regels toe die de structuur van de structuur bepalen.
Voordat we meer te weten komen over die regels, laten we eens kijken wat een boom is.
Een boom is een gegevensstructuur waarbij elk knooppunt nul of meer kinderen heeft. We hebben bijvoorbeeld een boom als deze:
Een organisatorische boomstructuur In deze structuur kunnen we de organisatiestructuur van een bedrijf zien. De blokken vertegenwoordigen mensen of divisies binnen het bedrijf en de regels vertegenwoordigen rapportagerelaties. Een boom is een zeer efficiënte, logische manier om deze informatie te presenteren en op te slaan.
De boom in de vorige afbeelding is een algemene boom. Het representeert ouder / kind relaties, maar er zijn geen regels voor de structuur. De CEO heeft één direct rapport, maar kan net zo goed geen of twintig hebben. In de afbeelding wordt de omzet links van Marketing weergegeven, maar die volgorde heeft geen betekenis. In feite is de enige waarneembare beperking dat elk knooppunt maximaal één ouder heeft (en het bovenste knooppunt, de raad van bestuur, geen ouder heeft).
Een binaire zoekboom gebruikt dezelfde basisstructuur als de algemene structuur die in de laatste figuur wordt getoond, maar met de toevoeging van een paar regels. Deze regels zijn:
Laten we eens kijken naar een structuur die is opgebouwd met behulp van deze regels:
Binaire zoekboom Merk op hoe de beperkingen die we hebben gespecificeerd worden afgedwongen in het diagram. Elke waarde links van het basisknooppunt (acht) heeft een waarde van minder dan acht en elke waarde rechts is groter dan of gelijk aan het basisknooppunt. Deze regel is recursief van toepassing op elk knooppunt onderweg.
Laten we met deze boom in gedachten eens nadenken over de stappen die zijn gezet om dit te bouwen. Toen het proces begon, was de boom leeg en toen werd een waarde, acht, toegevoegd. Omdat het de eerste toegevoegde waarde was, werd deze in de hoofdmap (uiteindelijke bovenliggende positie) geplaatst.
We weten niet de exacte volgorde waarin de rest van de knooppunten zijn toegevoegd, maar ik zal een mogelijk pad presenteren. Waarden worden toegevoegd met behulp van een methode met de naam Toevoegen dat aanvaardt de waarde.
BinaryTree tree = new BinaryTree (); tree.Add (8); tree.Add (4); tree.Add (2); tree.Add (3); tree.Add (10); tree.Add (6); tree.Add (7);
Laten we door de eerste paar items lopen.
Acht werd als eerste toegevoegd en werd de wortel. Vervolgens is er vier toegevoegd. Aangezien vier minder dan acht zijn, moet deze links van acht van regel nummer twee worden ingevoerd. Omdat er geen acht kinderen aan de linkerkant zijn, wordt vier het onmiddellijk achtergebleven kind van acht.
Twee wordt toegevoegd. twee is minder dan acht, dus het gaat naar links. Er is al een knooppunt links van acht, dus de vergelijkingslogica wordt opnieuw uitgevoerd. twee is minder dan vier, en vier heeft geen linker kind, dus twee worden het linker kind van vier.
Drie wordt toegevoegd en gaat links van acht en vier. In vergelijking met de twee knooppunten is deze groter, dus drie worden toegevoegd aan de rechterkant van twee volgens regel nummer drie.
Deze cyclus van waarden vergelijken op elk knooppunt en vervolgens elk kind steeds opnieuw controleren totdat de juiste slot is gevonden, wordt voor elke waarde herhaald totdat de laatste boomstructuur is gemaakt.
De BinaryTreeNode staat voor een enkel knooppunt in de boom. Het bevat verwijzingen naar de linker en rechter kinderen (null als er geen zijn), de waarde van het knooppunt en de IComparable.CompareTo methode waarmee de knooppuntwaarden kunnen worden vergeleken om te bepalen of de waarde naar links of rechts van het huidige knooppunt moet gaan. Dit is het geheel BinaryTreeNode klasse - zoals u kunt zien, het is heel eenvoudig.
class BinaryTreeNode: ICvergelijkbaar waarbij TNode: ICvergelijkbaar public BinaryTreeNode (TNode value) Waarde = waarde; public BinaryTreeNode Left get; vast te stellen; public BinaryTreeNode Right get; vast te stellen; public TNode Value get; privé set; /// /// Vergelijkt het huidige knooppunt met de opgegeven waarde. /// /// De knooppuntwaarde die moet worden vergeleken met /// 1 als de exemplaarwaarde groter is dan /// de opgegeven waarde, -1 als minder, of 0 als gelijk. openbare int CompareTo (andere TNode) return Value.CompareTo (other);
De BinaryTree class biedt de basismethoden die je nodig hebt om de tree te manipuleren: Toevoegen, Verwijderen, een bevat methode om te bepalen of een item bestaat in de boom, verschillende traversal en opsommingsmethoden (dit zijn methodes die ons toelaten de knopen in de boom op te sommen in verschillende goed gedefinieerde orders), en de normale tellen en Duidelijk methoden.
Om de boom te initialiseren, is er een BinaryTreeNode verwijzing die het hoofd (wortel) knooppunt van de boom vertegenwoordigt, en er is een geheel getal dat bijhoudt hoeveel items in de boom staan.
public class BinaryTree: IEnumerable waarbij T: ICvergelijkbaar private BinaryTreeNode _head; privé int _count; public void Toevoegen (T-waarde) gooi new NotImplementedException (); public bool Bevat (T-waarde) gooi nieuwe NotImplementedException (); public bool Remove (T-waarde) gooi nieuwe NotImplementedException (); public void PreOrderTraversal (Action action) gooi nieuwe NotImplementedException (); public void PostOrderTraversal (actie actie) gooi nieuwe NotImplementedException (); public void InOrderTraversal (actie actie) gooi nieuwe NotImplementedException (); public IEnumerator GetEnumerator () gooi nieuwe NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () throw new NotImplementedException (); public void Clear () throw new NotImplementedException (); openbare int Graaf krijgen;
| Gedrag | Voegt de opgegeven waarde toe aan de juiste locatie in de structuur. |
| Prestatie | O (log n) gemiddeld; O (n) in het slechtste geval. |
Het toevoegen van een knoop aan de boom is niet erg ingewikkeld en wordt nog eenvoudiger wanneer het probleem wordt vereenvoudigd tot een recursief algoritme. Er zijn twee gevallen die moeten worden overwogen:
In het eerste geval, wijzen we eenvoudig het nieuwe knooppunt toe en voegen het toe aan de boom. In het tweede geval vergelijken we de waarde met de waarde van het knooppunt. Als de waarde die we proberen toe te voegen minder is dan de waarde van het knooppunt, wordt het algoritme herhaald voor het linker kind van het knooppunt. Anders wordt het herhaald voor het juiste kind van het knooppunt.
public void Toevoegen (T-waarde) // Case 1: De boom is leeg. Wijs het hoofd toe. if (_head == null) _head = new BinaryTreeNode (value); // Casus 2: de boom is niet leeg, dus recursief // vind de juiste locatie om het knooppunt in te voegen. else AddTo (_head, value); _count ++; // Recursief algoritme toevoegen. private void AddTo (BinaryTreeNode node, T-waarde) // Geval 1: Waarde is minder dan de huidige knooppuntwaarde if (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);
| Gedrag | Verwijdert de eerste gevonden noorder met de aangegeven waarde. |
| Prestatie | O (log n) gemiddeld; O (n) in het slechtste geval. |
Het verwijderen van een waarde uit de boom is een conceptueel eenvoudige handeling die in de praktijk verrassend complex wordt.
Op een hoog niveau is de werking eenvoudig:
De eerste stap is eenvoudig, en zoals we zullen zien, wordt bereikt met behulp van hetzelfde mechanisme dat de methode Bevat gebruikt. Nadat het te verwijderen knooppunt is geïdentificeerd, kan de bewerking echter een van de drie paden volgen die worden bepaald door de staat van de boom rond het knooppunt dat moet worden verwijderd. De drie toestanden worden beschreven in de volgende drie gevallen.
Eerste geval: het knooppunt dat moet worden verwijderd, heeft geen rechterkind.
Geval 1 Het knooppunt dat moet worden verwijderd, heeft geen rechterkind In dit geval kan de verwijderingsbewerking eenvoudig het linkerkind, als er een is, verplaatsen naar de plaats van het verwijderde knooppunt. De resulterende boom zou er als volgt uitzien:
Case 1 - Boom staat na verwijdering Geval twee: het te verwijderen knooppunt heeft een rechterkind dat op zijn beurt geen linkerkind heeft.
Geval twee Het knooppunt dat moet worden verwijderd, heeft een rechterkind dat geen linkerkind heeft In dit geval willen we het rechter kind van het verwijderde knooppunt (zes) verplaatsen naar de plaats van het verwijderde knooppunt. De resulterende boom ziet er als volgt uit:
Boom staat na verwijdering Case drie: Het knooppunt dat moet worden verwijderd, heeft een rechterkind dat op zijn beurt een linkerkind heeft.
Geval 3 - Het te verwijderen knooppunt heeft een rechterkind dat een linkerkind heeft In dit geval moet het meest linkse kind van het rechterkind van het verwijderde knooppunt in de sleuf van het verwijderde knooppunt worden geplaatst.
Laten we even nadenken over waarom dit waar is. Er zijn twee feiten die we kennen over de subboom die begint met het knooppunt dat verwijderd wordt (bijvoorbeeld de subboom waarvan de root het knooppunt is met de waarde vijf).
We moeten een waarde in de sleuf van het verwijderde knooppunt plaatsen die kleiner is dan of gelijk is aan elk knooppunt rechts ervan. Om dat te doen, moeten we de kleinste waarde aan de rechterkant krijgen. Daarom hebben we het linkse knooppunt van het rechter kind nodig.
Na het verwijderen van het knooppunt ziet de boom er als volgt uit:
Case 3 - Boom na knoop verwijdering Nu we de drie verwijderingsscenario's begrijpen, laten we eens naar de code kijken om het voor elkaar te krijgen.
Een ding om op te merken: de FindWithParent methode (zie de sectie Bevat) retourneert het knooppunt dat moet worden verwijderd en het bovenliggende knooppunt dat wordt verwijderd. Dit wordt gedaan omdat wanneer het knooppunt wordt verwijderd, we de parent's moeten bijwerken Links of Rechts eigenschap om naar het nieuwe knooppunt te wijzen.
We zouden dit kunnen vermijden als alle knooppunten een verwijzing naar hun ouder zouden houden, maar dat zou per knooppunt geheugenoverhead en boekhoudkosten introduceren die alleen in dit ene geval nodig zijn.
public bool Verwijderen (T-waarde) BinaryTreeNode current, parent; // Zoek het te verwijderen knooppunt. current = FindWithParent (waarde, ouder buiten); if (current == null) return false; _count--; // Geval 1: als de huidige geen rechterkind heeft, vervangt de huidige links de huidige. if (current.Right == null) if (parent == null) _head = current.Left; else int result = parent.CompareTo (current.Value); if (resultaat> 0) // Als de bovenliggende waarde groter is dan de huidige waarde, // maakt het huidige linker kind een linkerkind van het bovenliggende element. parent.Left = current.Left; else if (resultaat < 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) // Als de bovenliggende waarde groter is dan de huidige waarde, // maak van het huidige rechter kind een linkerkind van het bovenliggende element. parent.Left = current.Right; else if (resultaat < 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) // Als de bovenliggende waarde groter is dan de huidige waarde, // maakt u het linker onderliggende kind van de ouder. parent.Left = meest links; else if (resultaat < 0) // If parent value is less than current value, // make leftmost the parent's right child. parent.Right = leftmost; return true;
| Gedrag | Retourneert true als de boom de opgegeven waarde bevat. Anders wordt false geretourneerd. |
| Prestatie | O (log n) gemiddeld; O (n) in het slechtste geval. |
bevat verdedigt naar FindWithParent, die een eenvoudig tree-walking algoritme uitvoert dat de volgende stappen uitvoert, beginnend bij het hoofdknooppunt:
Sinds bevat geeft a terug Boolean, de geretourneerde waarde wordt bepaald door of FindWithParent geeft een niet-nul terug BinaryTreeNode (waar) of een null (false).
De FindWithParent methode wordt ook gebruikt door de methode Verwijderen. De parameter out, parent, wordt niet gebruikt door bevat.
public bool Bevat (T-waarde) // Uitstel voor de knoopzoekhulpfunctie. BinaryTreeNode bovenliggende; return FindWithParent (waarde, ouder out)! = null; /// /// Zoekt en retourneert het eerste knooppunt dat de opgegeven waarde bevat. Als de waarde /// niet wordt gevonden, wordt deze null geretourneerd. Retourneert tevens het bovenliggende element van het gevonden knooppunt (of null) /// dat wordt gebruikt in Verwijderen. /// private BinaryTreeNode FindWithParent (T-waarde, ouderlijke ouder BinaryTreeNode) // Probeer nu gegevens in de structuur te vinden. BinaryTreeNode current = _head; parent = null; // Hoewel we geen overeenkomst hebben ... while (current! = Null) int result = current.CompareTo (value); if (resultaat> 0) // Als de waarde minder is dan de huidige waarde, ga dan naar links. parent = current; stroom = stroom. Verlaten; else if (resultaat < 0) // If the value is more than current, go right. parent = current; current = current.Right; else // We have a match! break; return current;
| Gedrag | Retourneert het aantal waarden in de structuur (0 als leeg). |
| Prestatie | O (1) |
Het telveld wordt verhoogd met de Toevoegen methode en verlaagd door de Verwijderen methode.
public int Count krijg return _count;
| Gedrag | Verwijdert alle knooppunten van de boom. |
| Prestatie | O (1) |
public void Wissen () _head = null; _count = 0;
Tree traversals zijn algoritmen die het mogelijk maken om elke waarde in de boom in een welbepaalde volgorde te verwerken. Voor elk van de besproken algoritmen wordt de volgende boom gebruikt als de monsterinvoer.
De voorbeelden die volgen, accepteren allemaal een Actie parameter. Deze parameter definieert de actie die op elk knooppunt wordt toegepast wanneer het door de traversal wordt verwerkt.
Het gedeelte Bestelling voor elke passage geeft de volgorde aan waarin de volgende boom zou doorlopen.
De voorbeeldboom voor resultaten van traversale bestellingen | Gedrag | Voert de geleverde actie uit op elke waarde in preorder (zie de beschrijving die volgt). |
| Prestatie | Op) |
| Bestellen | 4, 2, 1, 3, 5, 7, 6, 8 |
De preorder traversal verwerkt het huidige knooppunt voordat het naar links gaat en dan naar rechts kinderen. Beginnend bij het wortelknooppunt, vier, wordt de actie uitgevoerd met de waarde vier. Vervolgens worden het linkerknooppunt en alle onderliggende elementen verwerkt, gevolgd door het rechterknooppunt en alle onderliggende elementen.
Een veelgebruikt gebruik van de preorder traversal zou zijn om een kopie te maken van de boom die niet alleen dezelfde knooppuntwaarden bevat, maar ook dezelfde hiërarchie.
public void PreOrderTraversal (Action action) PreOrderTraversal (action, _head); private void PreOrderTraversal (Action action, BinaryTreeNode node) if (node! = null) action (node.Value); PreOrderTraversal (actie, knooppunt.Links); PreOrderTraversal (actie, knooppunt.Rechts);
| Gedrag | Voert de geleverde actie uit op elke waarde in de postorder (zie de beschrijving die volgt). |
| Prestatie | Op) |
| Bestellen | 1, 3, 2, 6, 8, 7, 5, 4 |
De postorder traversal bezoekt het linker en rechter kind van het knooppunt recursief en voert dan de actie uit op het huidige knooppunt nadat de kinderen compleet zijn.
Traceringen van postorders worden vaak gebruikt om een volledige boomstructuur te verwijderen, bijvoorbeeld in programmeertalen waarbij elk knooppunt moet worden vrijgegeven, of om substructuren te verwijderen. Dit is het geval omdat het hoofdknooppunt het laatst is verwerkt (verwijderd) en de kinderen zo zijn verwerkt dat de hoeveelheid werk die wordt Verwijderen algoritme moet uitvoeren.
public void PostOrderTraversal (Action action) PostOrderTraversal (action, _head); private void PostOrderTraversal (Action action, BinaryTreeNode node) if (node! = null) PostOrderTraversal (action, node.Left); PostOrderTraversal (actie, knooppunt.Rechts); Actie (node.Value);
| Gedrag | Voert de opgegeven actie uit voor elke waarde in in volgorde (zie de beschrijving die volgt). |
| Prestatie | Op) |
| Bestellen | 1, 2, 3, 4, 5, 6, 7, 8 |
In volgorde traversale processen de knooppunten in de sorteervolgorde - in het vorige voorbeeld zouden de knooppunten in numerieke volgorde worden gesorteerd van klein naar groot. Dit gebeurt door het kleinste (meest linkse) knooppunt te vinden en het vervolgens te verwerken voordat de grotere (rechter) knooppunten worden verwerkt.
Inorder-traversalen worden altijd gebruikt wanneer de knooppunten in sorteervolgorde moeten worden verwerkt.
Het volgende voorbeeld toont twee verschillende methoden voor het uitvoeren van een inorder-traversal. De eerste implementeert een recursieve benadering die een callback uitvoert voor elk doorkruist knooppunt. De tweede verwijdert de recursie door het gebruik van de Stack-gegevensstructuur en retourneert een IEnumerator om directe opsomming toe te staan.
Public void InOrderTraversal (actie actie) InOrderTraversal (actie, _head); private void InOrderTraversal (Action action, BinaryTreeNode node) if (node! = null) InOrderTraversal (action, node.Left); Actie (node.Value); InOrderTraversal (actie, node.Right); public IEnumerator InOrderTraversal () // Dit is een niet-recursief algoritme dat een stack gebruikt om het verwijderen / recursie aan te tonen. if (_head! = null) // Sla de knooppunten op die we in deze stapel hebben overgeslagen (vermijdt recursie). Stack> stack = new Stack> (); BinaryTreeNode current = _head; // Bij het verwijderen van recursie moeten we bijhouden of // we naar het linkerknooppunt of de juiste knooppunten moeten gaan. bool goLeftNext = true; // Begin door Head op de stapel te duwen. stack.Push (stroom); while (stack.Count> 0) // Als we naar links gaan ... if (goLeftNext) // Duw alles behalve het meest linkse knooppunt naar de stapel. // We zullen het meest links na dit blok opleveren. while (current.Left! = null) stack.Push (current); stroom = stroom. Verlaten; // Inorder is left-> yield-> right. opbrengst retourstroom. Waarde; // Als we gelijk kunnen doen, doe dat dan. if (current.Right! = null) current = current.Right; // Als we eenmaal gelijk hebben, moeten we // opnieuw links gaan. goLeftNext = true; else // Als we niet gelijk kunnen gaan, moeten we het bovenliggende knooppunt // verwijderen, zodat we het kunnen verwerken en naar het juiste knooppunt gaan. current = stack.Pop (); goLeftNext = false;
| Gedrag | Retourneert een enumerator die opsommingst met behulp van het InOrder-traversaalalgoritme. |
| Prestatie | O (1) om de teller te retourneren. Het opsommen van alle items is O (n). |
public IEnumerator GetEnumerator () return InOrderTraversal (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return GetEnumerator ();
Accentsconagua