Binary Search Tree
A Tree is one of the most commonly used data structures among others.
“ A data structure that stimulates the hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. “
Souce: Wikipedia
The topic of today is Binary Tree. So a binary tree has a similar structure to a general tree but a parent node of a binary tree has no more than two children. This makes operations like inserting a new element or searching for a value in the tree become less complicated.
Geeksforgeeks.org clarifies the difference between a general tree and a binary tree as followed.
For better visualizing of how searching, inserting or deleting a node in a binary tree works, visit cs.usfca.edu. Let’s break it down.
Step 1: Initiate a Node object with class type Node.
class Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root. “
- Source: Wikipedia -
An object of class type Node will have a value and references to its left and right nodes. Since the initial node still hasn’t got any left or right references yet, its value would be None.
Step 2: Initiate an object of type BST.
class BST(object):
def __init__(self, root):
self.root = Node(root)
Here we are assigning an object of type Node to the attribute root of the object of type BST. So now the root of BST will also have a value and references to its left and right nodes.
Step 3: Create a function to insert a new element/node into the tree.
To do this, we need at least 2 functions, one for official usage and another one as a helper.
def _insert(self, node, new_val):
if node is not None:
if node.value > new_val:
if node.left is not None:
self._insert(node.left, new_val)
else:
node.left = Node(new_val)
else:
if node.right is not None:
self._insert(node.right, new_val)
else:
node.right = Node(new_val)
else:
node = Node(new_val)
As much as we love convention, “_insert” is a convention that is used for functions that are not supposed to be called by users.
The simplifier recursive algorithm for this function would be as followed:
- If there is a node available then look at it, if not create a new node.
- If a node is available, compare it with the value to be inserted new_val:
- If the value of the node is bigger than new_val and the node on the left is available, call the function again. If it is not available, create a new node.
- If the value of the node is smaller or equal to new_val and the node on the right is available, call the function again. If it is not available, create a new node.
Note:
- Since we only modify the tree, we don’t need to return anything.
- When moving to a new node, start the function again.
- The function called in the recursive algorithm is a method of the same object of type BST. Do not forget to put “self” in it. There is a great explanation of how “self” works in python pythontips.com.
Exercise:
- Create another function on how to search for a value in the BST.