True or False with explanations a. it is possible to build a balanced AVL tree f

Question

True or False with explanations

a. it is possible to build a balanced AVL tree from a non-sorted array of n numbers in O(n)

b. it is possible to build an AVL tree from a sorted array in time O(n)

For part a I have false. It will be quicker as insertion to an AVL tree takes O(logn)

For b I have false also. Every third insertion will cause a rotation so I think this will result in a tree built in Omega(n)?

Explanation / Answer

a. Its false, you cannot do it, if one could then we simply take the n elements and build the tree in O(n) time then made an inorder traversal of the tree to get the elements in sorted order, total time required will be O(n), but we have a O(nlogn) lower bound on comparison sorting, hence it contradicts the bound, hence cannot be done. b. True, we simply build the binary search tree which we regularly build. (by recursion the middle element is the root and then pass the left of the array to the function again then the right of the array to the same function then take the pointers and merge them, we can show that this tree is a AVL Tree quite easily(try proving it)) I am writing the function in C/C++ // A tree node has a value, heightdifference and left, right pointers node *AVLfromSorted(int *Array, int n/*(size)*/, int *Height){ Node * root = malloc(...); root-> value = Array[n/2]; int l,r; root->left = AVLfromSorted(Array,n/2-1,&l); root->right = AVLfromSorted(&Array[n/2+1],n - n/2,&r); root->heightdifference = l-r; *Height = max(l,r); return root; } //this func will generate the required AVL

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.