Assume that we are using a linked representation of a complete binary tree T, and an extra reference to the last node of that tree. Show how to update the reference to the last node after operations insert or remove in O(logn) time, where n is the current number of nodes of T. Be sure to handle all possible cases, as illustrated in Figure 9.12.

Transcribed Image Text:

(2B) (4,C) (SA) (SA) (4,0 (9F) (62) (15,K) (9) 7,0) (20_B) (7,0) (15,KT (12,H ((11,5) (14,1 (16,X)) 25 (14,E) (8,W) (208) (10,L) (16,X) (25 J) (12,H) (b) (a)