Why is this convention critical to the effective use of tree

Assignment Help Basic Computer Science

Reference no: EM131076301

Duplicates in an ADT could mean either identical items or, more subtly, objects that match because their class overloads the equality operator so that it compares only certain fields, while differences exist in other fields. If duplicates are allowed in a binary search tree, it is important to have a convention that determines the relationship between the duplicates. Items that duplicate the root of a tree should either all be in the left sub tree or all be in the right sub tree, and, of course, this property must hold for every sub tree.

a. Why is this convention critical to the effective use of the binary search tree?

b. This chapter stated that you can remove an item from a binary search tree by replacing it with the item that either immediately follows or immediately precedes the item to be deleted. If duplicates are allowed, however, the choice between in order successor and in order predecessor is no longer arbitrary. How does the convention of putting duplicates in either the left or right sub tree affect this choice?

Reference no: EM131076301

Questions Cloud

Determine the maximum purchase price : Determine the maximum purchase price you should be willing to pay now for a 6%, $10,000, 10-year bond with interest paid semiannually, if we assume your MARR is 8% per year, compounded quarterly.

Discuss correlation between gdp growth and health outcomes : Discuss the correlation between GDP growth and health outcomes. Compare short-term trends vs. long-term trends. Why would this be an example of the fallacy of composition in health economics?

Significance of daily interruption in sedation : Significance of Daily Interruption in Sedation - mechanical ventilation days by a percentage and drop in hospital expenses and decrease in mechanical ventilator days from the time of admission?

Crowding out is an important topic : Crowding out is an important topic.

Why is this convention critical to the effective use of tree : Why is this convention critical to the effective use of the binary search tree?

Determine the vertex of the graph of the quadratic function : Sketch the graph of the quadratic function f(x) = (x+4)2+1. Identify the vertex and axis of symmetry. Sketch the graph of the quadratic function f(x) = x2+2x+1. Identify the axis of symmetry.

What can you do if you need entries : What can you do if you need entries whose priority values are equal to be served on a first-come, first-served basis?

Draw a graph of the curve : Draw a graph of the curve x2 - y2 = 1. Use implicit differentiation to find the tangent line at all points except (-1, 0) and (1, 0). What goes wrong for these points? What is the tangent line to the curve at the point (1, 0)

How can you adjust a heap if a single value changes : How can you adjust a heap if a single value changes?

User Account

All Pages