TMandzu's blog

saving binary trees with pointers
By TMandzu, 11 years ago, In English

Hello I have never used pointers to build a binary tree , I always used arrays . I want to build an interval (where elements can be added between queries , not segment ) tree with pointers and need your help . I can't understand why people write any functions or procedures in the structure of pointer. If you know , please link any tutorial which can help me to study the syntax of pointers .

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The simplicity of the interval trees you mention is exactly in avoiding the use of a data structure with pointers to children and parent. Though I've heard about a structure called Dynamic Interval Tree, which allows you to build an interval tree spanning a very large range and only create those nodes that are queried in the process; in this case pointers would be convenient (I haven't implemented such a structure myself).

What do you mean by "write any functions or procedures in the structure of pointer"?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, Dynamic interval tree is exactly what I want to write . I once wrote it with arrays in 1D , and now I want to write with pointers in 2D .

    for example : struct vertex { vertex * l, * r; int sum;

    vertex (int val)
    : l(NULL), r(NULL), sum(val)
{ }

vertex (vertex * l, vertex * r)
    : l(l), r(r), sum(0)
{
    if (l)  sum += l->sum;
    if (r)  sum += r->sum;
}

    };

    I cant understand after "struct vertex { vertex * l, * r; int sum; "

    its a code at the end of this page http://e-maxx.ru/algo/segment_tree and also don't know what " new " function does in that code.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Dynamic interval tree in 2D was on IOI 2013 .

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Well, then your problem is not with interval trees, but with C++ syntax and concepts itself :)

      Those two "vertex" methods within "vertex" structure are constructors — the methods that are executed when a new object of vertex class is created. Since you have two constructors for this class, you can either provide a value when you create a new object, or provide the two children of this node. For example, if you write vertex a(100);, the first method is invoked. If l(NULL), r(NULL), sum(val) confuses you, that's a shorthand for l = NULL, r = NULL, sum = val; (only works for the constructor).

      The new keyword (as well as malloc in plain C) lets you create an object dynamically. It is stored in "heap" memory, contrary to any local objects within functions, which are stored in "stack" memory. When you write new class_name, an object of the class class_name is created; the expression itself returns a pointer to that object. That's why you can assign the result of this expression to any variable of type class_name*.

      I guess you should refer to some C++ textbook for further reading.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I understood everything in this code , but I have question in the second code. what "this" means in void recalc() ?

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          When a method is executed, you might need a pointer to the object whose method is executed. This pointer is this. So you can actually ignore all 'this' instances but the first and Recalc() reads as:

          void Recalc(){
    if (!this)
        return;

    maxValue = value;
    if (l && l->maxValue > maxValue)
        maxValue = l->maxValue;
    if (r && r->maxValue > maxValue)
        maxValue = r->maxValue;
}

          As for !this, it seems the same as this != NULL, but I don't quite understand how one can call recalc for a nonexisting object at all.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            thank you very much :)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              Just in case, note that this can not be always ignored like that. If you have a local variable with the same name as a field of the class, the field is hidden and you can only access it through this -> field_name.

              → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        include

        include

        using namespace std;

        struct treap{

        int x, value, maxValue;

double y;

treap *l, *r;

treap(int x, int value): x(x), y(rand()), value(value), maxValue(value), l(NULL), r(NULL) {}

treap():l(NULL), r(NULL){}

void Recalc(){

    if (!this)
        return;

    this->maxValue = this->value;
    if (this->l && this->l->maxValue > this->maxValue)
        this->maxValue = this->l->maxValue;
    if (this->r && this->r->maxValue > this->maxValue)
        this->maxValue = this->r->maxValue;
}

        };

        void split(treap * t, int x, treap* &l, treap* &r){ if (!t){ l = NULL; r = NULL; return; }

        if (t->x > x){
    r = t;

    split(r->l, x, l, r->l);
} else {
    l = t;
    split(l->r, x, l->r, r);
}
r->Recalc();
l->Recalc();

        }

        void merge(treap* l, treap* r, treap* &t){

        if (!l || !r){
    t = !l ? r : l;
    return;
}

if (l->y > r->y){
    t = l;
    merge(l->r, r, l->r);
} else {
    t = r;
    merge(l, r->l, r->l);
}
t->Recalc();

        }

        int max(int x, int y, treap* t){

        treap *l = new treap(), *m = new treap(), *r = new treap();
split(t, x — 1, l, r);
split(r, y, m, r);
int result = m->maxValue;
merge(l, m, l);
merge(m, r, t);
return result;

        }

        void insert(int x, int value, treap* &t){

        if (!t){
    t = new treap(x, value);

    return;
}

treap *l = new treap(), *m = new treap(x, value), *r = new treap();
split(t, x, l, r);
merge(l, m, m);
merge(m, r, t);

        }

        int main() { srand((int)time(0)); treap* t = NULL; int n, m;

        cin >> n >> m;

for (int i = 0; i < n; i++){
    int x, v;
    cin >> x >> v;
    insert(x, v, t);
}

for (int i = 0; i < m; i++){
    int x, y;
    cin >> x >> y;
    cout << max(x, y, t) << endl;
}

return 0;

        }

        this is full code.

        → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    this is the second example from Cartesian tree

    struct treap{

    int x, value, maxValue;

double y;

treap *l, *r;

treap(int x, int value): x(x), y(rand()), value(value), maxValue(value), l(NULL), r(NULL) {}


treap():l(NULL), r(NULL){}

void Recalc(){
    if (!this)
        return;

    this->maxValue = this->value;
    if (this->l && this->l->maxValue > this->maxValue)
        this->maxValue = this->l->maxValue;
    if (this->r && this->r->maxValue > this->maxValue)
        this->maxValue = this->r->maxValue;
}

    };

    → Reply