Python Binary Tree
Introduction of Binary Tree
A binary tree is a data structure commonly used in computer science and programming. It is a type of tree in which each node has at most two children, which are referred to as the left child and the right child. Binary trees are used to store and organize data in various ways, and they can be implemented using a number of different programming languages, including Python.
let’s take an example of a binary tree in which 5,3,7,2,4,6,8 are inserted.
The first number inserted is 5, which becomes the tree’s root node.
Then, 3 is inserted and becomes the left child of the root node, because it is less than the root node’s data.
Next, 7 is inserted and becomes the right child of the root node, because it is greater than the root node’s data.
The next number inserted is 2, which is less than the left child of the root node (5) and again less than (3). So, it becomes the left child of the left child of root node.
The next number, (4), is also less than the root node (5) so we will look at the left side. Now comes the number node (3) and (4) is greater than node (3) so it becomes the right child of node(3)
The next number inserted is (6), which is greater than the root node (5) and less than Node (7). So, it becomes the left child of the node (7).
Finally, 8 is inserted and added as the right child of the right child of the root node.
Types of Data That Can Be Stored in Python Binary Trees
Binary trees can store a wide variety of data types, including integers, strings, and objects. They can also store data in a specific order, such as numerical or alphabetical order. This makes them useful for tasks such as sorting and searching for data.
How to implement binary search trees in Python
A search engine implementation is one example of how a binary tree can be used in a real-world scenario. The data in the binary tree is organized based on keywords, with each node representing a different keyword. When a user enters a search query, the search engine uses the binary tree to find and display relevant results quickly. We will use the numbers that we used in the above example.
class Node: def __init__(self, data): self.data = data self.left = None self.right = None class BinaryTree: def __init__(self): self.root = None def insert(self, data): new_node = Node(data) if self.root is None: self.root = new_node else: current = self.root while True: if data < current.data: if current.left is None: current.left = new_node break else: current = current.left else: if current.right is None: current.right = new_node break else: current = current.right def search(self, data): current = self.root while current is not None: if current.data == data: return current elif data < current.data: current = current.left else: current = current.right return None tree = BinaryTree() tree.insert(5) tree.insert(3) tree.insert(7) tree.insert(2) tree.insert(4) tree.insert(6) tree.insert(8) result = tree.search(6) if result is not None: print("Number found: ", result.data) else: print("Number not found")
The following will be the output.
Number found: 6
Use cases and types of binary tree
|Type of Binary Tree||Description||Use cases|
|Full Binary Tree||A binary tree in which every node has either 0 or 2 children||Representing a hierarchical structure, such as a file system|
|Complete Binary Tree||A binary tree in which every level is completely filled, except possibly the last level and the last level has all keys as left as possible||Representing data in a priority queue, where the parent node has higher priority than its children|
|Perfect Binary Tree||A full binary tree in which all leaf nodes are at the same level||Representing a fixed number of elements, such as a binary heap|
|Balanced Binary Tree||A binary tree in which the height of the left and right subtrees of every node differ by at most 1||Searching for elements in a large dataset, where the height of the tree is logarithmic to the number of elements in the tree|
|AVL Tree||A balanced binary search tree in which the difference between the height of left and right subtrees of any node is not more than 1||Searching for elements in a large dataset, where the height of the tree is logarithmic to the number of elements in the tree|
|Red-Black Tree||A self-balancing binary search tree in which each node has a color attribute, either red or black, and the tree follows certain properties such as all leaf nodes are black and the number of black nodes in any path from the root to a leaf node is constant||Searching for elements in a large dataset, where the height of the tree is logarithmic to the number of elements in the tree|
|Splay Tree||A self-balancing binary search tree in which the recently accessed element is moved to the root, making it frequently accessed elements faster to access||Caching frequently accessed elements for faster retrieval, such as in a web browser cache|
Binary trees have some limitations that should be considered when deciding whether to use them in an application:
- Space complexity: Binary trees require additional memory to store the left and right child pointers of each node. In unbalanced trees, the space complexity can be as high as O(n), where n is the number of elements in the tree.
- Time complexity: For some operations, such as searching for an element, the time complexity of a binary tree can be as low as O(log n) for balanced trees and O(n) for unbalanced trees. However, other operations, such as insertion and deletion, can have an O(n) time complexity for unbalanced trees.
- Unbalanced trees: If the tree becomes unbalanced, the performance of certain operations can degrade significantly. Balancing techniques such as AVL and Red-Black trees can mitigate this issue, but they come with additional complexity and overhead.
- Not all data is suitable: Binary trees are suitable for data with a well-defined ordering, such as numerical or lexicographic data. However, they may not be suitable for data without a clear ordering, such as sets of non-unique items.
In summary, binary trees can be an efficient data structure for organizing and searching large amounts of data. Still, they have certain limitations that should be considered when deciding whether to use them. Unbalanced trees can perform poorly, and not all data types are suitable for organizing in a binary tree.