Странная ошибка в реализации моего splay tree

Question

Я пытаюсь написать структуру шаблона C++ для дерева splay, но когда я пытаюсь проверить код, я получаю очень странные результаты.

Это мой код для шаблона:

template <class T> 
struct splaytree { 
    struct node { 
     splaytree<T> *tree; 
     node *p, *c[2]; 
     T v; 
     int w; 
     node(T t, splaytree<T> *st) { 
      v = t; 
      p = 0; 
      c[0] = 0; 
      c[1] = 0; 
      w = 1; 
      tree = st; 
     } 
     int side() { 
      return (p->c[1] == this) ? 1:0; 
     } 
     void r() { 
      node *x = this; 
      int b = x->side(); 
      node *p = x->p; 
      x->w = p->w; 
      p->w = x->c[1^b]->w + 1 + p->c[1^b]->w; 
      x->p = p->p; 
      p->p = x; 
      p->c[0^b] = x->c[1^b]; 
      x->c[1^b] = p; 
     } 
     void splay() { 
      node *x = this; 
      while (x->p) { 
       node *p = x->p; 
       if (p == tree->root) x->r(); 
       else if (((x->side())^(p->side()))) { 
        x->r(); 
        x->r(); 
       } 
       else { 
        p->r(); 
        x->r(); 
       } 
      } 
      tree->root = this; 
     } 
     int index() { 
      this->splay(); 
      return this->c[0]->w; 
     } 
    }; 
    node *root; 
    splaytree() { 
     root = 0; 
    } 
    void add(T k) { 
     node x0(k,this); 
     node *x = &x0; 
     if (root == 0) { 
      root = x; 
      return; 
     } 
     node *i = root; 
     while (i != x) { 
      int b = (k < i->v) ? 0:1; 
      if (i->c[b] == 0) { 
       i->c[b] = x; 
       i->w++; 
       x->p = i; 
      } 
      i = i->c[b]; 
     } 
     x->splay(); 
    } 
}; 

Я использую это, чтобы проверить:

int main() { 
    splaytree<int> st; 
    st.add(2); 
    cout << st.root->v << endl; 
    cout << st.root->v << endl; 
    st.add(3); 
    cout << st.root->c[0] << endl; 
} 

Я вставил элемент 2, а затем печатается значение корневого узла дважды. Как-то два отпечатка дали мне два разных значения (2 и 10 в Ideone на http://ideone.com/RxZMyA). Когда я запускал программу на своем компьютере, вместо этого мне дали 2 и 1875691072. В обоих случаях при вставке 3 после 2 левый дочерний элемент корневого узла был нулевым указателем, если он должен быть узловым объектом, содержащим 2.

Может кто-нибудь скажет мне, почему я получаю два разных значения при печати то же самое дважды, и что я могу сделать, чтобы моя функция splaytree.add() работала по назначению? Благодаря!

Answer 1

После

node x0(k,this); 
    node *x = &x0; 
    if (root == 0) { 
     root = x; 
     return; 
    } 

root является адресом локальной переменной. К тому моменту, когда вы печатаете root->v, x0 ушел из сферы действия. Все ставки относительно того, что действительно указывает root, отключены.