Skip to main content

Tree Data Structure and Its all types

 

What are tree Data Structures?

  • Tree is a hierarchical data structure that stores the information naturally in the form of a hierarchy style.
  • Tree is one of the most powerful and advanced data structures.
  • It is a non-linear data structure compared to arrays, linked lists, stack, and queue.
  • It represents the nodes connected by edges.
structure of tree

The above figure represents the structure of a tree. Tree has 2 subtrees.
A is a parent of B and C.
B is called a child of A and also a parent of D, E, F.

Tree is a collection of elements called nodes, where each node can have an arbitrary number of children.

FieldDescription
RootRoot is a special node in a tree. The entire tree is referenced through it. It does not have a parent.
Parent NodeParent node is an immediate predecessor of a node.
Child NodeAll immediate successors of a node are its children.
SiblingsNodes with the same parent are called Siblings.
PathPath is a number of successive edges from source node to destination node.
Height of NodeHeight of a node represents the number of edges on the longest path between that node and a leaf.
Height of TreeHeight of tree represents the height of its root node.
Depth of NodeDepth of a node represents the number of edges from the tree's root node to the node.
Degree of NodeDegree of a node represents a number of children of a node.
EdgeEdge is a connection between one node to another. It is a line between two nodes or a node and a leaf.

In the above figure, D, F, H, G are leaves. B and C are siblings. Each node excluding a root is connected by a direct edge from exactly one other node
parent →  children.

Levels of a node

Levels of a node represent the number of connections between the node and the root. It represents a generation of a node. If the root node is at level 0, its next node is at level 1, its grandchild is at level 2, and so on. Levels of a node can be shown as follows:

levels of tree

Note:

- If node has no children, it is called Leaves or External Nodes.

- Nodes which are not leaves, are called Internal Nodes. Internal nodes have at least one child.

- A tree can be empty with no nodes or a tree consists of one node called the Root.

Height of a Node

height of node

As we studied, height of a node is a number of edges on the longest path between that node and a leaf. Each node has height.

In the above figure, A, B, C, D can have height. Leaf cannot have height as there will be no path starting from a leaf. Node A's height is the number of edges of the path to K not to D. And its height is 3.

Note:

- Height of a node defines the longest path from the node to a leaf.

- Path can only be downward.

Depth of a Node

depth of node

While talking about the height, it locates a node at bottom where for depth, it is located at top which is root level and therefore we call it depth of a node.

In the above figure, Node G's depth is 2. In depth of a node, we just count how many edges between the targeting node & the root and ignoring the directions.

Note: Depth of the root is 0.

Advantages of Tree

  • Tree reflects structural relationships in the data.
  • It is used to represent hierarchies.
  • It provides an efficient insertion and searching operations.
  • Trees are flexible. It allows to move subtrees around with minimum effort.

Comments

Popular posts from this blog

Complete Tutorial on Business Analytics

CRISP-DM (Cross Industry Standard Process for Data Mining)                                    The framework is made up of 6 steps: Business Issue Understanding Data Understanding Data Preparation Analysis/Modeling Validation Presentation/Visualization The map outlines two main scenarios for a business problem: Data analysis Predictive analysis Data analysis refers to the more standard approaches of blending together data and reporting on trends and statistics and helps answer business questions that involve understanding more about the dataset such as "On average, how many people order coffee and a donut per transaction in my store in any given week?" Predictive analysis will help businesses predict future behavior based on existing data such as "Given the average coffee order, how much coffee can I expect to sell next week if I were to add a new brand of coffee?" Business Issue Understanding "This initial phase focuses on understanding the project objectives a

What is a Type II Error?

  A Type II error is a false negative in a test outcome, where something is falsely inferred to not exist. This usually means incorrectly accepting the null hypothesis (H0), which is the testing statement that whatever is being studied has no statistically significant effect on the problem. An example would be a drug trial that incorrectly concludes the prescribed medication had no effect on the patient’s ailment, when in fact the disease was cured, but subsequent exams caused a false positive showing the patient was still sick. Null Hypothesis and Statistical Significance In practice, the difference between a false positive and a false negative is usually not so clear-cut. Since the tests are most often quantitively rather than qualitatively based, the results tend to be expressed in a confidence interval value less than 100%, rather than a simple Yes/No decision. This question of how likely the results are to be found if the null hypothesis is true is called statistical significance.

The Art of Winning Kaggle Competitions

 What is Kaggle? Learning data science can be overwhelming. Finding a community to share code, data, and ideas can se e m also seem like an overwhelming as well as farfetched task. But, there is one spot where all of these characteristics come together. That place is called Kaggle. Looked at more comprehensively, Kaggle is an online community for data scientists that offers machine learning competitions, datasets, notebooks, access to training accelerators, and education. Anthony Goldbloom (CEO) and Ben Hamner (CTO) founded Kaggle in 2010, and Google acquired the company in 2017. Kaggle competitions have improved the state of the machine learning art in several areas. One is mapping dark matter; another is HIV/AIDS research. Looking at the winners of Kaggle competitions, you’ll see lots of XGBoost models, some Random Forest models, and a few deep neural networks. The Winning Recipe of Kaggle Competitions involves the following steps: Step one   is to start by reading the competition gu