1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
sergey [27]
2 years ago
10

Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree roote

d at v.
(a) Modify the Insert operation (given below) to insert an element so that all the .sum fields of the tree are correct after applying the Insert operation. (Assume that all the .sum fields were correct before the Insert operation.) Your modified algorithm should take the same time as the original Insert operation. Explain your modification and give pseudo-code for the modified algorithm.

function Insert(T,z)

y <-- LocateParent(T,z)

z.parent <-- y

if (y = NIL) then T.root <-- z ;

else if (z.key< y.key) then y.left <-- z

else y.right <-- z

(b) Argue for the correctness of your algorithm. Explain why all the .sum fields are correct after running your modified Insert operation.

(c) Analyze the running time of your modified algorithm in terms of the size n and the height h of the binary search tree.
Computers and Technology
1 answer:
AVprozaik [17]2 years ago
6 0

Answer:

Each time you insert a new node, call the function to adjust the sum.

This method has to be called each time we insert new node to the tree since the sum at all the

parent nodes from the newly inserted node changes when we insert the node.

// toSumTree method will convert the tree into sum tree.

int toSumTree(struct node *node)

{

if(node == NULL)

return 0;

// Store the old value

int old_val = node->data;

// Recursively call for left and right subtrees and store the sum as new value of this node

node->data = toSumTree(node->left) + toSumTree(node->right);

// Return the sum of values of nodes in left and right subtrees and

// old_value of this node

return node->data + old_val;

}

This has the complexity of O(n).

Explanation:

You might be interested in
This loop is a good choice when you know how many times you want the loop to iterate in advance of entering the loop.1. do-while
Luba_88 [7]

Answer:

Option 3 is the correct answer.

Explanation:

  • In c, c++ or Java programming language, The for loop takes three parameters in which first is an initialization, second is condition check and the third is an increment. None of the other loop (except for loop) takes three parameters. The other loop takes only one parameter and that is the condition check.
  • So when a user knows about the times of iteration then it is a good choice to use the for loop but when the person does not know about the times of iteration if the loop. It means the iteration of the loop is based on the condition then it is a good choice to chose while or Do-while loop.
  • The above question wants to ask which loop for a user can best if he familiar with the iteration of the loop then the answer is for loop which is started from option 3. Hence Option 3 is the correct answer while the other is not because--
  1. Option 1 states about the do-while loop which takes condition only.
  2. Option 2 states about the while loop which also takes condition only.
  3. Option 4 states about the infinite loop which is not any loop.
  4. Option 5 states about none of these which is not correct because option 3 is the correct answer.

6 0
3 years ago
Assume that a gallon of paint covers about 350 square feet of wall space. Create anapplication with a main() method that prompts
Elena-2011 [213]

Answer:

import java.util.Scanner;

public class PaintClculator {

   public static void main(String[] args) {

Scanner in = new Scanner(System.in);

       System.out.println("Enter Values for length, width, and height of the room");

       double length = in.nextDouble();

       double width = in.nextDouble();

       double height = in.nextDouble();

       double wallArea = calculateWallArea(length,width,height);

       double noGallons = calculatePaint(wallArea);

       double price = price(noGallons);

       System.out.println("Price is: "+ price);

   }

   // Creating Method to Calculate Wall Area

   public static double calculateWallArea( double length, double width, double height){

       // formular for the surface area of a room Area=2*length*heigth+2*width*height+lenth*width

       double Area = 2*length*height+2*width*height+length*width;

       System.out.println("Wall Area: "+Area);

       return Area;

   }

   //Creating method to calculate amount of paint

   public static double calculatePaint(double Area){

       double noGallons = Area/350;

       System.out.println("Number of gallons: "+noGallons);

       return noGallons;

   }

   // Creating Method Calculate Price

   public static double price(double noGallons){

       return noGallons*32;

   }

}

Explanation

  1. Created Three Methods in all; calculateWallArea(), calculatePaint(), and price()
  2. Method calculateWallArea() calculates area based on this formula Area=2*length*heigth+2*width*height+lenth*width
  3. The value of Area is passed to method calculatePaint() Which calculates the number of gallons required to cover the area given that one gallon covers 350 wall space
  4. Method price() calculates and dis[plays the price by calling method calculatePaint() that returns number of gallons. since one gallon is 32$
3 0
3 years ago
Please help me very important
3241004551 [841]

Answer:

C, Or D.

Explanation:

<em>Because A speed enhancing hard drive Can store any type of quick file if you just click on it will load fast. Same thing goes for a hard drive but you have to transfer the file</em>

4 0
2 years ago
Assume that you have 22 slices of pizza and 7 friends that are going to share it (you've already eaten). There's been some argum
xz_007 [3.2K]

Answer:

In Python:

numberOfWholeSlices = int(22/7)

print(numberOfWholeSlices )

Explanation:

For each friend to get a whole number of slices, we need to make use of the int function to get the integer result when the number of slices is divided by the number of people.

So, the number of slice is: 22/7

In python, the expression when assigned to numberOfWholeSlices  is:

numberOfWholeSlices = int(22/7)

Next, is to print the calculated number of slices

print(numberOfWholeSlices )

4 0
3 years ago
Josephine is in the process of creating ads within her Standard Display campaign. She finds that there are two main ad formats t
Tresset [83]

Answer:

B. Responsive display ads

E. Uploaded ad (Image & AMPHTML).

Explanation:

If what you want to achieve is greater control and greater efficiency and scale while you place your ad? Then the two ad format to achieve that are, responsive display ad and uploaded ad.

The uploaded ad will guarantee you have greater control while the responsive display ad gives you greater scale and efficiency.

6 0
3 years ago
Other questions:
  • PLEASEEE HELPPPP me
    13·1 answer
  • 3. Which one of the following statements is correct? _____ variables are those whose storage bindings are created when their dec
    12·1 answer
  • The smallest building block of a wireless lan is a ______.
    5·1 answer
  • ____________ occurs when a provider does not support data export or when a provider's service is unavailable through others.
    11·1 answer
  • Select the antonym for given word freedom
    7·2 answers
  • LeonRoyal15 if anyone plays fortnite
    10·2 answers
  • Two-dimensional random walk (20 points). A two-dimensional random walk simulates the behavior of a particle moving in a grid of
    14·1 answer
  • Why is know app downloading in my android phone even if I have 900 MB ???
    8·2 answers
  • Imagine you are a toy designer. How would you use measuring, dimensions, volume, and surface area information to create your toy
    10·2 answers
  • Each of the flowchart segments in Figure 3-24 is unstructured. Redraw each segment so that it does the same processes under the
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!