Week 9

Know more about Binary Search Tree

• Efficiency of Binary Search Tree

This week Danny lead us learn more knowledge about BST(Binary Search Tree).

First, we come to discuss of the efficiency of the BST with the initial insert method. 

For example, to an empty BST, if we insert 10 numbers from 1 to 10 with increasing or decreasing order. One of the Tree will be like:

The other one is almost same but with converse numbers. Obviously, the height is so high. The BST does really a bad job to the inserting numbers that have been in ordered before.In other words, to numbers in certain order, BST could not display its special features.

So how we deal with that. By the lab I find we could use random module to change the inserting order of the numbers in a number list. Like this: 

import random

while number_list:

   num = random.choice(number_list)

   number_list.remove(num)

   bst.insert(num)

Although it could fix the problem in some way, it is not a perfect method. We should find the key part of the problem is that out BST could not adjust its existing structures to fit the new inserting number. Hence, we have to optimize the initial insert method.

  I have not come up with some great idea about this. I need to think of it for some days.