Recall the definition ot an AVL tree: an AVL tree is either leaf or node(h, k, l
ID: 3653598 • Letter: R
Question
Recall the definition ot an AVL tree: an AVL tree is either leaf or node(h, k, l, r) where h is the height ot the node, k is the key for the node, and l and r are the left and right sub - trees. Furthermore, the height of l and r must differ by at most one. We already know how to perform insertion, deletion, and lookup in an AVL tree in time O(lgn) for each operation. Write pseudocode for a function tolist which, given an AVL tree, produces a list of the tree's keys in sorted order. Prove that your implementation of tolist runs in O(n) time. Write pseudocode for a function fromlist which, given a sorted list of keys, produces a valid AVL tree containing those keys in 0(n)timc. Free Hint: Repeated insertion will not be enough. Try a divide - and - conquer approach. Prove that your implementation of fromlist runs in O(n) time. Graph Representations; 12 points Consider an adjacency forest representation for graphs: a vector of AVL trees with an entry for each node, where the entry for each node u is an AVL tree whose keys are the nodes adjacent to v. For this problem, we will assume that we have implementations of tolist and fromlist that both run in O(n) time (see above problem). Write peudocode for a function adjacent which, given an adjacency forest and the index of a node, produces a list of adjacent nodes. Use tolist in your solution. How long does it take to run adjacent for every node in a graph? Write pseudocode for a function makeforest which, given an adjacency list, produces the corresponding actyacency forest. Use fromlist in your solution. How long does it take to run makeforest on a given graph? How long do breadth - first search and depth - first search take using adjacency forests?Explanation / Answer
a ) since the inorder traversal of a binary search tree gives the sorted sequence of keys , we will use the inorder traversal and when we output the element we insert it into a array which has n size. where n is number of nodes in the tree.
tolist(root)
stack s; /* declare stack */
s.push(root); /* push root in the stack */
A[1..n]; /* declare array */
i = 1;
while ( s is not empty ) do /* loop until s is not empty */
top = s.top();
if top != NULL then
if top is not visited) then /* if we haven't processed top then add left child to stack
s.push(left(top));
else
A[i] = key(top); /*process top*/
s.pop();
s.push(right(top)); /* push right child of top */
i = i + 1
else
s.pop();
if s is not empty then
make top visited
return A
A is the list which consists of sorted keys.
b) there is only one loop in the program and we see that every node is pushed to the stack at most once and at least once , and we are iterating over the elements of s which is the number of nodes pushed in the stack which is n so the running time is O(n).
c) we will pick the middle element of array each time and make it the root of the tree.the pseudocode is
fromlist(A,left,right) return root element of tree
if ( left < right ){
mid = (left + right )/ 2;
allocate node r
key(r) = A[mid];
left(r) = fromlist(A,left,mid-1);
right(r) = fromlist(A,mid+1,right);
}
d )
the recurrence relation can be written as
t(n) = 2 * t (n/2) + O(1) , becuase at each step of recursion we are splitting the array into two parts and we are taking constant time in creating root node. each time we are halving the subproblem into half,the recursion is similar to quick sort , just we have no partition method just simply creation and assinment of root which is O(1) rather than O(n) time taken by partition subroutine.
By master method the solution to this recurrence is
O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.