Data Structures

Tree Data Structure: Types and Applications

A tree is a non-linear data structure that is used to store the data in a hierarchical form. The data will be maintained in the nodes that are linked in hierarchical order.

1. Introduction to Tree Data Structure

The linear data structures such as Array, Linked List, Stack, and Queue store the data sequentially. So the time complexity increases when performing the operation with a large amount of data. The hierarchical order of Trees helps to perform the operations faster than linear data structures.

Representation

Tree Data Structure Representation
Tree Data Structure Representation
  • Root: The topmost node.
  • Node: Node consists of data, a pointer to the left child, and a pointer to the right child.
  • Parent: A node directly above is called its parent.
  • Children: All the nodes directly under it are called children.
  • Leaves: All the nodes that have no children are called leaves.

2. Types of Trees in Data Structure

Binary TreeA tree with a maximum of two children is allowed for every node.
Binary Search TreeA Binary Tree with a particular ordering of nodes.
AVL TreeA self-balanced Binary Search Tree.
Red Black TreeA self-balanced Binary Search Tree with nodes colored in red or black.
Splay TreeA self-balanced Binary Search Tree to keep the most recently accessed items on top.
HeapA self-balanced Binary Tree with a particular ordering of nodes.
B TreeA self-balanced m-way Binary Search Tree to maintain the sorted stream of data.
B+ TreeB Tree extended for efficient search, insert and delete operations.
Spanning TreeA subset of a Graph that has all vertices connected with the minimum number of edges.
Different Types of Trees in Data Structure

3. Time & Space Complexity of Trees

TypeSearchInsertionDeletionSpace Complexity
Binary Search TreeO (n)O (n)O (n)O (n)
AVL TreeO (log n)O (log n)O (log n)O (n)
Red Black TreeO (log n)O (log n)O (log n)O (n)
Splay TreeO (log n)O (log n)O (log n)O (n)
HeapO (log n)O (log n)O (log n)O (n)
B TreeO (log n)O (log n)O (log n)O (n)
B+ TreeO (log n)O (log n)O (log n)O (n)
Time & Space Complexity of Tree Data Structure

4. Applications of Tree in Data Structure

  • A tree is generally used to represent hierarchical data such as File System.
  • B Tree is widely used for Database indexes and File systems.
  • Heaps are used in Dijkstra’s Algorithm to find the shortest path, implement the priority queues, etc.,
  • Spanning Tree helps in designing any network such as computer networks, telecommunication networks, transportation networks, water supply networks, electrical grids, etc.
  • Splay Tree plays a major role in caching data and is used by GNU compiler, sed stream editor, Unix malloc, etc.
Copyright copyright 2024 Simplerize