이즈미르의 프로그래밍

이번에는 레드 블랙 트리를 정리해 보도록 하자. 사실 알고리즘보단 자료구조에 가까운 느낌이다. 그래도 C++ stl에서 사용하고 있어서 한 번쯤은 구현해볼 가치가 있다. 이름에서 알 수 있듯이 트리(tree)를 기반으로 한다. 이진트리(binary tree)에서 최악의 구조가 발생하지 않도록 여러 규칙들을 걸어 놓았다. 먼저 규칙들을 살펴보자. (출처는 위키백과 : https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties) [규칙 1] Each node is either red or black. (노드는 레드 혹은 블랙 중의 하나이다.) [규칙 2] The root is black. (루트 노드는 블랙이다.) [규칙 3] All leaves (NI..