Trees are the longest living organisms on Earth, and never die of old age
This is a completely interesting but meaningless fact, the reason why I'm saying this is because today in our data structures series we will learn about trees.
Today you will learn:
- What are trees and their use cases.
- Types of trees
- Basic python implementation
- What is a tree?
- Binary Tree Implementation
A tree is a non-linear data structure that is used to represent hierarchical data.
Examples of hierarchical data may include:
- Company's chain of command
- E-Commerce categories
- Mafia's chain of command
Let's take the company chain of command example, the structure may look like this:
This kind of data would be ideal for trees, but before we move on to code, we first gotta understand some key terms.
- Node - Element in a tree
- Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.
- Parent − Any node except the root node has one edge upward to a node called the parent.
- Child − The node below a given node connected by its edge downward is called its child node.
- Leaf − The node which does not have any child node is called the leaf node.
- Subtree − Subtree represents the descendants of a node.
- Visiting − Visiting refers to checking the value of a node when control is on the node.
- Traversing − Traversing means passing through nodes in a specific order.
- Levels − The Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
- Keys − Key represents a value of a node based on which a search operation is to be carried out for a node.
Below are the types of trees in a data structure:
A tree without any constraints, a node may have infinite children.
The binary tree is the kind of tree in which most two children can be found for each parent. The kids are known as the left child and right child. This is the most popular type of tree.
Binary Search Tree
Binary Search Tree is basically a binary tree but with additional constraints. The left child value of a node should in BST be less than or equal to the parent value, and the right child value should always be greater than or equal to the parent’s value. This Binary Search Tree property makes it ideal for search operations since we can accurately determine at each node whether the value is in the left or right sub-tree. This is why the Search Tree is named.
Named after their inventor Adelson, Velski & Landis, AVL trees are height-balancing binary search trees. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor.
A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the colour (red or black). These colours are used to ensure that the tree remains balanced during insertions and deletions. Although the balance of the tree is not perfect, it is good enough to reduce the searching time and maintain it around O(log n) time, where n is the total number of elements in the tree.
A spanning tree is a subset of Graph G, which has all the vertices covered with the minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.
A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Generally, Heaps can be of two types:
- Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
- Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
- Store hierarchical data, like folder structure, organization structure, XML/HTML data.
- A Binary Search Tree is a tree that allows fast search, insert, delete on a sorted data. It also allows finding the closest item.
- Heap tree is a tree data structure that is implemented using arrays and used to implement priority queues.
- B-Tree and B+ Tree: They are used to implement indexing in databases.
- Syntax Tree: Used in Compilers.
- K-D Tree: A space partitioning tree used to organize points in K dimensional space.
- Trie: Used to implement dictionaries with prefix lookup.
- Suffix Tree: For quick pattern searching in a fixed text.
- Spanning Tree and shortest-path trees are used in routers and bridges respectively in computer networks
- As a workflow for compositing digital images for visual effects.
We are gonna implement a binary tree because it's the most popular tree, and it's the base for many other trees. For this implementation, we will use linked lists because it's simple.
class TreeNode: def __init__(self, val): self.val = val self.p = None self.left = None self.right = None def get(self): return self.val def set(self, val): self.val = val def getChildren(self): children =  if(self.left != None): children.append(self.left) if(self.right != None): children.append(self.right) return children
class BinaryTree: def __init__(self): self.root = None def search(self, k): node = self.root while node != None: if node.key == k: return node if node.key > k: node = node.left else: node = node.right return None def insert(self, k): t = TreeNode(k) parent = None node = self.root while node != None: parent = node if node.key > t.key: node = node.left else: node = node.right t.p = parent if parent == None: self.root = t elif t.key < parent.key: parent.left = t else: parent.right = t return t def delete(self, node): if node.left == None: self.transplant(node, node.right) elif node.right == None: self.transplant(node, node.left) else: succ = self.minimum(node.right) if succ.p != node: self.transplant(succ, succ.right) succ.right = node.right succ.right.p = succ self.transplant(node, succ) succ.left = node.left succ.left.p = succ
That's it, I know I haven't gone deeper into trees. This is just an introductory post, but I would recommend reading other great articles on the internet. I hope you learned something today, and if you got any questions feel free to leave them down in the comments.