Application of tree data structure
Why Tree?
Unlike Array and Linked List, which are linear data structures, the tree is a hierarchical (or non-linear) data structure.
Definition
When starting out programming, it is common to understand better the linear data structures than data structures like trees and graphs.
Trees are well-known as non-linear data structures. They don’t store data in a linear way. They organize data hierarchically.
Let’s dive into real-life examples!
What do I mean when I say in a hierarchical way?
The HTML tag contains other tags. We have a head tag and a body tag. Those tags contain specific elements. The head tag has meta and title tags. The body tag has elements that show in the user interface, for example, h1, a, li, etc.
A technical definition
A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data, and it may or may not have a child node.
The first node of the tree is called the root. If this root node is connected by another node, the root is then a parent node and the connected node is a child.
All Tree nodes are connected by links called edges. It’s an important part of trees because it’s managing the relationship between nodes.
Leaves are the last nodes on a tree. They are nodes without children. Like real trees, we have the root, branches, and finally the leaves.
Other important concepts to understand are height and depth.
The height of a tree is the length of the longest path to a leaf. The depth of a node is the length of the path to its root.
Terminology summary
1.Root is the topmost node of the tree
2. Edge is the link between two nodes
3. Child is a node that has a parent node
4. Parent is a node that has an edge to a child node
5. Leaf is a node that does not have a child node in the tree
6. Height is the length of the longest path to a leaf
7. Depth is the length of the path to its root
Binary trees
Implementation of Binary Search Tree in Javascript
A tree is a collection of nodes connected by some edges. A tree is a non-linear data structure. A Binary Search tree is a binary tree in which nodes that have lesser value are stored on the left while the nodes with a higher value are stored at the right.
Now let’s see an example of a Binary Search Tree node:
// Node class
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
As in the above code snippet, we define a node class having three-property data, left and right, Left and right are pointers to the left and right node in a Binary Search Tree. Data is initialized with data which is passed when the object for this node is created and left and right is set to null.
// Binary Search tree class
class BinarySearchTree
{
constructor()
{
// root of a binary seach tree
this.root = null;
}
The above example shows a framework of a Binary Search tree class, which contains a private variable root that holds the root of a tree, it is initialized to null.
// function to be implemented
// insert(data)
// remove(data)
Now lets implement each of this function:
- insert(data) — It inserts a new node in a tree with a value data
// helper method which creates a new node to
// be inserted and calls insertNode
insert(data)
{
// Creating a node and initailising
// with data
var newNode = new Node(data);
// root is null then node will
// be added to the tree and made root.
if(this.root === null)
this.root = newNode;
else
// find the correct position in the
// tree and add the node
this.insertNode(this.root, newNode);
}
// Method to insert a node in a tree
// it moves over the tree to find the location
// to insert a node with a given data
insertNode(node, newNode)
{
// if the data is less than the node
// data move left of the tree
if(newNode.data < node.data)
{
// if left is null insert node here
if(node.left === null)
node.left = newNode;
else
// if left is not null recur until
// null is found
this.insertNode(node.left, newNode);
}
// if the data is more than the node
// data move right of the tree
else
{
// if right is null insert node here
if(node.right === null)
node.right = newNode;
else
// if right is not null recur until
// null is found
this.insertNode(node.right,newNode);
}
}
insert(data) — It creates a new node with a value data, if the tree is empty it add this node to a tree and make it a root, otherwise, it calls insert(node, data).
insert(node, data) — It compares the given data with the data of the current node and moves left or right accordingly, and recur until it finds a correct node with a null value where a new node can be added.
2. remove(data) — This function removes a node with a given data.
// helper method that calls the
// removeNode with a given data
remove(data)
{
// root is re-initialized with
// root of a modified tree.
this.root = this.removeNode(this.root, data);
}
// Method to remove node with a
// given data
// it recur over the tree to find the
// data and removes it
removeNode(node, key)
{
// if the root is null then tree is
// empty
if(node === null)
return null;
// if data to be delete is less than
// roots data then move to left subtree
else if(key < node.data)
{
node.left = this.removeNode(node.left, key);
return node;
}
// if data to be delete is greater than
// roots data then move to right subtree
else if(key > node.data)
{
node.right = this.removeNode(node.right, key);
return node;
}
// if data is similar to the root’s data
// then delete this node
else
{
// deleting node with no children
if(node.left === null && node.right === null)
{
node = null;
return node;
}
// deleting node with one children
if(node.left === null)
{
node = node.right;
return node;
}
else if(node.right === null)
{
node = node.left;
return node;
}
// Deleting node with two children
// minumum node of the rigt subtree
// is stored in aux
var aux = this.findMinNode(node.right);
node.data = aux.data;
node.right = this.removeNode(node.right, aux.data);
return node;
}
}
*remove(data) — It is helper methods that call removed by passing root node and given data and updates the root of the tree with the value returned by the function
*removeNode(node, data) — It searches for a node with a given data and then perform certain steps to delete it.
Conclusion
The tree is a hierarchical and non-parametric data structure. It is simple to understand due to its visual representation. It can work on both classification and continuous data. It is used in data science to build predictive models as it can handle large amounts of data and can be validated statistically.