HAMA 블로그

레드블랙트리는 이진트리이자, 균형을 갖춘트리입니다. C++ 의 map 이 레드블랙트리 기반이며, jemalloc 에서도 사용됩니다.레드블랙트리의 정의는 다음과 같습니다.1. 모든 노드는 red나 black의 색깔을 갖는다. 2. Root 노드는 항상 black이다. 3. 모든 leaf 노드는 센티넬 노드(sentinel node)로서 black이다. (일단 항상 2개의 다른 값으로 채워질 수 있는 NIL=NULL 자식을 가진다.) 4. Red 노드의 자식은 모두 black이다. (Black의 자식은 black/red 모두 가능) 5. 루트(root)에서 leaf로의 경로를 생각할 때, 모든 경로에 대해서 black의 숫자는 같다. (이것을 black height라고 한다.) 삽입삽입시에 이진트리와 마찬가..