STL - set

namespace pmr {
    template<
        class Key,
        class Compare = std::less<Key>
    > using set = std::set<Key, Compare, std::pmr::polymorphic_allocator<Key>>;
}

 

Time Complexity

Red - Black Tree로 구현되어 search에 O(logn)의 시간이 걸리며, 삽입 및 삭제는 O(logn + a)의 시간이 걸린다.

 

Red - Black Tree

자가 균형 이진 탐색 트리로, 다음과 같은 조건들을 만족한다.

• 모든 노드는 빨간색 또는 검은색이다.
• 루트 노드는 검은색이다.
• 모든 리프 노드(NIL)들은 검은색이다.
• 빨간색 노드의 자식은 검은색이다. (즉, 빨간색 노드가 연속으로 나올 수 없다.)
• 모든 리프 노드에서 Black Depth는 같다 (즉, 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.)