Rood-zwartboom

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Voorbeeld van een rood-zwarte boom

In de informatica is een rood-zwartboom een zelf-balancerende binaire zoekboom waarbij elke knoop voorzien wordt van de kleur zwart of rood om de boom bij aanpassingen te (her)balanceren. Rood-zwartbomen worden vaak gebruikt om associatieve arrays te implementeren.

Eigenschappen[bewerken]

Een rood-zwartboom is een binaire zoekboom waarvan de toppen ofwel rood, ofwel zwart gekleurd zijn en voldoet aan de volgende eigenschappen:

  • de wortel van een rood-zwartboom is zwart
  • de kinderen van een rode ouder zijn zwart
  • de bladeren van de rood-zwartboom zijn zwart
  • het aantal zwarte knopen op elk pad van de wortel naar een blad is steeds gelijk over de hele boom. Deze afstand wordt aangeduid met z(T).

Toevoegen[bewerken]

Het toevoegen van een sleutel aan een rood-zwartboom gebeurt steeds door een rood blad toe te voegen op de juiste plaats in de zoekboom. Als de ouder van deze knoop zwart is, dan wordt nog steeds aan alle eigenschappen voldaan en is er geen probleem. In het andere geval hebben we twee opeenvolgende rode knopen en moet er geherbalanceerd worden. Dit wordt gedaan door de twee rode knopen en diens ouder te vervangen door een perfecte binaire boom waarvan de wortel rood is en beide kinderen zwart zijn. Indien de wortel van deze nieuwe deelboom er voor zorgt dat er opnieuw twee opeenvolgende rode knopen zijn, dan passen we de procedure opnieuw toe. Zo schuift het probleem steeds één plaats hoger, en wanneer het de wortel bereikt van de boom bereikt kan men simpelweg de wortel zwart kleuren.

Efficiëntie[bewerken]

Een rood-zwartboom heeft minimaal 2^{z(t)}-1, zwarte knopen.

Bewijs (door inductie op het aantal knopen):

Een rood-zwartboom met 1 knoop (dit is dan een zwarte wortel) voldoet aan de definitie. Stel dus dat de stelling geldig is voor rood-zwartbomen met n knopen.

Beschouw T een rood-zwartboom met n+1 knopen. Ga vanaf de wortel van T naar links (resp. rechts) tot je de eerste zwarte knoop tegenkomt. Noem deze wl (resp. wr). wl en wr zijn beide wortels van rood-zwart bomen, waarbij het aantal zwarte knopen z'(t) gelijk is aan z(t)-1. Volgens de inductie-hypothese hebben beide dus 2^{z(t)-1}-1 knopen. Hier moet nog 1 knoop bij (de wortel van T) 2*(2^{z(t)-1}-1)+1=2^{z(t)}-1

Hetgeen aantoont dat voor een willekeurige rood-zwartboom met n toppen, de maximale diepte gegeven is door a*log(n) voor een willekeurige constante a. Anders gezegd, zoeken in een rood-zwartboom kan in logaritmische complexiteit.