CP164 Study Guide - Final Guide: Binary Search Algorithm, The Algorithm, Init
The BST Class
The BST class constructor is very simple, containing only a root node that is initialized
to None and a node count.
class BST:
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty BST.
Use: bst = BST()
-------------------------------------------------------
Postconditions:
Initializes an empty bst.
-------------------------------------------------------
"""
self._root = None
self._count = 0
return
Searching a BST
We have not yet seen the BST insertion method, but we can understand it better if we understand
how to find an value in a BST. Searching a BST can be done either recursively or iteratively. We
will examine the iterative algorithm here - we will soon see examples of BST methods that are
far more easily done recursively than iteratively.
To understand how to search a BST we have to understand how nodes are order in the tree. As
noted above:
for each node N, the keys in the left subtree of N are less than the key of N, and the keys in the
right subtree of N are greater than the key ofN
This means that each time we look at a node, if the value in the node does not match the key
value we must look to either the left or right children of the node. The direction chosen depends
on the comparison between the current node value and the key. The algorithm is:
• Get the root node.
• If there is no node, the search fails.
• Search the tree: compare the node value to the key:
•
• If the key and node value match, the search ends successfully.
• If the key < the node value, search the left subtree of the node.
• If the key > the node value, search the right subtree of the node.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
The bst class constructor is very simple, containing only a root node that is initialized to none and a node count. class bst: def __init__(self): Initializes an empty bst. self. _root = none self. _count = 0 return. We have not yet seen the bst insertion method, but we can understand it better if we understand how to find an value in a bst. Searching a bst can be done either recursively or iteratively. We will examine the iterative algorithm here - we will soon see examples of bst methods that are far more easily done recursively than iteratively. To understand how to search a bst we have to understand how nodes are order in the tree. As noted above: for each node n, the keys in the left subtree of n are less than the key of n, and the keys in the right subtree of n are greater than the key ofn.
