Given the set of keys 1, . . . , n, where key i has weight wi , i = 1, . . . , n

Question

Given the set of keys 1, . . . , n, where key i has weight wi , i = 1, . . . , n. The Optimal Binary Search Tree problem is to construct a binary search tree for these keys, in such a way that Pn i=1 widi is minimized, where di is the depth of key i in the tree (note: here we assume the root has a depth equal to one). This sum is called the weighted access cost. Consider the greedy heuristic for Optimal Binary Search Tree: for keys 1, . . . , n, choose as root the node having the maximum weight. The repeat this for both the resulting left and right subtrees. Apply this heuristic to keys 1-5 with respective weights 50,40,20,30,40. Show that the resulting tree does not yield the minimum weighted access cost.

Explanation / Answer

ANSWER:

Number of elements: 5

Keys: 1,2,3,4 and 5

Weights={50, 40, 20, 30, 40}

Analysis:

Step 1) Select root node depth d0=1

Weights= {50, 40, 20, 30, 40}

Node with maximum weight is node 1 and weight is 50

BST = {1}

W= {50}

WAC= {1*50} =50

Step 2)   at depth d2=2

Weights={40, 20, 30, 40}

Node with maximum weight will be 2 and its weight 40 is less than root node, it is fixed in left sub tree node.

BST ={1,2}

W={50,40}

WAC={ 50+(2*40)} =130

Step 3)   

Weights={ 20, 30, 40}

Node with maximum weight will be 5 and its weight 40 is less than root.

We can fix it as left sub tree’s right child

at depth d3=3

BST ={1,2,5}

W={50,40,40}

WAC={ 50+(2*40)+(3*40)} =130+120 = 250

Step 4)   

Weights={ 20, 30}

Node with maximum weight will be 4 and its weight 30 is less than root.

Also it is less than left sub tree root, fix it as left child.

at depth d3=3

BST ={1,2,5,4}

W={50,40,40,30}

WAC={ 50+(2*40)+(3*40)+(3*30)} = 250+90 =340

Step 5)   

Weights={ 20}

Node with maximum weight will be 3 and its weight 20 is less than root.

Also it is less than left sub tree root and its child node. So it is fixed at depth 4 as left child.

at depth d4=4

BST ={1,2,5,4,3}

W={50,40,40,30,20}

WAC={ 50+(2*40)+(3*40)+(3*30)+(3*20)} = 340+60 =400

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.