트리 데이터 구조 만들기 - 다른 접근법

Question

전달되는 동안 트리 데이터 구조에 대해 많은 질문을했지만 C++에서 올바른 방식으로 처리하지 않은 것처럼 보입니다.

데이터 구조를 작성하는 방식으로 "끝"또는 "시작"반복기를 갖는 방법에 대해 단일 방식을 생각할 수 없습니다. 이와 같이 모든 기능을 멤버 메서드로 포함하는 방식으로 넘어갔습니다. 대신 이터레이터 & 알고리즘의 표준 접근 방식을 사용합니다.

내 트리 구조의 목표는 다음과 같습니다. 가능한 한 빨리 1 트리에서 다른 트리로 분기를 이동하는 것입니다. 2) 각 가지는 나무가되어야합니다. 또한 트리에서 작업하는 작업은 지점에서 실행될 수 있어야합니다.

내가 한 것은 단순히 벡터가 포함 된 클래스를 만드는 것입니다. - 벡터 내부에는이 클래스의 다른 객체가 있습니다. 예 (난 단지 내가 지금 직면하고있는 가장 큰 문제로, 여기에 최소한의 예를 게시하고있어 클래스가 처리 할 단순히 너무 큰 것입니다) :이 함께 볼 수 있듯이

template <typename ValTy> 
class Tree { 
private: 
    std::vector<std::unique_ptr<Tree> > subtrees; 
    ValTy value; 
}; 

난 그냥 무언가를 취할 수 있습니다 subtrees - 트리로 사용하거나 주위에 복사하십시오. 그러나 최상위 트리에는 몇 개의 하위 트리 (또는 몇 개의 레벨)가 있는지에 대한 정보가 없으므로 "끝 반복자"를 지정하는 것은 불가능합니다. 그리고 std :: find() 같은 알고리즘은 전체 트리 (그리고 모든 서브 트리)를 반복하지 않습니다.

쉬운 "분기"구조를 유지하면서 가능한 이러한 알고리즘을 사용할 수 있습니까?

Answer 1

하위 트리 벡터의 반복자 쌍 스택을 유지함으로써 이러한 트리를 반복 할 수 있습니다. 이러한 벡터의 증가는 맨 위에있는 하위 트리 반복자의 증가량을 의미하며, 맨 아래 이터레이터가 끝나면 정리됩니다.

end()이 벡터의 반복자는 단순히 빈 스택입니다.

Answer 2

위와 같이 알 수 있듯이 하위 트리 ( )를 가져 와서 트리로 사용하거나 복사 할 수 있습니다. 그러나 상위 레벨 트리에는 몇 개의 하위 트리 (또는 얼마나 많은 레벨)가 있는지에 대한 정보가 없으므로 "끝 반복자"를 말할 수 없습니까? 그리고 처럼 std :: find()와 같은 알고리즘은 전체 트리 (및 모든 하위 트리)을 반복하지 않습니다.

여기의 문제는 더 많은 개념적 문제입니다.

재귀를 사용하여 트리 구조 내에서 항상 CRUD 기능을 해결합니다. 재귀에는 하위 트리의 수에 대한 지식이 필요하지 않으며 이는 O(log n) 삽입, 찾기 및 삭제를 가능하게하는 것 중 하나입니다.

삽입 예를 : 당신은 그냥 NULL 때까지 왼쪽 아이를가는 나무에 얼마나 많은 수준을 알 필요가있는 경우

void insertNode(Node* &treeNode, Node *newNode) { 
    if (treeNode) treeNode = newNode; 
    else if (newNode->key < treeNode->key) insertNode(treeNode->left, newNode); 
    else insertNode(treeNode->right, newNode); 
} 

. 이 지식을 사용하여 나무에있는 아이들의 수를 세는 알고리즘을 O(log n) 쉽게 해결할 수 있습니다.

---

트리는 재귀 액세스 용으로 설계되었습니다. 비회원 액세스를 원한다면, 아마도 나무가 당신이 찾고있는 것이 아니겠습니까? -이 구조는 어떤 액세스 빈도에서 어떤 데이터를 보유 할 것입니까?