Week 8: Binary Search Trees

Hello friends, 

       The main topic in lectures this week was Binary Search Trees (BST's). A binary search tree is a binary tree, whereby every node's value is greater than values of all nodes in its left subtree, and less than the values of all the nodes in its right subtree. BST's allow efficient searching of data. To find a specific value, v in a BST, we can compare v to the value r at the root.

- If v = r, then the value is found

- If v < r, we move down the left subtree than repeat this process

- If v > r, we move down the right subtree then repeat this process

- If we reach an empty node than the value is not in the tree

The find function is defined below for a "BTNode" class.

code:

def _find(node: BTNode,  data: object): 

if not node or node.data == data: # reached None or data 

return node 

elif data < node.data: 

return _find(node.left, data) 

# data => node.data: 

return _find(node.right, data) 

We also discussed in class that this find function can be modified and used to implement insert and delete function. This is because both these function do similar comparisons to the values at each node, but then modify the node when the value is found. 

It is important to note that searching a BST  is only more efficient than searching linearly through a list when the BST is balanced. If a BST has values at each node, whereby the child of each node is greater than its parent, then searching through the BST will be the same as searching through a list. Thus, BST's are efficient only when there are values greater and smaller in the subtrees of each node. A 'complete binary tree' is an ideal BST, because each level is full except the bottom level, which is filled from left to right.