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

Please modify these three function like the question

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 a 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 objectt * delete.by number(tree.node.t *tree, int k) which deletes (and returns) the object stored in the k-th leaf, moving al leaves above it one step to the left (without renumbering) 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 a 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 objectt * delete.by number(tree.node.t *tree, int k) which deletes (and returns) the object stored in the k-th leaf, moving al leaves above it one step to the left (without renumbering)