A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them "symmetric binary B-tre
M. Thein, and M. Thwin. International Journal of Computer Science, Engineering and Information Technology (IJCSEIT), volume 2 of IFIP Advances in Information and Communication Technology, page 13-32. Springer, (December 2012)
T. Zhang, R. Ramakrishnan, and M. Livny. Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (SIGMOD'96), page 103--114. (1996)
R. Agrawal, A. Borgida, and H. Jagadish. Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989, page 253-262. ACM Press, (1989)