C++ 이진 검색 트리 - 복합 형식

Question

두 가지 유형의 개체에 대해 BST를 구현해야합니다. 계정 및 고객. 두 유형 모두 pk (둘 다 "id"라고 함)가 있습니다. Google에서 솔루션을 검색 할 때 BST 솔루션을 많이 찾을 수 있지만 간단한 유형 (예 : BST 솔루션은 {1,2,3,4,99, ... 999}와 같은 정수를 정렬 할 수 있습니다. 그러나 BST 솔루션이 자신의 pk를 기반으로 복잡한 유형/클래스를 정렬하기를 원합니다. 가능한가요? 감사.

Answer 1

정수의 이진 검색 트리를 작성하는 데 사용되는 논리는 즉시 다른 데이터 형식으로 일반화 할 수 있어야합니다. 각 노드에 키로 정수를 저장하는 대신 고객 및 계정 이름을 각 필드에 저장하고 조회를 수행 할 때 기본 키만 비교하십시오. 정말 간단해야합니다.

즉 숙제를위한 것이 아니라면 바이너리 검색 트리와 완전히 동일한 복잡성 보장이 있지만 이미 작성되었으며 널리 사용 가능하며 많은 테스트를 거친 std :: map을 사용해야합니다.

희망이 도움이됩니다.

Answer 2

노드 정의를 수정하고 저장하려는 객체에 대한 참조를 추가하고 색인을 설정하는 경우 (사례에서는 pk) 메모를 정렬 할 수 있습니다. 다른 종류의 사용에 대한 템플릿을 해결할 수 있습니다

class Account 
{ 
    public: 
     Account(int k) : pk(k) {}; 
     int pk; 
    /* ... */ 
}; 


template<typename T> 
class TreeNode 
{ 
    public: 
     TreeNode(T& the_object) : id(the_object.pk), object(the_object) {}; 

     int id; 
     T& object; 
}; 


int main() { 
    Account a(9); 
    TreeNode<Account> tn(a); 
    std::cout << tn.id; 
} 

당신이 나무에 다른 개체 유형을 혼합 할 경우, 다른 방법은 PK 속성에 대한 접근을 포함하는 클래스를 정의하고 계정 및 고객이 내재하는 것입니다 예를 들어 그것은 : 다른 답변으로

class Indexable 
{ 
    public: 
     Indexable(int the_pk) : pk(the_pk) {}; 
     int pk; 
}; 

class Account : public Indexable 
{ 
    public: 
     Account(int k) : Indexable(k) {}; 
    /* ... */ 
}; 

class TreeNode 
{ 
    public: 
     TreeNode(Indexable& the_object) : id(the_object.pk), object(the_object) {}; 

     int id; 
     Indexable& object; 
}; 


int main() { 
    Account a(9); 
    TreeNode tn(a); 
    std::cout << tn.id; 
} 

생산에서 당신은 표준 : :지도 또는 트리 구조의 또 다른 알려진 라이브러리를 사용하는 것이 좋습니다 지적했다.