How do I initialize a parent pointer?

netsuki (15)
I am having trouble figuring out how to initialize the parent pointer I added to my AVL tree node implementation. My node is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
    struct AvlNode
    {
        Comparable element; //data element of template type Comparable
        list<int> lines; //line occurrences
	bool flag; //checks validity for lazy deletion
        AvlNode   *left;
        AvlNode   *right;
        AvlNode   *parent;
        int       height;

        AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt, 
							AvlNode *pt, int h = 0, bool b = true )
          : element( theElement ), left( lt ), right( rt ), parent( pt ), height( h ), flag( b ) { }
    };


My problem is that I can't seem to figure out how to initialize the *parent in the insert function as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
    /*
     * Internal method to insert into a subtree.
     * x is the item to insert.
     * t is the node that roots the subtree.
     * lineNum is the line number occurrence to be recorded
     */
    void insert( const Comparable & x, const int & lineNum, AvlNode * & t)
    {
        if( t == NULL )
	{
	        if(t->parent == NULL) //insertion at the root, new tree
		{
			t = new AvlNode(x, NULL, NULL, NULL);
		}
                t = new AvlNode( x, NULL, NULL, ?); //set value, parent, lt and rt to NULL
		t->lines.push_back(lineNum); //add line number occurrence
	}
        else if( x < t->element )
        {
            insert( x, lineNum, t->left);
            if( height( t->left ) - height( t->right ) == 2 )
                if( x < t->left->element )
		{
                    rotateWithLeftChild( t );
		}
                else
		{
                    doubleWithLeftChild( t );
		}
        }
        else if( t->element < x )
        {
            insert( x, lineNum, t->right);
            if( height( t->right ) - height( t->left ) == 2 )
                if( t->right->element < x )
		{
                    rotateWithRightChild( t );
		}
                else
		{
                    doubleWithRightChild( t );
		}
        }
        else
	{	
		if(t->flag == false)
		t->flag = true; //change flag to true if node was previously "deleted"
                t->lines.push_back(lineNum);  // Duplicate; add new line occurrence 
	}
        t->height = max( height( t->left ), height( t->right ) ) + 1; //recalculate height
    }


I've never used parent pointers before, so I'm a bit confused as to how to initialize the parent.
ne555 (10692)
1
2
3
 
       if( t == NULL )
	{
	        if(t->parent == NULL) //Only Chuck Norris can dereference NULL pointers


You could just pass the parent pointer to the insert() function
I think that I already told you this: 'encapsulate the behaviour in a tree class'


¿Are you ever going to construct the node with something else that NULL for its leafs?
Topic archived. No new replies allowed.