The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
16 views

  1. Consider the array $A=[20,13,19,8,3,5,4] that represents a heap. Draw the heap after removing the element 20.
  2. List all the distinct integer keys $k$ such that, when $k$ is inserted in the Binary Search Tree of Figure 1, its height increases. Note that you are not allowed to insert an already existing key again. Justify your answer.

asked in Others by Veteran (103k points) | 16 views

1 Answer

0 votes

I. Am assuming we have to make max heap.

For the given array heap will have is

Swap 20 and 4

Delete 20 which is leaf now than Max heapify.

19 > 4 so swap

5 > 4 so swap

Images made using: http://btv.melezinek.cz/binary-heap.html

II. Answer is 38.

We have to add one new key k such that height of the tree increases. To increase height additions should be at the last level.

Let's see the cases.

For K < 37, no increase in height as we will be adding k as left child of 37.

For  K = 37 duplicates not possible

For K =38, it will be added as left child of node 39 (last level node) so height increases.

For  K = 39 or 40 duplicates not possible

For  K = 41 will be added as left child of node 42, no increase in height.

For $42  < K < 95 $ Will be added as right child of 42 (not last level node) so no increase on height.

For $ 95< K < 111$ Will be added as left child of 111  (not last level node) so no increase on height.

For  K = 111 or 112 or 113, duplicates not possible

For  113 < K < 125, Will be added as left child of 125 (not last level node) so no increase on height.

For  K > 125, Will be added as right child of 125 (not last level node) so no increase on height.

 

answered by Loyal (7.9k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,065 questions
47,661 answers
147,304 comments
62,381 users