Please only answer the question 6. Please only answer the question 6. 5. (2 poin
ID: 3602797 • Letter: P
Question
Please only answer the question 6.
Please only answer the question 6.
5. (2 points) Construct a Huffiman trie based on the following distribution of letters. When combining two trees, always place the smaller on the left. cCCC 6. (2 points) Show that for any leaf v in a binary search tree, if u is the parent of v, then either key[v] is the largest key in the tree smaller than key[u], or key[v] is the smallest key in the tree larger than key[u]. (Heileman, p.216) 7. (2 points) Prove that the maximum number of nodes in a binary tree of height h is 2-1. 8. (1 point) In terms of Mand L, what is the maximum height of a BTree with n elements? Sources of questions: Gregory L. Heileman, Data Structures, Algorithms, and Object Oriented Programming, New York, NY, McGraw-Hill, 1996Explanation / Answer
ANSWER FOR 6TH QUESTION
WITH THE HELP OF FOLLOWING DATA
A Binary Search Tree is a binary tree where nodes are ordered in the following way:
As from the above data gathered
If u is the parent of leaf v. Then from the above explanation we can clearly say that key of leaf v value is either greater or smaller than the key of u.
if v is the left chid then we can say key[v]<key[u] that we can say key[v] is the largest key in the tree smaller than key[u].
if v is the left chid then we can say key[v] < key[u] that we can say key[v] is the largest key in the tree smaller than key[u].
if v is the right chid then we can say key[v] > key[u] that we can say key[v] is the smallest key in the tree lareger than key[u].
THANK YOU