Pohon merah-hitam

Contoh dari sebuah pohon merah-hitam

Sebuah 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 di tahun 1972 oleh Rudolf Bayer yang menamai pohon ini "pohon B biner simetris". Tetapi nama modern dari pohon ini diperoleh dalam sebuah kertas di tahun 1978 oleh Leo J. Guibas dan Robert Sedgewick.