Take the height-balanced tree code, and replace the key field by a field int leaves. That field should contain the number of leaves below the node, so n->leaves = 1 if n is a leaf, and n->leaves =n->left->leaves + n->right->leaves else. The leaves field must be updated after an insertion or deletion for all nodes on the path from the root to the changed leaf, and after a rotation for the changed nodes.

Then you

(1) replace the find function by

object t *find by number(tree node t *tree, int k); which returns the object stored in the k-th leaf from left (start counting with the leftmost leaf as 1);

(2) replace the insert function by void insert by number(tree node t *tree, int k, object t *new obj);

which inserts new obj in a new k-th leaf, moving all leaves above it one step to the

right (without renumbering), and

(3) replace the delete function by

object t * delete by number(tree node t *tree, int k); which deletes (and returns) the object stored in the k-th leaf, moving all leaves above it one step to the left (without renumbering).

The programming language is C or C++; test your code before submission using the gcc or g++ compiler.

Here's the code:

#include

#include

#define BLOCKSIZE 256

typedef int object_t;

typedef int key_t;

typedef struct tr_n_t { key_t key;

struct tr_n_t *left;

struct tr_n_t *right;

int height;

} tree_node_t;

tree_node_t *currentblock = NULL;

int size_left;

tree_node_t *free_list = NULL;

tree_node_t *get_node()

{ tree_node_t *tmp;

if( free_list != NULL )

{ tmp = free_list;

free_list = free_list -> left;

}

else

{ if( currentblock == NULL || size_left == 0)

{ currentblock =

(tree_node_t *) malloc( BLOCKSIZE * sizeof(tree_node_t) );

size_left = BLOCKSIZE;

}

tmp = currentblock++;

size_left -= 1;

}

return( tmp );

}

void return_node(tree_node_t *node)

{ node->left = free_list;

free_list = node;

}

tree_node_t *create_tree(void)

{ tree_node_t *tmp_node;

tmp_node = get_node();

tmp_node->left = NULL;

return( tmp_node );

}

void left_rotation(tree_node_t *n)

{ tree_node_t *tmp_node;

key_t tmp_key;

tmp_node = n->left;

tmp_key = n->key;

n->left = n->right;

n->key = n->right->key;

n->right = n->left->right;

n->left->right = n->left->left;

n->left->left = tmp_node;

n->left->key = tmp_key;

}

void right_rotation(tree_node_t *n)

{ tree_node_t *tmp_node;

key_t tmp_key;

tmp_node = n->right;

tmp_key = n->key;

n->right = n->left;

n->key = n->left->key;

n->left = n->right->left;

n->right->left = n->right->right;

n->right->right = tmp_node;

n->right->key = tmp_key;

}

object_t *find(tree_node_t *tree, key_t query_key)

{ tree_node_t *tmp_node;

if( tree->left == NULL )

return(NULL);

else

{ tmp_node = tree;

while( tmp_node->right != NULL )

{ if( query_key < tmp_node->key )

tmp_node = tmp_node->left;

else

tmp_node = tmp_node->right;

}

if( tmp_node->key == query_key )

return( (object_t *) tmp_node->left );

else

return( NULL );

}

}

int insert(tree_node_t *tree, key_t new_key, object_t *new_object)

{ tree_node_t *tmp_node;

int finished;

if( tree->left == NULL )

{ tree->left = (tree_node_t *) new_object;

tree->key = new_key;

tree->height = 0;

tree->right = NULL;

}

else

{ tree_node_t * path_stack[100]; int path_st_p = 0;

tmp_node = tree;

while( tmp_node->right != NULL )

{ path_stack[path_st_p++] = tmp_node;

if( new_key < tmp_node->key )

tmp_node = tmp_node->left;

else

tmp_node = tmp_node->right;

}

/* found the candidate leaf. Test whether key distinct */

if( tmp_node->key == new_key )

return( -1 );

/* key is distinct, now perform the insert */

{ tree_node_t *old_leaf, *new_leaf;

old_leaf = get_node();

old_leaf->left = tmp_node->left;

old_leaf->key = tmp_node->key;

old_leaf->right = NULL;

old_leaf->height = 0;

new_leaf = get_node();

new_leaf->left = (tree_node_t *) new_object;

new_leaf->key = new_key;

new_leaf->right = NULL;

new_leaf->height = 0;

if( tmp_node->key < new_key )

{ tmp_node->left = old_leaf;

tmp_node->right = new_leaf;

tmp_node->key = new_key;

}

else

{ tmp_node->left = new_leaf;

tmp_node->right = old_leaf;

}

tmp_node->height = 1;

}

/* rebalance */

finished = 0;

while( path_st_p > 0 && !finished )

{ int tmp_height, old_height;

tmp_node = path_stack[--path_st_p];

old_height= tmp_node->height;

if( tmp_node->left->height -

tmp_node->right->height == 2 )

{ if( tmp_node->left->left->height -

tmp_node->right->height == 1 )

{ right_rotation( tmp_node );

tmp_node->right->height =

tmp_node->right->left->height + 1;

tmp_node->height = tmp_node->right->height + 1;

}

else

{ left_rotation( tmp_node->left );

right_rotation( tmp_node );

tmp_height = tmp_node->left->left->height;

tmp_node->left->height = tmp_height + 1;

tmp_node->right->height = tmp_height + 1;

tmp_node->height = tmp_height + 2;

}

}

else if ( tmp_node->left->height -

tmp_node->right->height == -2 )

{ if( tmp_node->right->right->height -

tmp_node->left->height == 1 )

{ left_rotation( tmp_node );

tmp_node->left->height =

tmp_node->left->right->height + 1;

tmp_node->height = tmp_node->left->height + 1;

}

else

{ right_rotation( tmp_node->right );

left_rotation( tmp_node );

tmp_height = tmp_node->right->right->height;

tmp_node->left->height = tmp_height + 1;

tmp_node->right->height = tmp_height + 1;

tmp_node->height = tmp_height + 2;

}

}

else /* update height even if there was no rotation */

{ if( tmp_node->left->height > tmp_node->right->height )

tmp_node->height = tmp_node->left->height + 1;

else

tmp_node->height = tmp_node->right->height + 1;

}

if( tmp_node->height == old_height )

finished = 1;

}

}

return( 0 );

}

object_t *delete(tree_node_t *tree, key_t delete_key)

{ tree_node_t *tmp_node, *upper_node, *other_node;

object_t *deleted_object; int finished;

if( tree->left == NULL )

return( NULL );

else if( tree->right == NULL )

{ if( tree->key == delete_key )

{ deleted_object = (object_t *) tree->left;

tree->left = NULL;

return( deleted_object );

}

else

return( NULL );

}

else

{ tree_node_t * path_stack[100]; int path_st_p = 0;

tmp_node = tree;

while( tmp_node->right != NULL )

{ path_stack[path_st_p++] = tmp_node;

upper_node = tmp_node;

if( delete_key < tmp_node->key )

{ tmp_node = upper_node->left;

other_node = upper_node->right;

}

else

{ tmp_node = upper_node->right;

other_node = upper_node->left;

}

}

if( tmp_node->key != delete_key )

deleted_object = NULL;

else

{ upper_node->key = other_node->key;

upper_node->left = other_node->left;

upper_node->right = other_node->right;

upper_node->height = other_node->height;

deleted_object = (object_t *) tmp_node->left;

return_node( tmp_node );

return_node( other_node );

}

/*start rebalance*/

finished = 0; path_st_p -= 1;

while( path_st_p > 0 && !finished )

{ int tmp_height, old_height;

tmp_node = path_stack[--path_st_p];

old_height= tmp_node->height;

if( tmp_node->left->height -

tmp_node->right->height == 2 )

{ if( tmp_node->left->left->height -

tmp_node->right->height == 1 )

{ right_rotation( tmp_node );

tmp_node->right->height =

tmp_node->right->left->height + 1;

tmp_node->height = tmp_node->right->height + 1;

}

else

{ left_rotation( tmp_node->left );

right_rotation( tmp_node );

tmp_height = tmp_node->left->left->height;

tmp_node->left->height = tmp_height + 1;

tmp_node->right->height = tmp_height + 1;

tmp_node->height = tmp_height + 2;

}

}

else if ( tmp_node->left->height -

tmp_node->right->height == -2 )

{ if( tmp_node->right->right->height -

tmp_node->left->height == 1 )

{ left_rotation( tmp_node );

tmp_node->left->height =

tmp_node->left->right->height + 1;

tmp_node->height = tmp_node->left->height + 1;

}

else

{ right_rotation( tmp_node->right );

left_rotation( tmp_node );

tmp_height = tmp_node->right->right->height;

tmp_node->left->height = tmp_height + 1;

tmp_node->right->height = tmp_height + 1;

tmp_node->height = tmp_height + 2;

}

}

else /* update height even if there was no rotation */

{ if( tmp_node->left->height > tmp_node->right->height )

tmp_node->height = tmp_node->left->height + 1;

else

tmp_node->height = tmp_node->right->height + 1;

}

if( tmp_node->height == old_height )

finished = 1;

}

/*end rebalance*/

return( deleted_object );

}

}

void check_tree( tree_node_t *tr, int depth, int lower, int upper )

{ if( tr->left == NULL )

{ printf("Tree Empty "); return; }

if( tr->key < lower || tr->key >= upper )

printf("Wrong Key Order ");

if( tr->right == NULL )

{ if( *( (int *) tr->left) == 10*tr->key + 2 )

printf("%d(%d) ", tr->key, depth );

else

printf("Wrong Object ");

}

else

{ check_tree(tr->left, depth+1, lower, tr->key );

check_tree(tr->right, depth+1, tr->key, upper );

}

}

int main()

{ tree_node_t *searchtree;

char nextop;

searchtree = create_tree();

printf("Made Tree: Height-Balanced Tree ");

while( (nextop = getchar())!= 'q' )

{ if( nextop == 'i' )

{ int inskey, *insobj, success;

insobj = (int *) malloc(sizeof(int));

scanf(" %d", &inskey);

*insobj = 10*inskey+2;

success = insert( searchtree, inskey, insobj );

if ( success == 0 )

printf(" insert successful, key = %d, object value = %d, \

height is %d ",

inskey, *insobj, searchtree->height );

else

printf(" insert failed, success = %d ", success);

}

if( nextop == 'f' )

{ int findkey, *findobj;

scanf(" %d", &findkey);

findobj = find( searchtree, findkey);

if( findobj == NULL )

printf(" find failed, for key %d ", findkey);

else

printf(" find successful, found object %d ", *findobj);

}

if( nextop == 'd' )

{ int delkey, *delobj;

scanf(" %d", &delkey);

delobj = delete( searchtree, delkey);

if( delobj == NULL )

printf(" delete failed for key %d ", delkey);

else

printf(" delete successful, deleted object %d, height is now %d ",

*delobj, searchtree->height);

}

if( nextop == '?' )

{ printf(" Checking tree ");

check_tree(searchtree,0,-1000,1000);

printf(" ");

if( searchtree->left != NULL )

printf("key in root is %d, height of tree is %d ",

searchtree->key, searchtree->height );

printf(" Finished Checking tree ");

}

}

return(0);

}