Take the height-balanced tree code, and replace the key field by a field int lea
ID: 3701755 • Letter: T
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 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 <stdio.h>
#include <stdlib.h>
#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 );
}
}
Explanation / Answer
object_k delete(tree_node_t* tree, int k)
object_k *deleted _object;
if(tree->left==NULL)
return (NULL);
else if (tree->right==NULL)
{
if(tree->k=delete_k)
{
delete_object=(object_k*)tree->left;
tree->left=NULL;
return(deleted_object);
}
else
return (NULL);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.