Question

In: Computer Science

IN C++: Create sets of 1 Million integer, where no integer is repeated. Insert these numbers...

IN C++:

Create sets of 1 Million integer, where no integer is repeated. Insert these numbers to an AVL tree and an R-B tree.

Using a random number generator, select 10% of the numbers in the trees and delete them.
Repeat the experiment 10 times. Report your answers in a tables

Solutions

Expert Solution

#include<bits/stdc++.h>
using namespace std;

// An AVL tree node
class Node
{
   public:
   int key;
   Node *left;
   Node *right;
   int height;
};

// A utility function to get maximum
// of two integers
int max(int a, int b);

// A utility function to get the
// height of the tree
int height(Node *N)
{
   if (N == NULL)
       return 0;
   return N->height;
}

// A utility function to get maximum
// of two integers
int max(int a, int b)
{
   return (a > b)? a : b;
}

/* Helper function that allocates a
new node with the given key and
NULL left and right pointers. */
Node* newNode(int key)
{
   Node* node = new Node();
   node->key = key;
   node->left = NULL;
   node->right = NULL;
   node->height = 1; // new node is initially
                   // added at leaf
   return(node);
}
Node *rightRotate(Node *y)
{
   Node *x = y->left;
   Node *T2 = x->right;

   // Perform rotation
   x->right = y;
   y->left = T2;

   // Update heights
   y->height = max(height(y->left),
                   height(y->right)) + 1;
   x->height = max(height(x->left),
                   height(x->right)) + 1;

   // Return new root
   return x;
}

// A utility function to left
// rotate subtree rooted with x
Node *leftRotate(Node *x)
{
   Node *y = x->right;
   Node *T2 = y->left;

   // Perform rotation
   y->left = x;
   x->right = T2;

   // Update heights
   x->height = max(height(x->left),     
                   height(x->right)) + 1;
   y->height = max(height(y->left),
                   height(y->right)) + 1;

   // Return new root
   return y;
}

// Get Balance factor of node N
int getBalance(Node *N)
{
   if (N == NULL)
       return 0;
   return height(N->left) - height(N->right);
}

// Recursive function to insert a key
// in the subtree rooted with node and
// returns the new root of the subtree.
Node* insert(Node* node, int key)
{
   /* 1. Perform the normal BST insertion */
   if (node == NULL)
       return(newNode(key));

   if (key < node->key)
       node->left = insert(node->left, key);
   else if (key > node->key)
       node->right = insert(node->right, key);
   else // Equal keys are not allowed in BST
       return node;

   /* 2. Update height of this ancestor node */
   node->height = 1 + max(height(node->left),
                       height(node->right));

   /* 3. Get the balance factor of this ancestor
       node to check whether this node became
       unbalanced */
   int balance = getBalance(node);

   // If this node becomes unbalanced, then
   // there are 4 cases

   // Left Left Case
   if (balance > 1 && key < node->left->key)
       return rightRotate(node);

   // Right Right Case
   if (balance < -1 && key > node->right->key)
       return leftRotate(node);

   // Left Right Case
   if (balance > 1 && key > node->left->key)
   {
       node->left = leftRotate(node->left);
       return rightRotate(node);
   }

   // Right Left Case
   if (balance < -1 && key < node->right->key)
   {
       node->right = rightRotate(node->right);
       return leftRotate(node);
   }

   /* return the (unchanged) node pointer */
   return node;
}

// A utility function to print preorder
// traversal of the tree.
// The function also prints height
// of every node
void preOrder(Node *root)
{
   if(root != NULL)
   {
       cout << root->key << " ";
       preOrder(root->left);
       preOrder(root->right);
   }
}

// Driver Code
int main()
{
   Node *root = NULL;
   root = insert(root, 10);
   root = insert(root, 20);
   root = insert(root, 30);
   root = insert(root, 40);
   root = insert(root, 50);
   root = insert(root, 25);
   cout << "Preorder traversal of the "
           "constructed AVL tree is \n";
   preOrder(root);
  
   return 0;
}



Related Solutions

IN C++: Create sets of 1 Million integers with the following characteristics; Sets where no numbers...
IN C++: Create sets of 1 Million integers with the following characteristics; Sets where no numbers repeat Sets where the range of numbers is 1% of the array size Sets where no numbers repeat and each integer has 20 digits
Write a C++ code to insert the following numbers in two Linked Lists. Insert numbers of...
Write a C++ code to insert the following numbers in two Linked Lists. Insert numbers of first list in Linked List#1, and numbers of second list in Linked List#2. Do not insert both lists in a single Linked List. List#1. 5, 78, 45, 23, 11, 89, 10, 78, 6, 99, 876, 5, 67, 13 List#2. 5, 89, 688, 52, 557, 953, 5, 7, 55, 35, 89, 99, 99, 6, 557, 89, 5, 99, 6, 2, 45, 12, 7, 6, 94,...
QUESTION 5 1.    Switch to insert mode, and then create a script that performs the following: •       Sets...
QUESTION 5 1.    Switch to insert mode, and then create a script that performs the following: •       Sets the environment for the script to bash •       Have at least two comment lines that state the purpose of the script •       Clear the screen •       Sends messages back to the screen informing the user of what he or she is seeing displayed on the screen •       Have the script perform the following: o   Show your home directory o   Show your current working directory o   Create a directory called demo, and...
write C program to create 4 threads for summing the numbers between 1 and 40 where...
write C program to create 4 threads for summing the numbers between 1 and 40 where the first thread computes the sum between 1 and 10; the second thread computes the sum between 11 and 20; the third thread computes the sum between 21 and 30; and the fourth thread compute the sum between 31 and 40. The output should be similar to the following. The sum from 1 to 10 = 55 The sum from 11 to 20 =...
/* 1. Fix the CREATE and INSERT statements below to create the SHIPMENT table and insert...
/* 1. Fix the CREATE and INSERT statements below to create the SHIPMENT table and insert its data in DB Fiddle*/ CREATE TABLE SHIPMENT ( ShipmentID Int NOT NULL, ShipperName Char(35) NOT NULL, ShipperInvoiceNumber Int NOT NULL DepartureDate Date NULL, ArrivalDate Date NULL, InsuredValue Numeric(12,2) NOT NULL, CONSTRAINT Shipment_PK PRIMARY KEY (ShipmentID)) ); INSERT INTO SHIPMENT VALUES (1,'ABC Trans-Oceanic', 2008651, '10-Dec-14', '15-Mar-18', 15000.00); INSERT INTO SHIPMENT VALUES (2,'ABC Trans-Oceanic', 2009012, '10-Jan-18', '20-Mar-18', 12000.00); INSERT INTO SHIPMENT VALUES (3,'Worldwide', 49100300, '05-May-18',...
- Create a list with 40 integer random numbers - With a function (def) create two...
- Create a list with 40 integer random numbers - With a function (def) create two new lists from the list created by random numbers, in which on one are the even elements and on the other the odd elements - Create two variables with the length of both new lists and print the variables All exercices must be done in Phyton
Consider a repeated prisoner’s dilemma game that will be repeated for one million rounds. 1. If...
Consider a repeated prisoner’s dilemma game that will be repeated for one million rounds. 1. If this game is played by immortal rational utility maximizers, what is the Nash equilibrium for this repeated game? 2. If this game was played as an experiment using human players, would you expect to see this strategy? 3. If this game was played as an experiment with rational utility maximizers who have a maximum lifespan of 500,000 rounds, what is the Nash equilibrium for...
I have to create a program in C++ where a user can enter as many numbers...
I have to create a program in C++ where a user can enter as many numbers as they want (they predetermine the number of values to be inputted) and then the program can echo that input back to the user and then determine if the numbers were even, odd, or a zero and it outputs how many of each were found. This is to be down with four void functions and no arrays. The program initializes the variables zero, odds,...
Let a , b , c be three integer numbers. Write a C++ program with a...
Let a , b , c be three integer numbers. Write a C++ program with a functions void rotate1(int* a,int* b,int* c) void rotate2(int& a,int& b,int& c) such that a -> b , b -> c and c -> a. Thus we use two different approaches (pointers in rotate1 and references in rotate2).
JAVA PROGRAMMING 1)BuildLists: Write a program to create an ArrayList<Integer>. Fill it with numbers from 1...
JAVA PROGRAMMING 1)BuildLists: Write a program to create an ArrayList<Integer>. Fill it with numbers from 1 to 1000. Then remove every even number. Then remove every multiple of 3 remaining Then remove every multiple of 5 Then remove every multiple of 7 Then sum the array, and print.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT