Traversing 2-3 trees.2-3 a tree as a data structure for storing sets

Question

Traversing 2-3 trees.2-3 a tree as a data structure for storing sets

There is such an implementation of 2-3 trees :

class Tree {
private:
    Node * root;
    char name;
}

class Node {
    int value;
    std::vector<int> keys;
    std::vector<Node *> sons;
    Node * parent;

    Node(int val = 0) : value(val) , parent(nullptr) {}
    friend class Tree;
};

With a pointer to the parent. It is intended for storing a set . It is necessary to implement two-place operations on sets (union, intersection , difference). There is an idea to go around the tree (in depth) and alternately take from the leaves the values that are in the set . As soon as the value is taken, the leaf is removed and the value in the leaf is added to the first tree (this is for joining, for other operations it is the same) . Only now there is a problem with traversing the tree, please help with the description of the algorithm .

1

c++алгоритм структуры-данных дерево поиск

Author: hedgehogues, 2017-03-20

Source

1 answers

score 1 · Answer 1

Yes, you're right, a deep crawl is fine. As an example, I will write a search of vertices in depth (sometimes this tree traversal is called LR-traversal, i.e. left-right-traversal):

class Tree {
private:
    Node * root;
    char name;
}

class Node {
    int value;
    std::vector<int> keys;
    std::vector<Node *> sons;
    Node * parent;

    Node(int val = 0) : value(val) , parent(nullptr) {}
    friend class Tree;

    void DFS(Node* current);
};

void LRSearch(Node* current) {
    //do smth if leaf
    for (i = 0; i < this.sons.lenght(); ++i) { // Перебор прямых потомков
         //do smth
         LRSearch(this.sons[i]);
    }
}

The idea of this traversal is that we iterate through all the direct descendants of the vertex and go to each of them. For each child, we run a search of all its direct descendants. And so on. If we end up in a leaf, nothing will happen, since the list of direct descendants is empty, which means that we not going into the loop.

In some tasks, an auxiliary array of flags is used to count the visited vertices. But there is no need to mark the visited vertices here, since this is a tree and we know which vertices we have visited and which we have not.

Consider a graph with a cycle. Then, moving from vertex to vertex (initially we are at vertex 1), we will get to the 2nd vertex, to the 3rd, to the 4th. At each step (at each position, we will mark with a red circle that we are at a specific vertex). AT 4 let's check that the 1st vertex has already been visited and there is no need to go there. In this case, we return to the previous step of the recursion.

For a tree, as I said, the situation is changing. Getting to a certain vertex, it can not happen that there is a vertex among the subsequent ones (if we continue to spin the recursion), in which we were. In this case, after reaching the vertex 4. We will return back by recursion (steps 4 -- 6). When we reach the 1st vertex, we go to the 5th and we'll finish our rounds.

For the future. You can find most of the answers here, here. Solve problems and submit for review here and here.