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;
}
|