TechCodeview

Voordat u de Rood-zwarte boom en AVL-boom verschillen, moeten we de rood-zwarte boom en de AVL-boom afzonderlijk kennen.

Wat is een rood-zwarte boom?

De roodzwarte boom is een zelfbalancerende boom binaire zoekboom waarbij elk knooppunt één extra bit informatie bevat dat de kleur van het knooppunt aangeeft. De kleur van het knooppunt kan rood of zwart zijn, afhankelijk van de bitinformatie die door het knooppunt is opgeslagen.

abstractie in Java

Eigenschappen

Hieronder volgen de eigenschappen die verband houden met een rood-zwarte boom:

• Het hoofdknooppunt van de boom moet zwart zijn.
• Een rode knoop kan alleen zwarte kinderen hebben. Of we kunnen zeggen dat twee aangrenzende knooppunten niet rood van kleur kunnen zijn.
• Als het knooppunt geen linker- of rechterkind heeft, wordt dat knooppunt een bladknoop genoemd. Dus plaatsen we de linker en rechter kinderen onder het bladknooppunt dat bekend staat als nul

De zwarte diepte of zwarte hoogte van een bladknooppunt kan worden gedefinieerd als het aantal zwart dat we tegenkomen als we van het bladknooppunt naar het wortelknooppunt gaan. Een van de belangrijkste eigenschappen van de roodzwarte boom is dat elk bladknooppunt dezelfde zwarte diepte moet hebben.

Laten we deze eigenschap begrijpen aan de hand van een voorbeeld.

In de bovenstaande boom zijn er vijf knooppunten, waarvan er één rood is en de andere vier knooppunten zwart zijn. Er zijn drie bladknopen in de bovenstaande boom. Nu berekenen we de zwarte diepte van elk bladknooppunt. Zoals we kunnen zien is de zwarte diepte van alle drie de bladknopen 2; daarom is het een rood-zwarte boom.

Als de boom aan geen van de bovenstaande drie eigenschappen voldoet, is het geen rood-zwarte boom.

Hoogte van een roodzwarte boom

Beschouw h als de hoogte van de boom met n knooppunten. Wat zou de kleinste waarde van n zijn? De waarde van n is het kleinst als alle knooppunten zwart zijn. Als de boom alle zwarte knooppunten bevat, zou de boom een ​​volledige binaire boom zijn. Als de hoogte van een volledige binaire boom h is, dan is het aantal knooppunten in een boom:

n = 2u -1

Wat zou de grootste waarde van n zijn?

De waarde van n is het grootst wanneer elk zwart knooppunt twee rode kinderen heeft, maar het rode knooppunt kan geen rode kinderen hebben, zodat het zwarte kinderen zal hebben. Op deze manier zijn er afwisselende lagen van zwarte en rode kinderen. Dus als het aantal zwarte lagen h is, dan is het aantal rode lagen ook h; daarom wordt de totale hoogte van de boom 2 uur. Het totale aantal knooppunten is:

cm naar voet en inch

n = 2*2u-1

Wat is de AVL-boom?

Een AVL-boom is een zelfbalancerende binaire zoekboom als we het onderstaande geval observeren, dat een binaire zoekboom en een gebalanceerde boom is.

In de bovenstaande boom is de tijdscomplexiteit in het slechtste geval voor het zoeken naar een element O(h), dat wil zeggen de hoogte van de boom. In het bovenstaande geval is het aantal vergelijkingen dat is gemaakt om 17 elementen te doorzoeken 4, en is de hoogte van de boom ook 4.

Als we de scheve binaire boom beschouwen, zoals hieronder weergegeven:

In de scheve boom hierboven rechts is het aantal vergelijkingen dat is gemaakt om 17 elementen te doorzoeken 5, en het aantal elementen in de boom is ook 5. Daarom kunnen we zeggen dat als de boom een ​​scheve binaire boom is, de tijdscomplexiteit zou O(n) zijn.

Nu moeten we deze scheve bomen in evenwicht brengen, zodat ze de tijdscomplexiteit O(h) hebben. Er bestaat een term die bekend staat als a evenwichtsfactor , die wordt gebruikt om de binaire zoekboom in evenwicht te brengen. De balansfactor kan als volgt worden berekend:

statisch Java

De waarde van de balansfactor kan 1, 0 of -1 zijn. Als elk knooppunt in de binaire boom een ​​waarde van 1, 0 of -1 heeft, wordt van die boom gezegd dat hij een gebalanceerde boom is. binaire boom of AVL-boom.

De boom staat bekend als een perfect gebalanceerde boom als de balansfactor van elk knooppunt 0 is. De AVL-boom is een bijna gebalanceerde boom omdat elk knooppunt in de boom de waarde van de balansfactor 1, 0 of -1 heeft.

Verschillen tussen de rood-zwarte boom en de AVL-boom.

Hieronder volgen de verschillen tussen de rood-zwarte boom en de AVL-boom:

Binaire zoekboom

De rood-zwarte boom is een binaire zoekboom, en de AVL-boom is ook een binaire zoekboom.

Reglement

Bij een Rood-Zwarte Boom gelden de volgende regels:

1. Het knooppunt in een rood-zwarte boom is rood of zwart van kleur.
2. De kleur van het hoofdknooppunt moet zwart zijn.
3. De aangrenzende knooppunten mogen niet rood zijn. Met andere woorden, we kunnen zeggen dat het rode knooppunt geen rode kinderen kan hebben, maar dat het zwarte knooppunt wel zwarte kinderen kan hebben.
4. Er zou hetzelfde aantal zwarte knooppunten in elk pad moeten zijn; dan kan alleen een boom als een rood-zwarte boom worden beschouwd.
5. De externe knooppunten zijn de nulknooppunten, die altijd zwart van kleur zijn.

Regel van de AVL-boom:

Elk knooppunt moet de balansfactor hebben als -1, 0 of 1.

Voorbeeld

In de bovenstaande figuur moeten we controleren of de boom een ​​rood-zwarte boom is of niet. Om dit te controleren, moeten we eerst controleren of de boom een ​​binaire zoekboom is of niet. Zoals we in de bovenstaande figuur kunnen zien, voldoet het aan alle eigenschappen van de binaire zoekboom; daarom is het een binaire zoekboom. Ten tweede moeten we verifiëren of het aan de bovengenoemde regels voldoet of niet. De bovenstaande boom voldoet aan alle bovenstaande vijf regels; daarom wordt geconcludeerd dat de bovenstaande boom een ​​rood-zwarte boom is.

In de bovenstaande afbeelding moeten we controleren of de boom een ​​AVL-boom is of niet. Omdat elk knooppunt een waarde voor de balansfactor heeft van -1, 0 of 1, is het dus een AVL-boom.

Hoe kan de boom als een evenwichtige boom worden beschouwd of niet?

Als in het geval van een rood-zwarte boom aan alle bovenstaande regels is voldaan, op voorwaarde dat een boom een ​​binaire zoekboom is, dan wordt gezegd dat de boom een ​​rood-zwarte boom is.

Als in het geval van de AVL-boom de balansfactor -1, 0 of 1 is, wordt van de bovenstaande boom gezegd dat hij een AVL-boom is.

Gereedschappen die worden gebruikt voor het balanceren

Als de boom niet in balans is, worden er twee hulpmiddelen gebruikt om de boom in een Rood-Zwarte boom in evenwicht te brengen:

Opnieuw kleuren Rotatie

Als de boom niet in balans is, wordt één hulpmiddel gebruikt om de boom in de AVL-boom in evenwicht te brengen:

Rotatie

Efficiënt voor welke operatie

In het geval van de rood-zwarte boom zijn de invoeg- en verwijderbewerkingen efficiënt. Als de boom door het opnieuw kleuren in balans komt, zijn invoeg- en verwijderbewerkingen efficiënt in de rood-zwarte boom.

Java-visualizer

In het geval van de AVL-boom is de zoekbewerking efficiënt omdat er slechts één hulpmiddel nodig is om de boom in evenwicht te brengen.

Tijdcomplexiteit

In het rood-zwarte boomgeval is de tijdscomplexiteit voor alle bewerkingen, dat wil zeggen invoegen, verwijderen en zoeken, O(logn).

In het geval van een AVL-boom is de tijdscomplexiteit voor alle bewerkingen, dat wil zeggen invoegen, verwijderen en zoeken, O(logn).

Laten we de verschillen in de tabelvorm begrijpen.