Recursion and passing by reference

[adam2016]

Hi guys

I'm creating a vector that will represent a binary search tree, the root node will be the first element and the left child will be double the parent, the right child will be double+1 of the parents position.

any how I have run into a problem that somewhat confuses me, and seems quite basic.

template <class T>
class BSTVector{

public:

    vector<T> bst = vector<T>(200,NULL);

    BSTVector(){}

    void addNode(T ele,int& currentNum)
    {
        if(bst[currentNum] == NULL)
        {
            bst[currentNum] = ele;
            return;
        }
        if(ele < bst[currentNum])
        {
            addNode(ele,currentNum*2);
        }
        else
        {
            cout << ele << "added here" << endl; // for debug
            addNode(ele,(currentNum*2)+1);
        }
    }
};


int main()
{
    BSTVector<int> bs;
    int cn = 1;
    bs.addNode(8,cn);
    cn = 1;
    bs.addNode(4,cn);
    cn = 1;
    bs.addNode(5,cn);

I get the following compiler error - \C++\BinaryTreeAsAVector\main.cpp|43|error: invalid initialization of non-const reference of type 'int&' from an rvalue of type 'int'|

ok I declare and initialise the variable cn and pass it to the addNode function so why is the compiler complaining of an rvalue?

As mentioned I pass the cn variable by reference so if this doesn't work how do I pass a variable that I can double or (double)+1 each time the a new stack frame of addNode is called recursively?

thanks

[adam2016]

if(ele < bst[currentNum])
        {
            currentNum *= 2;
            addNode(ele,currentNum);
        }
        else
        {
            currentNum = (currentNum*2)+1;
            addNode(ele,currentNum);
        }

stupid me, of course it's an r value in the function itself I pass currentNum*2 which is an rvalue

I should have updated currentNum before passing currentNum to it

anyway is there an easier way to update a variable without having to reset it back to 1 each time I call add node?

BSTVector<int> bs;
    int cn = 1;
    bs.addNode(8,cn);
    cn = 1;
    bs.addNode(4,cn);
    cn = 1;
    bs.addNode(5,cn);

thanks!

[ne555]

don't pass it by reference

void addNode(T ele, int currentNum){
   //...
   addNode(ele, 2*currentNum+1);
}

    int cn = 1;
    bs.addNode(8,cn);

that's the client code, ¿why you start at 1 instead of 0? (2n+1, 2n+2)
¿why the client should care about passing `cn'?
bs.addNode(8);

[dutch]

In C++11 or greater, you should use nullptr (not NULL). But your idea doesn't work. NULL or nullptr assigned to an int (as you are doing in your example) just assigns 0. (In fact, pre-C++11 it was normal to just use 0 instead of NULL.)

In order to indicate an unused position you could, perhaps, have a parallel vector of bools.

As for the reference problem, as ne555 asked, why are you using a reference in the first place?

It is, of course, totally impractical to represent a BST as a vector or array. Usually only a "complete" tree is represented in that way, such as that used in heapsort.

#include <iostream>
#include <vector>
using namespace std;

template <typename T, int Size=200>
class BSTVector{
    vector<T> bst = vector<T>(Size);
    vector<bool> used = vector<bool>(Size);

    static void print(const BSTVector& bst, int pos = 0) {
        if (!bst.used[pos]) return;
        print(bst, pos * 2 + 1);
        cout << bst.bst[pos] << ' ';
        print(bst, pos * 2 + 2);
    }

public:
    BSTVector(){}

    void addNode(T ele, int pos = 0) {
        if (pos >= Size)
            cerr << "overflow\n";
        else if (!used[pos]) {
            bst[pos] = ele;
            used[pos] = true;
        }
        else
            addNode(ele, pos * 2 + 1 + (ele >= bst[pos]));
    }

    void print() const {
        print(*this);
        cout << '\n';
    }
};

int main() {
    BSTVector<int> bs;
    for (int n: {8, 4, 5, 2, 9, 6, 0, 3, 7, 1})
        bs.addNode(n);
    bs.print();
}

[adam2016]

Thanks guys and Dutch that's a very a good idea

and yeah that is a problem if you wanted to insert 0 so yeah a parallel vector of bools would be a good idea

as far as why I used a reference, again a pretty poor choice , after coding all morning I can't even honestly tell you why I choose it, it was pretty much down to a slew of bugs

It is, of course, totally impractical to represent a BST as a vector or array. Usually only a "complete" tree is represented in that way, such as that used in heapsort.

I got the idea from a data structure book, so why would using a vector or array to represent a BST be impractical as opposed to a complete tree like a heapsort?

thanks

[ne555]

I don't remember the balancing algorithms so can't say about the insert and delete element operations
but once you have the tree constructed, you can balance it to make it full.
then using an array will be smaller (as you don't need root or children pointers) and you wouldn't be jumping wildly in memory, but are contained to a block (less cache misses)

[dutch]

I got the idea from a data structure book

In what context did they suggest you use it? Was it, perchance, a complete binary tree? Or possibly a way to "simulate" pointers in a language that doesn't have them?

The problem is that there will be a lot of empty locations, so it is not very efficient in terms of space.

If you store this tree, which is complete except for the right-hand side of the last row, then the vector will not have any holes in it:

                 1
         2               3
     4       5       6       7
   8   9   10 11   12 13

vector: 1 2 3 4 5 6 7 8 9 10 11 12 13

If you store this tree, then the vector has 9 used positions and 12 holes:

                   1
          2            3
     4          5        6
            7              8
             9

vector: 1 2 3 4 5 - 6 - - 7 - - - - 8 - - - - - 9

However, as ne555 mentioned, if the tree is balanced then it will be more-nearly complete (but not totally), and storing the elements in an array keeps them closer together in memory (unless what is stored in the tree is pointers). So there are potential uses for it, since most real bst's will be balanced.

[jonnin]

why do you say a tree from a vector is impractical?
node would need a 'used' bool, perhaps (mostly to rebuild if loaded from a file), but if you have that, you use the index in the array as your pointers, push back new nodes, keep a list of deleted indices and reclaim them instead of push back for new data, etc? It works fine. If you want the binary search, use the tree/pointers. If you want to save/load file use the vector. Its not for every tree solution but it doesn't have a lot of drawbacks that I see? I don't like the classic approach of storing it with the gaps, but that isn't needed at all. You also want null to be eg -1 as 0 is valid index. Its really just 'one more way' to slice up an array for whatever purpose, but its a royal pain in an array (and much, much kinder in a vector).

[adam2016]

come to think about it, yes I think they did mention that it has to be a complete binary tree

If you store this tree, which is complete except for the right-hand side of the last row, then the vector will not have any holes in it:

makes sense, a complete binary tree would be hard to create right? I mean what would be the chances of your tree being complete if you where to pick a list of random numbers ie 8, 4 , 2 , 10 , 9 , 3

@Jonnin also that is true that is a good idea you could let -1 be your null, but for types other than int you may need to create a wrapper class that contains an int in order to store types that are not int

[dutch]

what would be the chances of your tree being complete

An unbalanced BST would have no real chance of being complete. A balanced BST will be better, but not perfect. The tree used in heapsort is perfectly complete by design (except possibly for the right-hand side of the last row).

I think jonnin is talking about a totally different way of using the array, a way that would be more space-efficient (note that he talks about reusing "deleted" indices). But I'm not entirely sure.

[jonnin]

yes, i was talking about keeping it compacted. This isn't the store in an array algorithm where specific BST locations have a known index, but really just using a vector and its indices in place of new/delete/pointers and most of the rest of the tree stuff would be the same old code. Again the primary advantage is you can save and load the vector's array to a file and do other serialized/iterative stuff (eg modify each node's data, just iterate the vector) and the tree remains intact. Its conceptually 'taking a tree view of a vector'. I dunno what purpose it would serve, since a binary search on a vector is the same as the tree search, so about the only reason I could see it would be if a traversal is critical to your needs? It mostly feels like playing

[dutch]

So the vector would map vector indices to actual addresses and the tree nodes would use vector indices instead of addresses.

#include <iostream>
#include <fstream>
#include <vector>

struct Node {
    int data;
    int left, right;
    Node(int d, int l=-1, int r=-1) : data{d}, left{l}, right{r} {}
};

int insert(int node, std::vector<Node*>& v, int data) {
    if (node == -1) {
        v.push_back(new Node(data));
        return v.size() - 1;
    }
    if (data < v[node]->data)
        v[node]->left = insert(v[node]->left, v, data);
    else
        v[node]->right = insert(v[node]->right, v, data);
    return node;
}

void print(int node, const std::vector<Node*>& v) {
    if (node == -1) return;
    print(v[node]->left, v);
    std::cout << v[node]->data << ' ';
    print(v[node]->right, v);
}

void save(const std::string& filename, int root, const std::vector<Node*>& v) {
    std::ofstream fout(filename);
    fout << root << '\n';
    for (int i = 0; i < int(v.size()); ++i)
        fout << v[i]->data  << ' ' << v[i]->left  << ' ' << v[i]->right << '\n';
}

int restore(const std::string& filename, std::vector<Node*>& v) {
    std::ifstream fin(filename);
    int root, node, left, right;
    fin >> root;
    for (int i = 0; fin >> node >> left >> right; ++i)
        v.push_back(new Node(node, left, right));
    return root;
}

void clear(int& root, std::vector<Node*>& v) {
    root = -1;
    for (int i = 0; i < int(v.size()); ++i)
        delete v[i];
    v.clear();
}

int main() {
    std::vector<Node*> v;
    int root = -1;

    for (int n: {6, 3, 4, 9, 0, 2, 8, 5, 1, 7})
        root = insert(root, v, n);

    print(root, v);
    std::cout << '\n';

// requires file system access
/*
    save("save.txt", root, v);

    clear(root, v);

    root = restore("save.txt", v);

    print(root, v);
    std::cout << '\n';
*/
    clear(root, v);
}

Contents of save.txt:

0
6  1  3
3  4  2
4 -1  7
9  6 -1
0 -1  5
2  8 -1
8  9 -1
5 -1 -1
1 -1 -1
7 -1 -1