[ad_1]
We have all watched trees from our childhood. It has roots, stems, branches and leaves. It was observed long back that each leaf of a tree can be traced to root via a unique path. Hence tree structure was used to explain hierarchical relationships, e.g. family tree, animal kingdom classification, etc.
This hierarchical structure of trees is used in Computer science as an abstract data type for various applications like data storage, search and sort algorithms. Let us explore this data type in detail.
Contributed by: Swati Deval
Tree Terminology
A tree is a hierarchical data structure defined as a collection of nodes. Nodes represent value and nodes are connected by edges. A tree has the following properties:
- The tree has one node called root. The tree originates from this, and hence it does not have any parent.
- Each node has one parent only but can have multiple children.
- Each node is connected to its children via edge.
Following diagram explains various terminologies used in a tree structure.
Also Read: Introduction to Decision Trees
| Terminology | Description | Example From Diagram |
| Root | Root is a special node in a tree. The entire tree originates from it. It does not have a parent. | Node A |
| Parent Node | Parent node is an immediate predecessor of a node. | B is parent of D & E |
| Child Node | All immediate successors of a node are its children. | D & E are children of B |
| Leaf | Node which does not have any child is called as leaf | H, I, J, F and G are leaf nodes |
| Edge | Edge is a connection between one node to another. It is a line between two nodes or a node and a leaf. | Line between A & B is edge |
| Siblings | Nodes with the same parent are called Siblings. | D & E are siblings |
| Path / Traversing | Path is a number of successive edges from source node to destination node. | A – B – E – J is path from node A to E |
| Height of Node | Height of a node represents the number of edges on the longest path between that node and a leaf. | A, B, C, D & E can have height. Height of A is no. of edges between A and H, as that is the longest path, which is 3. Height of C is 1 |
| Levels of node | 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 | Level of H, I & J is 3. Level of D, E, F & G is 2 |
| Degree of Node | Degree of a node represents the number of children of a node. | Degree of D is 2 and of E is 1 |
| Sub tree | Descendants of a node represent subtree. | Nodes D, H, I represent one subtree. |
Types of Trees
Types of trees depend on the number of children a node has. There are two major tree types:
- General Tree: A tree in which there is no restriction on the number of children a node has, is called a General tree. Examples are Family tree, Folder Structure.
- Binary Tree: In a Binary tree, every node can have at most 2 children, left and right. In diagram below, B & D are left children and C, E & F are right children.
Binary trees are further divided into many types based on its application.
- Full Binary Tree: If every node in a tree has either 0 or 2 children, then the tree is called a full tree. The tree in the above diagram is not a full binary tree as node C has only the right child.
- Perfect Binary tree: It is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.
In perfect full binary tree, l = 2h and n = 2h+1 – 1 where, n is number of nodes, h is height of tree and l is number of leaf nodes. In the above diagram, h is 2 so leaves will be 4 and nodes will 23 – 1 which is 7.
- Balanced Tree: If the height of the left and right subtree at any node differs at most by 1, then the tree is called a balanced tree.
- Binary Search Tree: It is a binary tree with binary search property. Binary search property states that the value or key of the left node is less than its parent and value or key of right node is greater than its parent. And this is true for all nodes.
Binary search trees are used in various searching and sorting algorithms. There are many variants of binary search trees like AVL tree, B-Tree, Red-black tree, etc.
Also Read: What is Machine Learning? How does it work?
Trees in Data Science
A Tree structure is used in predictive modelling. It is usually called a Decision tree. In the Decision tree, each internal node represents a test or condition on a predictive variable, and edge gives various possible answers to this test. Leaf node gives the outcome of all tests on a path. Decision tree for accepting or rejecting job offer is as follows:
Deciding whether to accept or reject a job is based on two parameters: salary and commute time. Nodes specify conditions on which these two parameters are tested. The priority of the condition depends on how close it is to root. The most affecting parameter is tested first, in this case, salary. So that is the 1st split at the root. Then the next relevant condition. Hence, decision trees not only help in finding the decisions, but it also does in the fastest way.
There are many algorithms like CART (Classification And Regression Tree), Random forest, which helps in building models.
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.
0
[ad_2]
Source link