Help implementing either threading or a parent pointer in an AVL tree

netsuki (15)
I need to write iterators for my AVL tree, but I first need either threading or a parent pointer to get it working. I can't seem any examples of how to implement these.

The nodes are as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
struct AvlNode
    {
        Comparable element; //stored element of template type Comparable
		list<int> lines; //line numbers on which element occurs
		bool flag; //flag for lazy deletion
        AvlNode   *left;
        AvlNode   *right;
        int       height;

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


If I were to implement a AvlNode *parent pointer into this struct, I am confused as how to edit the rest of the code to work.

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
   / * 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 of occurrence
     */
    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;
    }

 /**
     * Rotate binary tree node with left child.
     * For AVL trees, this is a single rotation for case 1.
     * Update heights, then set new root.
     */
    void rotateWithLeftChild( AvlNode * & k2 )
    {
        AvlNode *k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
        k1->height = max( height( k1->left ), k2->height ) + 1;
        k2 = k1;
    }

    /**
     * Rotate binary tree node with right child.
     * For AVL trees, this is a single rotation for case 4.
     * Update heights, then set new root.
     */
    void rotateWithRightChild( AvlNode * & k1 )
    {
        AvlNode *k2 = k1->right;
        k1->right = k2->left;
        k2->left = k1;
        k1->height = max( height( k1->left ), height( k1->right ) ) + 1;
        k2->height = max( height( k2->right ), k1->height ) + 1;
        k1 = k2;
    }

    /**
     * Double rotate binary tree node: first left child.
     * with its right child; then node k3 with new left child.
     * For AVL trees, this is a double rotation for case 2.
     * Update heights, then set new root.
     */
    void doubleWithLeftChild( AvlNode * & k3 )
    {
        rotateWithRightChild( k3->left );
        rotateWithLeftChild( k3 );
    }

    /**
     * Double rotate binary tree node: first right child.
     * with its left child; then node k1 with new right child.
     * For AVL trees, this is a double rotation for case 3.
     * Update heights, then set new root.
     */
    void doubleWithRightChild( AvlNode * & k1 )
    {
        rotateWithLeftChild( k1->right );
        rotateWithRightChild( k1 );
    }


Any help at all, or even links to examples would be much appreciated! I am having a really hard time with this.
Topic archived. No new replies allowed.