Question

In: Computer Science

Write a JAVA program which prints the root node after the "remove" procedure the the splay...

Write a JAVA program which prints the root node after the "remove" procedure the the splay tree.

Solutions

Expert Solution

#include<stdio.h>

#include<stdlib.h>

// An AVL tree node

struct node

{

int key;

struct node *left, *right;

};

/* Helper function that allocates a new node with the given key and

NULL left and right pointers. */

struct node* newNode(int key)

{

struct node* node = (struct node*)malloc(sizeof(struct node));

node->key = key;

node->left = node->right = NULL;

return (node);

}

// A utility function to right rotate subtree rooted with y

// See the diagram given above.

struct node *rightRotate(struct node *x)

{

struct node *y = x->left;

x->left = y->right;

y->right = x;

return y;

}

// A utility function to left rotate subtree rooted with x

// See the diagram given above.

struct node *leftRotate(struct node *x)

{

struct node *y = x->right;

x->right = y->left;

y->left = x;

return y;

}

// This function brings the key at root if key is present in tree.

// If key is not present, then it brings the last accessed item at

// root. This function modifies the tree and returns the new root

struct node *splay(struct node *root, int key)

{

// Base cases: root is NULL or key is present at root

if (root == NULL || root->key == key)

return root;

// Key lies in left subtree

if (root->key > key)

{

// Key is not in tree, we are done

if (root->left == NULL) return root;

// Zig-Zig (Left Left)

if (root->left->key > key)

{

// First recursively bring the key as root of left-left

root->left->left = splay(root->left->left, key);

// Do first rotation for root, second rotation is  

// done after else

root = rightRotate(root);

}

else if (root->left->key < key) // Zig-Zag (Left Right)

{

// First recursively bring the key as root of left-right

root->left->right = splay(root->left->right, key);

// Do first rotation for root->left

if (root->left->right != NULL)

root->left = leftRotate(root->left);

}

// Do second rotation for root

return (root->left == NULL)? root: rightRotate(root);

}

else // Key lies in right subtree

{

// Key is not in tree, we are done

if (root->right == NULL) return root;

// Zag-Zig (Right Left)

if (root->right->key > key)

{

// Bring the key as root of right-left

root->right->left = splay(root->right->left, key);

// Do first rotation for root->right

if (root->right->left != NULL)

root->right = rightRotate(root->right);

}

else if (root->right->key < key)// Zag-Zag (Right Right)

{

// Bring the key as root of right-right and do  

// first rotation

root->right->right = splay(root->right->right, key);

root = leftRotate(root);

}

// Do second rotation for root

return (root->right == NULL)? root: leftRotate(root);

}

}

// The delete function for Splay tree. Note that this function

// returns the new root of Splay Tree after removing the key  

struct node* delete_key(struct node *root, int key)

{

struct node *temp;

if (!root)

return NULL;

  

// Splay the given key

root = splay(root, key);

  

// If key is not present, then

// return root

if (key != root->key)

return root;

  

// If key is present

// If left child of root does not exist

// make root->right as root   

if (!root->left)

{

temp = root;

root = root->right;

}

  

// Else if left child exits

else

{

temp = root;

  

/*Note: Since key == root->key,

so after Splay(key, root->lchild),

the tree we get will have no right child tree

and maximum node in left subtree will get splayed*/

// New root

root = splay(root->left, key);

  

// Make right child of previous root as

// new root's right child

root->right = temp->right;

}

  

// free the previous root node, that is,

// the node containing the key

free(temp);

  

// return root of the new Splay Tree

return root;

  

}

// A utility function to print preorder traversal of the tree.

// The function also prints height of every node

void preOrder(struct node *root)

{

if (root != NULL)

{

printf("%d ", root->key);

preOrder(root->left);

preOrder(root->right);

}

}

/* Driver program to test above function*/

int main()

{

// Splay Tree Formation

struct node *root = newNode(6);

root->left = newNode(1);

root->right = newNode(9);

root->left->right = newNode(4);

root->left->right->left = newNode(2);

root->right->left = newNode(7);

int key = 4;

root = delete_key(root, key);

printf("Preorder traversal of the modified Splay tree is \n");

preOrder(root);

return 0;

}  


Related Solutions

Write a program to remove the node of Fruit type which contains “Banana” from a given...
Write a program to remove the node of Fruit type which contains “Banana” from a given linked list and then print the updated linked list. Part of the program is given below but it is incomplete. You need to complete it. You should create your own data file. After you complete the program, please check it carefully to ensure it can handle the following cases: Banana is the first node in the linked list. Banana is not the first node...
Consider the following splay tree: Show the paths from root to node 12, 10, 9, 5,...
Consider the following splay tree: Show the paths from root to node 12, 10, 9, 5, and 1 after search node 3. (Sample answer: for the above splay tree, the path from root to node 9 can be expressed as 10, 4, 6, 8, 9.) The path from root to node 12:Question Blank.The path from root to node 10:Question Blank.The path from root to node 9:Question Blank.The path from root to node 5:Question Blank.The path from root to node 1:Question...
write a java program that implements the splay tree data structure for the dictionary abstract data...
write a java program that implements the splay tree data structure for the dictionary abstract data type. Initially the program reads data from "in.dat", and establishes an ordinary binary search tree by inserting the data into the tree. The data file contains integers, one per line. in.dat file contents: 3456 5678 1234 2369 7721 3354 1321 4946 3210 8765 Then the program starts an interactive mode. The commands are as follows. S 1000 - splay the tree at 1000 F...
Write a Java program that takes in a string and a number and prints back the...
Write a Java program that takes in a string and a number and prints back the string from the number repeatedly until the first character... for example Pasadena and 4 will print PasaPasPaP. Ask the user for the string and a number Print back the string from the number repeatedly until the first character For both programs please utilize: methods arrays loops Turn in screenshots
Write a Java program that prompts the user to input a string and prints whether it...
Write a Java program that prompts the user to input a string and prints whether it is a palindrome. A palindrome is a string which reads the same backward as forward, such as Madam (disregarding punctuation and the distinction between uppercase and lowercase letters). The program must use the stack data structure. The program must include the following classes: The StackX class (or you can use the Java Stack class). The Palindrome class which must contain a method named palindrome()...
1.Write a Java program that prompts the user for a month and day and then prints...
1.Write a Java program that prompts the user for a month and day and then prints the season determined by the following rules. If an invalid value of month (<1 or >12) or invalid day is input, the program should display an error message and stop. Notice that whether the day is invalid depends on the month! You may assume that the user will never enter anything other than integers (no random strings or floats will be tested.) Tips: Break...
Write a java program that prints to the screen a countdown 2,4,6,8, and then "Who do...
Write a java program that prints to the screen a countdown 2,4,6,8, and then "Who do we appreciate!" (hint use a for loop). Create a java program which prints out a random goodwill message i.e. (Have a great day!) please have at least 4 messages. Write a java program that will ask the user to enter a number and print out to the screen until the number -3 is entered. Write a JAVA program that calls a method that finds...
JAVA PROGRAMMING Write a program that ask the user for a number then prints the cube...
JAVA PROGRAMMING Write a program that ask the user for a number then prints the cube of the number. The program should be called CubeNumbers. Use a value returning method with parameter, call the method myCube.
*Java program* Use while loop 1.) Write a program that reads an integer, and then prints...
*Java program* Use while loop 1.) Write a program that reads an integer, and then prints the sum of the even and odd integers. 2.) Write program to calculate the sum of the following series where in is input by user. (1/1 + 1/2 + 1/3 +..... 1/n)
Use if statements to write a Java program that inputs a single letter and prints out...
Use if statements to write a Java program that inputs a single letter and prints out the corresponding digit on the telephone. The letters and digits on a telephone are grouped this way: 2 = ABC    3 = DEF   4 = GHI    5 = JKL 6 = MNO   7 = PRS   8 = TUV 9 = WXY No digit corresponds to either Q or Z. For these 2 letters your program should print a message indicating that they are not...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT