파일에서 BST를 다시 작성하는 방법

Question

내 C++ 프로그램은 사용자 입력에서 불균형 BST를 생성하고이를 디스크에 저장합니다. 이 작업은 먼저 선주문 순회 (pre-order traversal)를 수행하고 각 노드에 고유 번호를 할당하여 각 노드를 인덱싱합니다. 그런 다음 BST를 파일로 출력합니다. 선주문 탐색을 수행 한 다음 데이터 값, 왼쪽 하위 색인 번호 및 오른쪽 하위 색인 번호를 인쇄하는 각 노드에 대해 인쇄 작업을 수행합니다.

그래서 BST를 디스크에 저장하면 메모리의 BST가 삭제됩니다. 파일을 읽고 BST를 다시 작성하여 이전과 똑같이 되길 원합니다.

Answer 1

최상의 바인딩을 사용하지 않는다고 가정하면이 간단한 알고리즘을 사용할 수 있습니다.

nodes_list = [] 
For each line i: 
    Search for node i in nodes_list 
    if(found): 
     node_i = found_node 
     node_i.set_value(line_value) 
    else: 
     node_i = new node(i) 
     node_i.set_value(line_value) 
     nodes_list.add(node_i) 
    Search for line_left_node in nodes_list 
    if(found): 
     node_i.set_left_node(found_node) 
    else: 
     left_node = new node(line_left_node) 
     node_i.set_left_node(left_node) 
     nodes_list.add(left_node) 
    Search for line_right_node in nodes_list 
    if(found): 
     node_i.set_right_node(found_node) 
    else: 
     right_node = new node(line_right_node) 
     node_i.set_right_node(right_node) 
     nodes_list.add(right_node) 

Answer 2

왼쪽 및 오른쪽 하위 색인 (해시 테이블)과 함께 모든 노드를 메모리로 읽습니다. 그런 다음 루트 (파일의 첫 번째 노드)에서 시작하여 해시 테이블의 인덱스를 통해 왼쪽 및 오른쪽 하위를 찾습니다. DFS 또는 BFS 방식으로 자식 노드에 대해 동일한 프로세스를 반복합니다. 어느 쪽이든 작동해야합니다.

트리를 구성하기 전에 전체 데이터를 메모리에로드하지 않으려면이를 최적화 할 수 있습니다. DFS 방식으로 노드를 읽고 트리를 구성 할 수 있습니다. 그래서 왼쪽 아이를 추가하면 곧장 앞으로 나아갈 수 있습니다. 아이를 추가하는 동안 인덱스 번호를 확인해야합니다. 일치하지 않으면 DFS 순서에서 현재 노드보다 높은 노드에 해당 자식을 추가하십시오.

Answer 3

포스트는 더 간단합니다. 스택에 복원 된 노드를 밀어 넣을 수 있으며 부모 노드에 연결된 자식 노드는 항상 스택의 최상위 항목이됩니다.

각 노드가 저장되어있는 노드를 기록한 경우 스택을 팝 아웃 할 대상과 할당 할 아이를 알고있을 때만 한 패스 만 있으면됩니다.

Answer 4

나무의 크기 (N)를 알고 있다고 가정합시다. 어쩌면 파일의 첫 번째 줄 일 수도 있습니다. 그렇지 않은 경우 인덱스 벡터의 동적 크기를 조정하기 위해이 방법을 쉽게 적용 할 수 있습니다. 이 반 의사가 있습니다 : 이유 node = index[nodeID]이 아닌 NULL로 보장됩니다

// Only needed while parsing the file 
std::vector<Node*> index(N, NULL); 

// We can always create the root node. 
// This simplifies the while loop below. 
index[0] = createNode(0); 

while (!in.eof()) { 
    int nodeID = -1, leftID = -1, rightID = -1; 
    parseNode(in, &nodeID, &leftID, &rightID); 

    // Guaranteed to be non-NULL 
    Node* node = index[nodeID]; 

    // if leftID or rightID is -1, createNode() 
    // will simply return NULL. 
    index[leftID] = createNode(leftID); 
    index[rightID] = createNode(rightID); 

    node->setLeftChild(index[leftID]); 
    node->setRightChild(index[rightID]); 
} 

때문에 읽기 사전 주문 색인/쓰기 /이다. 우리는 처음에 루트 노드를 미리 만들었고 다른 모든 노드는 부모에 의해 왼쪽 또는 오른쪽 자식으로 만들어졌습니다.

편집 : 우리는 풀 마스터 인덱스가 필요 없다는 것을 깨달았습니다. 잠재적 우익 노드를 저장하여 스택으로 확장하면됩니다. 당신이 예약 주문 탐색과 같은 이진 검색 트리를 저장하는 경우 당신이 그들을 읽을

// Candidate right-child nodes to expand 
std::stack<Node*> rightNodes; 

// Pre-create the root node as "left child" 
Node* left = createNode(0); 

while (!in.eof()) { 
    // We already know the next node. It is the previous 
    // node's left child (or root), or the nearest 
    // parent's right child. 
    Node* node; 

    if (left != NULL) { 
     node = left; 
    } 
    else { 
     node = rightNodes.top(); 
     rightNodes.pop(); 
    } 

    parseLine(in, &nodeID, &leftID, &rightID); 
    assert(node->ID() == nodeID); 

    // if leftID or rightID is -1, createNode() 
    // will simply return NULL. 
    left = createNode(leftID); 
    Node* right = createNode(rightID); 

    node->setLeftChild(left); 
    node->setRigthChild(right); 

    if (right != NULL) { 
     rightNodes.push(right); 
    } 
} 

Answer 5

는, 당신은 한 번에 요소를 삽입하여 단순히 나무를 얻을 것 : 여기 알고리즘의 버전입니다 네가 시작한 나무와 같을거야. 물론 O (n log n) 시간이 필요합니다. 당신이 외부 노드 (널 (null))를 저장하고자하는 경우 다음 당신은 다음과 같은 일을 할 수있는 :

ReadBSTPreOrder(node ** target) { 

    node * n = readNode(); 
    *target = n; 

    if (n == NULL) return; 
    ReadBSTPreOrder(&node->left); 
    ReadBSTPreOrder(&node->right); 
} 

이 BST의도하지 않은 이진 트리에 대한 작업의 추가 장점이있다. Null을 저장하는 것은 표현으로 원숭이를 기꺼이 원한다면 단일 비트가 될 수 있지만 null에 대한 단일 바이트 태그와 레코드에 대한 다른 태그는해야합니다. 그러면 색인을 작성하지 않아도됩니다.