let be red-black tree storing entriesand let be the key of an entry in show how to construct from tin (logntimetwo red-black trees and ''such that contains all the keys of less than kand 'contains all the keys of greater than this operation destroys - show that the nodes of any avl tree can be colored "redand "blackso that becomes red-black tree - the mergeable heap adt consists of operations insert( , )removemin()unionwith( )and min()where the unionwith(hoperation performs union of the mergeable heap with the present onedestroying the old versions of both describe concrete implementation of the mergeable heap adt that achieves (lognperformance for all its operations - consider variation of splay treescalled half-splay treeswhere splaying node at depth stops as soon as the node reaches depth [ / perform an amortized analysis of half-splay trees - the standard splaying step requires two passesone downward pass to find the node to splayfollowed by an upward pass to splay the node describe method for splaying and searching for in one downward pass each substep now requires that you consider the next two nodes in the path down to xwith possible zig substep performed at the end describe how to perform the zig-zigzig-zagand zig steps - describe sequence of accesses to an -node splay tree twhere is oddthat results in consisting of single chain of internal nodes with external node childrensuch that the internal-node path down alternates between left children and right children - explain how to implement an array list of elements so that the methods add and get take (logntime in the worst case (with no need for an expandable array