A Shed Under The Tree Data Structure
Binary Searchin Trees Python
Once again, I write on another data structure. My other data structure articles have been on linear data structures (Sequentially arranged data structures) from Linked Lists to Stacks and Queues.
Trees are nonlinear data structures(nodes can be connected to more than one node). There are different classifications of trees and more often than not, these classifications are based on the number of nodes each node in the tree is linked to. An example is a binary tree where each node is specified to link to two other nodes
Trees are popularly used to show a relationship between elements which could be hierarchical or otherwise and are efficient when it comes to insertion and deletion of nodes.
TREE DATA STRUCTURE TERMINOLOGIES
- Root - The first node of the tree.
- Path - Sequence of linked nodes.
- Parent - The preceding node.
- Child - A sub-node.
- Internal Node - A Node linked to parent and child nodes.
- Leaf Node - A Node without a sub-node.
- Generations - All Nodes in the same level.
- Siblings - Nodes with the same parent.
- Height - Number of levels from a root node to a leaf node.
HOW TREES ARE STRUCTURED
Every node of the tree directly or indirectly is linked to the root node(the first node) via a path(sequence of linked nodes), has a parent node (a preceding node) and a child node (a sub-node) which could be a value or null(in the case of emptiness). A node with a parent and a child is called an internal node, and one without a child is referred to as a leaf node. Generations spring up sibling nodes(nodes bound by the same parent node) as every node links to different nodes and the number of generations in the tree is the height of the tree.
The following should be noted about trees…
- No two nodes in a tree can reference the same node.
- The root node(the first/head node) is the only node that doesn't get referenced in the data structure.
THE IMPLEMENTATION OF THE TREE DATA STRUCTURE (BINARY SEARCH TREE)
The binary search tree is easy to implement, the structure is as seen below.
PYTHON 3
class Tree:
def __init__(self, data):
self.data = data
self.left_node = None
self.right_node = None
def printer(self): #prints the tree
if self.left_node:
self.left_node.printer()
print(self.data)
if self.right_node:
self.right_node.printer()
It all begins with the Tree class and then the constructor. The instance attributes left_node and right_node are links(addresses) to sibling nodes and the data attribute is a placeholder for elements.
OPERATIONS ON THE BINARY SEARCH TREE DATA STRUCTURE
A handful of operations one could carry out with the tree data structure, but for this article, I will be going over the insert and search operations.
To understand the algorithms used on binary search trees, one must understand the concept of a binary search tree. A binary search tree isn't just a binary tree but also an ordered search tree. In a binary search tree, there is a pattern with which the elements are stored to aid fast searching operations.
A binary search tree in the binary search tree above, it is noticeable that in the subtree of every node, the value left child is less than the value of the parent and the value of the right child is greater than the value of the parent node.
INSERTING ELEMENTS TO THE DATA STRUCTURE
Inserting elements into our tree data structure, we have to create a method for that. The method checks if there's a head(root) node, if there isn't, a new node is created and set as root and then a new element is placed. If there is a root node then, a new(child node) is created and linked to a parent node as a left or right subtree, depending on the pattern of the binary tree.
In the binary search tree above, We notice how the right subtree contains a value greater than the parent and in the same vein, the left subtrees contain values less than that of their parent.
If we are to insert an unknown element data, we could write this...
PYTHON 3
class Tree:
def __init__(self, data):
self.data = data
self.left_node = None
self.right_node = None
def insert(self, data):
if self.data:
if data < self.data:
if self.left_node is None:
self.left_node = Tree(data)
else:
self.left_node.insert(data)
elif data >= self.data:
if self.right_node is None:
self.right_node = Tree(data)
else:
self.right_node.insert(data)
else:
self.data = data
if self.data checks if a head node exists and if it does, then we proceed to check the inequality of data .
The if data < self.data block checks that the magnitude of data to be inserted is less than that of the parent node and inserts the to the left if so.
The elif data >= self.data block runs if data to be inserted is greater than or equal to the value of the parent node and adds data to the right node of the tree.
SEARCHING FOR AN ELEMENT IN THE BINARY SEARCH TREE
The method below searches for an element in the Binary Search Tree using the pattern of the tree.
PYTHON 3
def find(self, data):
if self.data:
if data < self.data:
if self.left_node is None:
return "Data Doesn't Exist"
return self.left_node.find(data)
elif data > self.data:
if self.right_node is None:
return "Data Doesn't Exist"
return self.right_node.find(data)
else:
return "Found it"
else:
return "Empty Tree"
if.self.data verifies that the tree contains at least, a root.
if data < self.data compares the value data to every left subtree, returns " Data Doesn't Exist" in case of left subtree exhaustion.
elif data > self.data compares the value data to every right subtree, returns " Data Doesn't Exist" in case of right subtree exhaustion.
The first else block runs when the comparison of data and a value in the tree evaluates True.
The last else block returns "Empty Tree" in a case where there is no root.
There it is. That's how to insert and search a Tree data structure in the Python programming language.
You can learn about the Asymptotic Analysis which sheds light on the importance of code optimization in this article.