Un árbol Rojo-Negro es un árbol binario de búsqueda auto-balanceado. Cada nodo de este árbol posee una información extra que es el color del nodo, este puede ser Rojo o Negro. La utilización de los colores es lo que hace que el árbol pueda quedar autobalanceado durante las inserciones o las eliminaciones de nodos.

• El equilibrio se conserva pintando cada nodo del árbol con uno de los dos colores de manera que satisfaga ciertas propiedades, que en conjunto restringen el desequilibrio en que el árbol puede caer en el peor de los casos.

• El equilibrio del árbol no es perfecto, pero es lo suficientemente bueno como para permitirle garantizar la búsqueda en el tiempo \(\O(logn)\), donde n es el número total de elementos en el árbol.