C++ 표준 라이브러리에 빨간색 검정 트리 또는 avl 트리 구현이 있습니까?

-1

멀티 세트와 마찬가지로 STL의 바이너리 검색 트리 구현은 RB 트리 또는 AVL 트리 구현을 사용할 수 있습니까?C++ 표준 라이브러리에 빨간색 검정 트리 또는 avl 트리 구현이 있습니까?

2017-03-04 ash

std :: map은 빨간색/검정색 트리입니다. 표준은 그것이 반드시 하나가되어야한다고 말하지는 않지만, 성능 보증은 다른 어떤 것이 사용될 것 같지 않게합니다. –

대부분의 표준 라이브러리 구현은 네 개의 (다중) 집합 맵 모두에 대해 RB 트리를 사용합니다. 그러나 표준에서는 구현을 지정하지 않습니다. – Zulan

일반적으로 multiset을 이진 트리로 구현하지 않습니다. 하나를 사용하면 트리가 O (logN) 삽입 및 제거가없는 링크 된 목록처럼 보이기 때문에 표준의 성능 보장을 깨뜨릴 수 있습니다.

일반적으로 std::set/std::multiset/std::map/std::multimap은 성능이 보장되므로 RB 트리로 구현됩니다. 그러나 이것은 필요하지 않습니다. 표준은 다른 작업에서 컨테이너의 성능만을 보장하며이를 구현하는 방법은 구현에 달려 있습니다.

RB 트리를 사용하고 있는지 확인하려면 구현을 확인하거나 직접 롤링하거나 RB 트리임을 보증하는 타사 라이브러리를 가져야합니다.

출처

2017-03-04 15:37:49 NathanOliver

고마워. :) – ash

붉은 검정색 나무는 이진 나무입니다. 균형 이진 트리. –

C++ 표준 라이브러리에 빨간색 검정 트리 또는 avl 트리 구현이 있습니까?

답변

관련 문제