Rood-zwartboom

Voorbeeld van een rood-zwarte boom

In de informatica is een rood-zwartboom een zelf-balancerende binaire boom 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.

Opstellen

De regels bij het opstellen van een rood-zwartboom zijn als volgt:

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

Herbalanceren

Bij het toevoegen of verwijderen van een knoop aan een rood-zwartboom moet men dus mogelijk de boom herbalanceren opdat deze nog voldoet aan de voornoemde eigenschappen. Dit wordt gedaan door de foute deelboom (dit is steeds een boom met 3 knopen, waarvan 2 rood zijn) te vervangen door een perfecte binaire boom waarvan de wortel rood is en beide kinderen zwart zijn. 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 (vermits deze op alle willekeurige paden ligt, en z(t) uniform beïnvloedt).

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.

Mediabestanden

Zie de categorie Red-black trees van Wikimedia Commons voor meer mediabestanden.