avl tree heap data structure c
Deze tutorial biedt een gedetailleerde uitleg van AVL-bomen en heap-gegevensstructuur in C ++, samen met AVL Tree-voorbeelden voor een beter begrip:
AVL Tree is een in hoogte gebalanceerde binaire boom. Elk knooppunt is geassocieerd met een gebalanceerde factor die wordt berekend als het verschil tussen de hoogte van de linker substructuur en de rechter substructuur.
De AVL-boom is genoemd naar zijn twee uitvinders, namelijk G.M. Abelson-Velvety en E.M. Landis, en werd in 1962 gepubliceerd in hun paper 'Een algoritme voor de organisatie van informatie'.
Zoek hier de volledige C ++-trainingsserie.
Wat je leert:
AVL-structuur in C ++
Om de boom in evenwicht te brengen, moet de gebalanceerde factor voor elk knooppunt tussen -1 en 1 liggen. Zo niet, dan zal de boom uit balans raken.
Een voorbeeld van een AVL-structuur wordt hieronder weergegeven.
In de bovenstaande boom kunnen we zien dat het hoogteverschil tussen de linker en rechter substructuur 1 is. Dit betekent dat het een gebalanceerde BST is. Aangezien de balansfactor 1 is, betekent dit dat de linker substructuur één niveau hoger is dan de rechter substructuur.
Als de balansfactor 0 is, betekent dit dat de linker en rechter substructuur zich op hetzelfde niveau bevinden, d.w.z. dat ze dezelfde hoogte hebben. Als de balansfactor -1 is, dan is de linker substructuur één niveau lager dan de rechter substructuur.
De AVL-boom bepaalt de hoogte van een binaire zoekboom en voorkomt dat deze scheef komt te staan. Omdat wanneer een binaire boom scheef komt te staan, dit het slechtste geval (O (n)) is voor alle bewerkingen. Door de balansfactor te gebruiken, legt de AVL-boom een limiet op aan de binaire boom en houdt dus alle bewerkingen op O (log n).
AVL Tree-bewerkingen
Hieronder volgen de bewerkingen die worden ondersteund door AVL-bomen.
# 1) AVL Tree Insertion
Invoegbewerking in de C ++ AVL-structuur is hetzelfde als die van de binaire zoekboom. Het enige verschil is dat we de boom naar links of rechts moeten draaien om de balansfactor te behouden, zodat deze niet uit balans raakt.
# 2) Verwijdering van AVL-boom
De verwijderingsoperatie wordt ook op dezelfde manier uitgevoerd als de verwijderoperatie in een binaire zoekboom. We moeten de boom opnieuw in evenwicht brengen door enkele AVL Tree-rotaties uit te voeren.
AVL Tree-implementatie
Hieronder volgt het C ++ -programma om de AVL-structuur en zijn bewerkingen te demonstreren.
Uitgang:
In volgorde doorlopen voor de AVL-structuur is:
4 5 8 11 12 17 18
Om door te lopen na verwijdering van knooppunt 5:
4 8 11 12 17 18
Merk op dat we de hierboven getoonde voorbeeldboom hebben gebruikt om de AVL-boom in het programma te demonstreren.
Toepassingen van AVL-bomen
- AVL-bomen worden meestal gebruikt voor soorten sets en woordenboeken in het geheugen.
- AVL-bomen worden ook veel gebruikt in databasetoepassingen waarin minder vaak wordt ingevoegd en verwijderd, maar er wordt regelmatig gezocht naar vereiste gegevens.
- Het wordt gebruikt in applicaties die verbeterd zoeken vereisen, afgezien van de databasetoepassingen
HEAP-gegevensstructuur in C ++
Een heap in C ++ is een speciale boomgebaseerde datastructuur en is een complete binaire boom.
Heaps kunnen van twee soorten zijn:
- Min-hoop : In min-heap is het kleinste element de wortel van de boom en elk knooppunt is groter dan of gelijk aan zijn ouder.
- Max-hoop : In max-heap is het grootste element de wortel van de boom en is elk knooppunt kleiner dan of gelijk aan het bovenliggende element.
Beschouw de volgende reeks elementen:
10 20 30 40 50 60 70
De min-heap voor de bovenstaande gegevens wordt hieronder weergegeven:
De maximale heap met behulp van de bovenstaande gegevens wordt hieronder weergegeven:
Binaire Heap C ++
Een binaire heap is de gebruikelijke implementatie van een heap-gegevensstructuur.
Een binaire heap heeft de volgende eigenschappen:
- Het is een complete binaire boom als alle niveaus volledig zijn gevuld, behalve mogelijk het laatste niveau en het laatste niveau heeft zijn sleutels zoveel mogelijk over.
- Een binaire heap kan een min-heap of max-heap zijn.
Een binaire heap is een complete binaire boom en kan daarom het beste worden weergegeven als een array.
Laten we eens kijken naar de matrixweergave van de binaire heap.
Beschouw de volgende binaire heap.
In het bovenstaande diagram wordt traversal voor de binaire heap niveauvolgorde genoemd.
Dus de array voor de bovenstaande binaire heap wordt hieronder weergegeven als HeapArr:
Zoals hierboven getoond, is HeapArr [0] de root van de binaire heap. We kunnen de andere elementen in algemene termen als volgt weergeven:
Als HeapArr [i] een i isthknooppunt in een binaire heap, dan de indexen van de andere knooppunten van de ithknooppunt zijn:
- HeapArr [(i-1) / 2] => Geeft de bovenliggende node terug.
- HeapArr [(2 * i) +1] => Geeft het linker kindknooppunt terug.
- HeapArr [(2 * i) +2] => Geeft het rechter kindknooppunt terug.
De binaire heap voldoet aan de 'ordeningseigenschap' die uit twee typen bestaat, zoals hieronder vermeld:
selenium interviewvragen voor 3 jaar ervaring
- Min Heap-eigenschap: De minimumwaarde bevindt zich in de root en de waarde van elk knooppunt is groter dan of gelijk aan de bovenliggende waarde.
- Max Heap-eigenschap: De maximale waarde bevindt zich aan de basis en de waarde van elk knooppunt is kleiner dan of gelijk aan de bovenliggende waarde.
Bewerkingen op binaire hoop
Hieronder volgen de basisbewerkingen die op een minimale heap worden uitgevoerd. In het geval van de maximale heap worden de bewerkingen dienovereenkomstig omgekeerd.
# 1) Invoegen () - Voegt een nieuwe sleutel in aan het einde van de boom. Afhankelijk van de waarde van de ingevoerde sleutel, moeten we mogelijk de heap aanpassen zonder de heap-eigenschap te schenden.
# 2) Verwijderen () - Wist een sleutel. Opmerking dat de tijdcomplexiteit van zowel het invoegen als het verwijderen van de heap O (log n) is.
# 3) verlagenKey () - Verlaagt de waarde van de sleutel. Mogelijk moeten we de eigenschap heap behouden wanneer deze bewerking plaatsvindt. De tijdcomplexiteit van de afnameKey-bewerking van de heap is ook O (log n).
# 4) extractMin () - Verwijdert het minimumelement uit de min-heap. Het moet de eigenschap heap behouden na het verwijderen van het minimumelement. De tijdcomplexiteit is dus O (log n).
# 5) getMin () - Retourneert het root-element van de min-heap. Dit is de eenvoudigste bewerking en de tijdcomplexiteit voor deze bewerking is O (1).
Implementatie van heap-gegevensstructuur
Hieronder wordt de C ++ -implementatie weergegeven om de basisfunctionaliteit van min-heap te demonstreren.
Uitgang:
Hoop na inbrengen: 2 4 6 8 10 12
wortel van de hoop: 2
Heap na deletekey (2): 2 4 12 8 10
minimum element in de hoop: 2
nieuwe root van de heap na afname Sleutel: 1
Toepassingen van Heaps
- Heapsort: Heapsort-algoritme wordt effectief geïmplementeerd met behulp van een binaire heap.
- Prioriteitswachtrijen: Binaire heap ondersteunt alle bewerkingen die nodig zijn voor het succesvol implementeren van de prioriteitswachtrijen in O (log n) tijd.
- Grafiekalgoritmen: Sommige algoritmen met betrekking tot grafieken gebruiken een prioriteitswachtrij en op hun beurt gebruikt de prioriteitswachtrij een binaire heap.
- De complexiteit van het quicksort-algoritme in het ergste geval kan worden overwonnen door heap-sort te gebruiken.
Gevolgtrekking
In deze tutorial hebben we twee datastructuren gezien, namelijk AVL-bomen en Heap-sortering in detail.
AVL-bomen zijn gebalanceerde binaire bomen die meestal worden gebruikt bij het indexeren van databases.
Alle bewerkingen die worden uitgevoerd op AVL-bomen zijn vergelijkbaar met die van binaire zoekbomen, maar het enige verschil in het geval van AVL-bomen is dat we de balansfactor moeten behouden, d.w.z. dat de gegevensstructuur een gebalanceerde boom moet blijven als resultaat van verschillende bewerkingen. Dit wordt bereikt door gebruik te maken van de AVL Tree Rotation-bewerking.
Heaps zijn complete binaire boomstructuren die worden geclassificeerd in min-heap of max-heap. Min-heap heeft het minimumelement als root en de volgende knooppunten zijn groter dan of gelijk aan hun bovenliggende knooppunt. In max-heap is de situatie precies het tegenovergestelde, d.w.z. het maximale element is de root van de heap.
Heaps kunnen worden weergegeven in de vorm van arrays met de 0thelement als de wortel van de boom. Heap-datastructuren worden voornamelijk gebruikt om heap-sorteer- en prioriteitswachtrijen te implementeren.
Bezoek hier om C ++ vanaf het begin te leren.
Aanbevolen literatuur
- Wachtrijgegevensstructuur in C ++ met illustratie
- Stapel gegevensstructuur in C ++ met illustratie
- Circulaire gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Inleiding tot gegevensstructuren in C ++
- Prioriteitswachtrijgegevensstructuur in C ++ met illustratie
- Dubbel gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Heap-sortering in C ++ met voorbeelden