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

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).

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

}

Delete Function Code:

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

}

}