CRBTree 클래스

  • 아티클

이 클래스는 Red-Black 트리를 만들고 활용하는 메서드를 제공합니다.

구문

template <typename K,
          typename V,
          class KTraits = CElementTraits<K>,
          class VTraits = CElementTraits<V>>
class CRBTree

매개 변수

K
키 요소 형식입니다.

V
값 요소 형식입니다.

KTraits
키 요소를 복사하거나 이동하는 데 사용되는 코드입니다. 자세한 내용은 CElementTraits 클래스를 참조하세요.

VTraits
값 요소를 복사하거나 이동하는 데 사용되는 코드입니다.

멤버

공용 Typedefs

속성 설명
CRBTree::KINARGTYPE 키가 입력 인수로 전달될 때 사용되는 형식입니다.
CRBTree::KOUTARGTYPE 키가 출력 인수로 반환되는 경우 사용되는 형식입니다.
CRBTree::VINARGTYPE 값이 입력 인수로 전달될 때 사용되는 형식입니다.
CRBTree::VOUTARGTYPE 값이 출력 인수로 전달될 때 사용되는 형식입니다.

public 클래스

속성 설명
CRBTree::CPair 클래스 키 및 값 요소를 포함하는 클래스입니다.

공용 생성자

속성 설명
CRBTree::~CRBTree 소멸자입니다.

공용 메서드

이름 설명
CRBTree::FindFirstKeyAfter 이 메서드를 호출하여 사용 가능한 다음 키를 사용하는 요소의 위치를 찾습니다.
CRBTree::GetAt 이 메서드를 호출하여 트리의 지정된 위치에 있는 요소를 가져옵니다.
CRBTree::GetCount 이 메서드를 호출하여 트리의 요소 수를 가져옵니다.
CRBTree::GetHeadPosition 이 메서드를 호출하여 트리의 머리에서 요소의 위치 값을 가져옵니다.
CRBTree::GetKeyAt 이 메서드를 호출하여 트리의 지정된 위치에서 키를 가져옵니다.
CRBTree::GetNext 개체에 저장된 CRBTree 요소에 대한 포인터를 가져오고 위치를 다음 요소로 이동하려면 이 메서드를 호출합니다.
CRBTree::GetNextAssoc 이 메서드를 호출하여 지도에 저장된 요소의 키와 값을 가져와서 위치를 다음 요소로 진행합니다.
CRBTree::GetNextKey 트리에 저장된 요소의 키를 가져와 위치를 다음 요소로 이동하려면 이 메서드를 호출합니다.
CRBTree::GetNextValue 트리에 저장된 요소의 값을 가져와서 위치를 다음 요소로 이동하려면 이 메서드를 호출합니다.
CRBTree::GetPrev 이 메서드를 호출하여 개체에 저장된 요소에 대한 포인터를 CRBTree 가져온 다음 위치를 이전 요소로 업데이트합니다.
CRBTree::GetTailPosition 이 메서드를 호출하여 트리의 꼬리에 있는 요소의 위치 값을 가져옵니다.
CRBTree::GetValueAt 개체의 지정된 위치에 저장된 값을 검색하려면 이 메서드를 CRBTree 호출합니다.
CRBTree::IsEmpty 빈 트리 개체를 테스트하려면 이 메서드를 호출합니다.
CRBTree::RemoveAll 개체에서 모든 요소를 제거하려면 이 메서드를 호출합니다 CRBTree .
CRBTree::RemoveAt 개체의 지정된 위치에 있는 요소를 제거하려면 이 메서드를 CRBTree 호출합니다.
CRBTree::SetValueAt 개체의 지정된 위치에 저장된 값을 변경하려면 이 메서드를 CRBTree 호출합니다.

설명

빨간색-검은색 트리는 노드당 추가 정보를 사용하여 "균형"으로 유지되도록 하는 이진 검색 트리입니다. 즉, 트리 높이가 불균형적으로 커지지 않고 성능에 영향을 주지 않습니다.

이 템플릿 클래스는 CRBMap 및 CRBMultiMap에서 사용하도록 설계되었습니다. 이러한 파생 클래스를 구성하는 메서드의 대부분은 .에서 제공합니다 CRBTree.

다양한 컬렉션 클래스 및 해당 기능 및 성능 특성에 대한 자세한 내용은 ATL 컬렉션 클래스를 참조 하세요.

요구 사항

헤더: atlcoll.h

CRBTree::CPair 클래스

키 및 값 요소를 포함하는 클래스입니다.

class CPair : public __POSITION

설명

이 클래스는 CRBTree::GetAt, CRBTree::GetNext 및 CRBTree::GetPrev 메서드에서 트리 구조에 저장된 키 및 값 요소에 액세스하는 데 사용됩니다.

멤버는 다음과 같습니다.

데이터 멤버 설명
m_key 키 요소를 저장하는 데이터 멤버입니다.
m_value 값 요소를 저장하는 데이터 멤버입니다.

CRBTree::~CRBTree

소멸자입니다.

~CRBTree() throw();

설명

할당된 리소스를 해제합니다. CRBTree::RemoveAll을 호출하여 모든 요소를 삭제합니다.

CRBTree::FindFirstKeyAfter

이 메서드를 호출하여 사용 가능한 다음 키를 사용하는 요소의 위치를 찾습니다.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

매개 변수

key
키 값입니다.

Return Value

사용 가능한 다음 키를 사용하는 요소의 위치 값을 반환합니다. 요소가 더 이상 없으면 NULL이 반환됩니다.

설명

이 메서드를 사용하면 위치 값을 미리 계산하지 않고도 트리를 쉽게 트래버스할 수 있습니다.

CRBTree::GetAt

이 메서드를 호출하여 트리의 지정된 위치에 있는 요소를 가져옵니다.

CPair* GetAt(POSITION pos) throw();
const CPair* GetAt(POSITION pos) const throw();
void GetAt(POSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;

매개 변수

pos
위치 값입니다.

key
키를 받는 변수입니다.

value
값을 받는 변수입니다.

Return Value

처음 두 폼은 CPair에 대한 포인터를 반환합니다. 세 번째 폼은 지정된 위치에 대한 키와 값을 가져옵니다.

설명

위치 값은 CRBTree::GetHeadPosition 또는 CRBTree::GetTailPosition과 같은 메서드를 호출하여 이전에 확인할 수 있습니다.

디버그 빌드에서 pos가 NULL과 같으면 어설션 오류가 발생합니다.

CRBTree::GetCount

이 메서드를 호출하여 트리의 요소 수를 가져옵니다.

size_t GetCount() const throw();

Return Value

트리에 저장된 요소 수(각 키/값 쌍은 하나의 요소)를 반환합니다.

CRBTree::GetHeadPosition

이 메서드를 호출하여 트리의 머리에서 요소의 위치 값을 가져옵니다.

POSITION GetHeadPosition() const throw();

Return Value

트리의 헤드에 있는 요소의 위치 값을 반환합니다.

설명

반환된 GetHeadPosition 값은 CRBTree::GetKeyAt 또는 CRBTree::GetNext와 같은 메서드와 함께 사용하여 트리를 트래버스하고 값을 검색할 수 있습니다.

CRBTree::GetKeyAt

이 메서드를 호출하여 트리의 지정된 위치에서 키를 가져옵니다.

const K& GetKeyAt(POSITION pos) const throw();

매개 변수

pos
위치 값입니다.

Return Value

트리의 위치 pos에 저장된 키를 반환합니다 .

설명

pos가 유효한 위치 값이 아니면 결과를 예측할 수 없습니다. 디버그 빌드에서 pos가 NULL과 같으면 어설션 오류가 발생합니다.

CRBTree::GetNext

개체에 저장된 CRBTree 요소에 대한 포인터를 가져오고 위치를 다음 요소로 이동하려면 이 메서드를 호출합니다.

const CPair* GetNext(POSITION& pos) const throw();
CPair* GetNext(POSITION& pos) throw();

매개 변수

pos
CRBTree::GetHeadPosition 또는 CRBTree::FindFirstKeyAfter와 같은 메서드에 대한 이전 호출에서 반환된 위치 카운터입니다.

Return Value

트리의 다음 CPair 값에 대한 포인터를 반환합니다.

설명

pos 위치 카운터는 각 호출 후에 업데이트됩니다. 검색된 요소가 트리 의 마지막 요소인 경우 pos 는 NULL로 설정됩니다.

CRBTree::GetNextAssoc

이 메서드를 호출하여 지도에 저장된 요소의 키와 값을 가져와서 위치를 다음 요소로 진행합니다.

void GetNextAssoc(
    POSITION& pos,
    KOUTARGTYPE key,
    VOUTARGTYPE value) const;

매개 변수

pos
CRBTree::GetHeadPosition 또는 CRBTree::FindFirstKeyAfter와 같은 메서드에 대한 이전 호출에서 반환된 위치 카운터입니다.

key
트리 키의 형식을 지정하는 템플릿 매개 변수입니다.

value
트리 값의 형식을 지정하는 템플릿 매개 변수입니다.

설명

pos 위치 카운터는 각 호출 후에 업데이트됩니다. 검색된 요소가 트리 의 마지막 요소인 경우 pos 는 NULL로 설정됩니다.

CRBTree::GetNextKey

트리에 저장된 요소의 키를 가져와 위치를 다음 요소로 이동하려면 이 메서드를 호출합니다.

const K& GetNextKey(POSITION& pos) const throw();

매개 변수

pos
CRBTree::GetHeadPosition 또는 CRBTree::FindFirstKeyAfter와 같은 메서드에 대한 이전 호출에서 반환된 위치 카운터입니다.

Return Value

트리의 다음 키에 대한 참조를 반환합니다.

설명

현재 위치 카운터( pos)를 업데이트합니다. 트리에 항목이 더 이상 없으면 위치 카운터가 NULL로 설정됩니다.

CRBTree::GetNextValue

트리에 저장된 요소의 값을 가져와서 위치를 다음 요소로 이동하려면 이 메서드를 호출합니다.

const V& GetNextValue(POSITION& pos) const throw();
V& GetNextValue(POSITION& pos) throw();

매개 변수

pos
CRBTree::GetHeadPosition 또는 CRBTree::FindFirstKeyAfter와 같은 메서드에 대한 이전 호출에서 반환된 위치 카운터입니다.

Return Value

트리의 다음 값에 대한 참조를 반환합니다.

설명

현재 위치 카운터( pos)를 업데이트합니다. 트리에 항목이 더 이상 없으면 위치 카운터가 NULL로 설정됩니다.

CRBTree::GetPrev

이 메서드를 호출하여 개체에 저장된 요소에 대한 포인터를 CRBTree 가져온 다음 위치를 이전 요소로 업데이트합니다.

const CPair* GetPrev(POSITION& pos) const throw();
CPair* GetPrev(POSITION& pos) throw();

매개 변수

pos
CRBTree::GetHeadPosition 또는 CRBTree::FindFirstKeyAfter와 같은 메서드에 대한 이전 호출에서 반환된 위치 카운터입니다.

Return Value

트리에 저장된 이전 CPair 값에 대한 포인터를 반환합니다.

설명

현재 위치 카운터( pos)를 업데이트합니다. 트리에 항목이 더 이상 없으면 위치 카운터가 NULL로 설정됩니다.

CRBTree::GetTailPosition

이 메서드를 호출하여 트리의 꼬리에 있는 요소의 위치 값을 가져옵니다.

POSITION GetTailPosition() const throw();

Return Value

트리의 꼬리에 있는 요소의 위치 값을 반환합니다.

설명

반환된 GetTailPosition 값은 CRBTree::GetKeyAt 또는 CRBTree::GetPrev와 같은 메서드와 함께 사용하여 트리를 트래버스하고 값을 검색할 수 있습니다.

CRBTree::GetValueAt

개체의 지정된 위치에 저장된 값을 검색하려면 이 메서드를 CRBTree 호출합니다.

const V& GetValueAt(POSITION pos) const throw();
V& GetValueAt(POSITION pos) throw();

매개 변수

pos
CRBTree::GetHeadPosition 또는 CRBTree::FindFirstKeyAfter와 같은 메서드에 대한 이전 호출에서 반환된 위치 카운터입니다.

Return Value

개체의 지정된 위치에 저장된 값에 대한 참조를 CRBTree 반환합니다.

CRBTree::IsEmpty

빈 트리 개체를 테스트하려면 이 메서드를 호출합니다.

bool IsEmpty() const throw();

Return Value

트리가 비어 있으면 TRUE를 반환하고, 그렇지 않으면 FALSE를 반환합니다.

CRBTree::KINARGTYPE

키가 입력 인수로 전달될 때 사용되는 형식입니다.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KOUTARGTYPE

키가 출력 인수로 반환되는 경우 사용되는 형식입니다.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

개체에서 모든 요소를 제거하려면 이 메서드를 호출합니다 CRBTree .

void RemoveAll() throw();

설명

요소를 저장하는 데 사용되는 메모리를 해제하여 개체를 지 CRBTree 웁니다.

CRBTree::RemoveAt

개체의 지정된 위치에 있는 요소를 제거하려면 이 메서드를 CRBTree 호출합니다.

void RemoveAt(POSITION pos) throw();

매개 변수

pos
CRBTree::GetHeadPosition 또는 CRBTree::FindFirstKeyAfter와 같은 메서드에 대한 이전 호출에서 반환된 위치 카운터입니다.

설명

지정된 위치에 저장된 키/값 쌍을 제거합니다. 요소를 저장하는 데 사용되는 메모리가 해제됩니다. pos에서 참조하는 POSITION은 유효하지 않으며 트리에 있는 다른 요소의 POSITION은 유효한 상태로 유지되지만 반드시 동일한 순서를 유지하지는 않습니다.

CRBTree::SetValueAt

개체의 지정된 위치에 저장된 값을 변경하려면 이 메서드를 CRBTree 호출합니다.

void SetValueAt(POSITION pos, VINARGTYPE value);

매개 변수

pos
CRBTree::GetHeadPosition 또는 CRBTree::FindFirstKeyAfter와 같은 메서드에 대한 이전 호출에서 반환된 위치 카운터입니다.

value
개체에 추가할 값입니다 CRBTree .

설명

개체의 지정된 위치에 CRBTree 저장된 값 요소를 변경합니다.

CRBTree::VINARGTYPE

값이 입력 인수로 전달될 때 사용되는 형식입니다.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

값이 출력 인수로 전달될 때 사용되는 형식입니다.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

참고 항목

클래스 개요