Diagram der viser et eksempel på et rød-sort træ.
Et rød-sort træ er en form for selv-balancerende binært søgetræ. Formålet med at have træet selv-balancerende er, at garantere, at højden på træet er O(lg n).
Et rød-sort træ er et træ der opfylder følgende 5 egenskaber:
Rød-sort træ / Definition
Rød-sort træ