Red-Black tree
레드-블랙 트리는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조이다. 최초의 구조는 1972년 루돌프 바이어가 창안했으며, 이를 "대칭형 이진 B-트리"라고 불렀고, 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 발표한 논문에서 레드-블랙 트리라는 이름이 등장하게 되었다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n) 의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.