3. Let T be a binary search tree. Suppose we want to include a eld v.size, the n
ID: 3800050 • Letter: 3
Question
3. Let T be a binary search tree. Suppose we want to include a eld v.size, the number of items stored in the subtree of v, at each node v. a. Given T, describe an algorithm that will populate all the size elds in T. What is the running time of your algorithm?
b. Now suppose we make modications to T by inserting or removing items. For each modication – i.e., an insertion or a removal – describe the modications that have to be made to the size elds of the nodes in T. How much time will such modications take?
c. Using the binary search tree on Figure 3.4, insert an item with key equal to 52 and show the changes that have to be made on the size elds of the nodes in the tree. Now, remove the item with key equal to 75. Again, show the changes that have to be made on the size elds of the nodes in the tree.
Explanation / Answer
BSTREE-Search(x, k)
1: y x
2: while y 6= nil do
3: if key[y] = k then return y
4: else if key[y] < k then y right[y]
5: else y left[y] 6: return (“NOT FOUND”)
BSTREE-Minimum(x)
1: if x = nil then return (“Empty Tree”)
2: y x
3: while left[y]
6= nil do
y left[y]
4: return (key[y])
BSTREE-Maximum(x)
1: if x = nil then return (“Empty Tree”)
2: y x
3: while right[y] 6= nil do y right[y
] 4: return (key[y])
BSTREE-Successor(x)
1: if right[x] 6= nil then
2: { y right[x]
3: while left[y] 6= nil do y left[y]
4: return (y) }
5: else
6: { y x
7: while right[p[x]] = x do y p[x]
8: if p[x] 6= nil then return (p[x])
9: else return (“NO SUCCESSOR”)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.