Data Structures: Trees

Introduction

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

Table of Contents

• What is a tree?
  • Common terminologies
  • Types of trees
  • Tree applications
• Binary Tree Implementation
  • Node
  • Tree
• Conclusion

What is a tree?

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.

Common terminologies

• 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.

Types of Trees

Below are the types of trees in a data structure:

General Tree

A tree without any constraints, a node may have infinite children.

Binary Tree

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.

AVL Tree

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.

Red-Black Trees

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.

Spanning 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.

Heap Tree

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:

1. 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.
2. 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.

Tree applications

• 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.

Binary Tree Implementation

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.

Node

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

Tree

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

Conclusion

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.