Trouble with non-recursive AVL tree insert

I have the following code for the recursive version:
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
//inserts item x (in this case a string), with a line number occurrence
//keeps track of number of rotations done
void insert( const Comparable & x, const int & lineNum, int & singleCount, int & doubleCount, AvlNode * & t )
    {
        if( t == NULL )
		{
                        t = new AvlNode( x, NULL, NULL );
			t->lines.push_back(lineNum);
		}
        else if( x < t->element )
        {
            insert( x, lineNum, singleCount, doubleCount, t->left );
            if( height( t->left ) - height( t->right ) == 2 )
                if( x < t->left->element )
				{
                                        rotateWithLeftChild( t );
					singleCount++;
				}
                else
				{
                                        doubleWithLeftChild( t );
					doubleCount++;
				}
        }
        else if( t->element < x )
        {
            insert( x, lineNum, singleCount, doubleCount, t->right );
            if( height( t->right ) - height( t->left ) == 2 )
                if( t->right->element < x )
				{
                                        rotateWithRightChild( t );
					singleCount++;
				}
                else
				{
                                        doubleWithRightChild( t );
					doubleCount++;
				}
        }
        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;
    }


I'm trying to make an iterative version. I have written a bit, but am having trouble figuring out when to do the rotations and when to change the value of t.

What I have:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    void iterInsert( const Comparable & x, const int & lineNum, int & singleCount, int & doubleCount, AvlNode * & t )
    {
		while((t != NULL)||(x != t->element))
		{
		 //don't know what to do here
		}
		if(t == NULL) //found insertion point
		{
			t = new AvlNode(x, NULL, NULL); //create node
			t->lines.push_back(lineNum); //add the line number occurrence 
		}
		else //duplicate, add line number occurrence
		{
			if(t->flag == false)
				t->flag = true; //change flag to true if previously "deleted"
			t->lines.push_back(lineNum);
		}
		t->height = max(height(t->left), height(t->right))+1; //set height
			
	
    }

Topic archived. No new replies allowed.