Rood-zwartboom

In de informatica is een rood-zwartboom een zelf-balancerende binaire zoekboom waarbij elke top 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

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

de wortel van een rood-zwartboom is altijd zwart
de kinderen van een rode top zijn zwart
het aantal zwarte toppen op elk pad van de wortel naar een blad is steeds gelijk over de hele boom. Deze afstand wordt aangeduid met $z(T)$ , waarbij T de boom voorstelt.

Toevoegen

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 ervoor 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 van de boom bereikt kan men simpelweg de wortel zwart kleuren. Dan verhoogt het aantal zwarte toppen op elk pad van de wortel naar een blad met een, maar het blijft wel voor alle paden gelijk.

Verwijderen

Een sleutel uit een rood-zwartboom verwijderen is gemakkelijker wanneer die sleutel een blad is. Meestal wordt een sleutel s die verwijderd moet worden dus omgewisseld met ofwel het kleinste element uit de deelboom groter dan s (de rechterdeelboom van s), ofwel het grootste element uit de deelboom kleiner dan s (de linkerdeelboom van s). Eens s dan in een blad zit, kan dit blad gewoon verwijderd worden. Is dat blad rood gekleurd, dan is er geen enkel probleem. Is dat blad echter zwart gekleurd, dan moet er geherbalanceerd worden op dezelfde manier als bij het toevoegen van een sleutel.

Efficiëntie

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.

Zie de categorie Red-black trees van Wikimedia Commons voor mediabestanden over dit onderwerp.