Pohon merah-hitam

Pohon merah-hitam (red-black tree) adalah jenis dari pohon biner terurut yang dapat menyeimbangkan dirinya sendiri, sebuah struktur data yang digunakan dalam ilmu komputer khususnya digunakan untuk mengimplementasikan array asosiatif. Struktur aslinya ditemukan pada tahun 1972 oleh Rudolf Bayer yang menamai pohon ini "pohon B biner simetris". Tetapi nama modern dari pohon ini diperoleh dalam sebuah publikasi pada tahun 1978 oleh Leo J. Guibas dan Robert Sedgewick.