STL map 구현 썸네일형 리스트형 Red Black Tree 소개 빨간색과 검은색 노드로 이루어진 균형 이진 트리 이진트리가 편향되어 O(n)의 탐색효율을 가지게 되는것을 방지한다. O(logn) 탐색은 빠르나 삽입, 삭제는 다소 느릴 수 있다. (Rebalance 때문) 조건 1. 모든 노드는 빨간색 혹은 검은색의 색상을 가진다. 2. 루트 노드는 검은색이다. 3. 단말 노드는 검은색이다. 4. 빨간색 노드의 자식들은 모두 검은색이다 (검은 노드의 자식이 빨간색일 필요는 없다.) 5. 루트노드에서 단말노드까지의 검은색 노드의 수는 동일하다. NIL 노드란 ? 검은색으로 생각하는 더미노드로 알고리즘의 구현을 편하게 해준다. 3번의 경우를 만족시킬 수도 있고, 다양한 예외처리에 사용하기 편하다. 구현 Color Type 노드의 색상을 나타내는 열거형 (enum) N.. 더보기 이전 1 다음
