File Based AVL Tree

For class I have to write a program that reads (plaintext) numbers from a file, and inserts them into an AVL tree stored in another (binary) file. I cannot have more than about 10 nodes in memory at one time. I've written the code and it works fine, but I feel it's running slower than it could. I can currently process a file with 100,000 numbers in 34 seconds. How can I make my code faster?

Here's a link to the full assignment details.

```
#include
#include
#include

const int C_NULL = -1;

struct node
{
node ( ) : value ( C_NULL ), left ( C_NULL ), right ( C_NULL ),
height ( C_NULL ), parent ( C_NULL ), location ( C_NULL ) { };

node ( int v, int l, int r, int h, int p, int loc )
: value ( v ), left ( l ), right ( r ),
height ( h ), parent ( p ), location ( loc ) { };

node ( std::fstream & file, const int loc ) { read ( file, loc ); };

int value, left, right, height, parent, location;

void read ( std::fstream & file, const int loc );

void write ( std::fstream & file );

void print ( )
{
std::cout.width ( 10 );
std::cout 0 )
{
int value, nodes = root.height + 1;

while ( input >> value )
{
if ( insertValue ( output, value, nodes++, root, child ) )
UpdateHeightAndCheckBalance ( output, root, child, 2 );

fixRootLocation ( output, root );
}
}

int smallest, biggest;

getSelectValues ( output, smallest, biggest );

std::cout > root.value;

if ( input ) // if there is at least one number in the file
{
node child ( C_NULL, C_NULL, C_NULL, 0, 0, 1 );

input >> child.value;

if ( input ) // if there is a second number
{
root.height = 1;

if ( root.value 1 ) // left heavy
return rebalanceLeft ( file, left, parent, right );

else if ( balance newleftright.height ) left.height = leftleft.height + 1;

else le

This code appears to have a lot of excessive whitespace. I do understand that putting a space between parentheses is a type of style, but you also add blank lines in many unnecessary places.

The biggest example are your function prototypes:

node seedTree ( std::ifstream & input, std::fstream & output );

bool insertValue ( std::fstream & file, const int value, const int numNodes, node & root, node & newNode );

void UpdateHeightAndCheckBalance ( std::fstream & file, node & parent, node & child, const int height );

void rebalanceLeft ( std::fstream & file, node & left, node & parent, const node & right );

void rebalanceRight ( std::fstream & file, const node & left, node & parent, node & right );

void fixRootLocation ( std::fstream & file, node & root );

void getSelectValues ( std::fstream & file, int & smallest, int & biggest );

void printNodes ( std::fstream & file );

You really don't need a blank line after each one. It just adds to the length of the code, but not in a good way. If some pieces of code are similar in functionality, leave them together (such as here). Otherwise, add a blank line between them. Adding whitespace to "isolate" code doesn't always improve readability and can even make the code more frustrating to read.

I'm also not sure why you're doing this in a single line:

while ( file.tellg ( ) < fSize ) node ( file, int ( file.tellg ( ) ) / C_NODE_SIZE ).print ( );

You've added many blank lines everywhere else, but here, you've done just the opposite. It would take more unnecessary time to understand this line.

Here's how it should look:

while (file.tellg() < fSize)
{
    node(file, int(file.tellg()) / C_NODE_SIZE).print();
}

Note that I've added curly braces here, which is good practice.

Speaking of curly braces, there are areas where you don't need them, such as here:

{ // set 'left' height and left.right.parent
    node newleftright ( file, left.right );

    newleftright.parent = left.location;

    newleftright.write ( file );

    if ( leftleft.height > newleftright.height ) left.height = leftleft.height + 1;

    else  left.height = newleftright.height + 1;
}

I assume you're using this as a way of grouping or isolating a block of code. This may not even help you at all and could be an indication that some kind of refactoring is needed. Otherwise, it would be okay to just remove these curly braces altogether. Try not to clutter you code with such things that may only hurt readability and won't make it any functionally better.

StackExchange Code Review Q#82885, answer score: 7