a) Discuss why it is necessary to balance Binary Search Trees (BSTs).
b) Consider a random sequence of 10, 11 or 12 positive integer numbers in the interval 1 .. 99.
Your sequence is: _________________________
Using the chosen sequence:
b1) build a BST by inserting the numbers, one by one, from left to right, in an empty tree and
b2) calculate the Average Comparison Effort (ACE) value of the BST.
Show the resulted BST and its associated ACE value. What is the minumim ACE value for your BST?
The algorithm for calculating the ACE value for a BST is given below.
Note. The Average Comparison Effort (introduced by Wiener and Pinson) for locating a node in a given BST with n nodes is calculated in the following way:
for (int level = 0, sum = 0; level < treeHeight; level++ ) {
sum += numberOfNodes(level) * (level + 1)
}
ACE = sum / n