I need help with the following programming problem, i just need METHODS, as desc
ID: 3547467 • Letter: I
Question
I need help with the following programming problem, i just need METHODS, as described in the questions.
1) Write a method in class BinaryTree to determine whether a given binary tree is a heap (max or min). What is the running time of your algorithm?
2) Write method in class MinHeap to find the largest item in a binary min heap. What is the complexity of your algorithm?
3) Add a method in class AVLTree to test whether a given binary search tree is AVL balanced. What is the running time of your algorithm?
Please, answer what is required as stated in the question, nothing else.
Thank you.
Explanation / Answer
1)
Checking if right element(min) is greater or left elment(max) is greater and then checking the child trees
Time complexity:O(nlogn)
2)
Method 1 (Use Bubble k times)
1) Modify Bubble Sort to run the outer loop at most k times.
2) Print the last k elements of the array obtained in step 1.
Time Complexity: O(nk)
Like Bubble sort, other sorting algorithms like Selection Sort can also be modified to get the k largest elements.
Method 2 (Use temporary array)
K largest elements from arr[0..n-1]
1) Store the first k elements in a temporary array temp[0..k-1].
2) Find the smallest element in temp[], let the smallest element be min.
3) For each element x in arr[k] to arr[n-1]
If x is greater than the min then remove min from temp[] and insert x.
4) Print final k elements of temp[]
Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + klogk)
Thanks to nesamani1822 for suggesting this method.
Method 3(Use Sorting)
1) Sort the elements in descending order in O(nLogn)
2) Print the first k numbers of the sorted array O(k).
Time complexity: O(nlogn)
2)
3)
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
method: checking difference between heights of left and right subtrees which cannot be more than one for all nodes.
Time complexity: O(nlogn)