Make a Binary Search Tree

here, you will be asked to make a binary search tree (BST) from a randomly generated permutation of numbers from 1 to 20. You will then calculate:

1- the height of each tree and make and provide a histogram of the height. 

2- the imbalance of the two main subtrees for each binary tree made and plot a histogram. 

3- Lastly, you will implement AVL and show how it changes the BSTs on the most imbalanced trees made. 

• Generate a random permutation of the numbers 1-20 using the random.sample() function in Python.
• make a binary search tree (BST) from the permutation using the insert() method provided in the skeleton code. To mak the histogram, I suggest you generate at least 1000 random sequences and save the height and imbalance of each tree.
• Calculate the height of each tree in the BST and make a histogram of the height using the height() method provided in the skeleton code. You can use a Python library such as matplotlib to make the histogram.
• Calculate the imbalance of the two main subtrees for each binary tree made using the imbalance() method provided in the skeleton code. You should record the imbalance for each tree and plot a histogram of the imbalances using a Python library such as matplotlib.
• Implement AVL and show how it changes the BSTs on the most imbalanced trees made. You can use the rotate_left() and rotate_right() methods provided in the skeleton code to implement AVL. You should show the BSTs before and after the AVL transformations and record the number of transformations needed to balance the trees.

Your submission should include the following:

1. Completed python script
2. Two histograms
3. A report that describes your implementation and discusses the results.
4. Two examples of trees with high height or significant imbalance made with

Answer rating: 100% (QA)

Creating a complete Python script for the requested task along with histograms and a report is a substantial project that would require significant co... View the full answer