There is an interesting data structure that has got its application in a wide number of scenarios in computer science. This data structure is Tree. Other data structures such as arrays, linked lists, stacks, and queues are linear data structures that store data sequentially.
To perform any operation in a linear data structure, the time complexity increases along with the increase in the data size (input data). But, it is not acceptable in today’s computational world since we have a lot of data to be processed.
Introduction to Tree Data Structure
Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure. But before getting into that, let’s ask ourselves a question.
Q: How should we decide which data structure to use?
Our choice of data structure depends upon several factors:
- What needs to be stored? A certain data structure can be the best fit for a particular kind of data
- Cost of operations. Quite often, we want to minimize the cost of the most frequently performed operations
- Memory consumption. Sometimes, we may want to minimize the memory usage
- Easy implementation. We may also choose a data structure for ease of implementation, although this may not be the best strategy.
Recommended reading: What Is Data Structure and Their Applications?
Q: What do we use Tree for?
The tree is one data structure that’s quite often used to represent hierarchical data. For example, let’s say we want to show employees in an organization and their positions in an organizational hierarchy, we can show it like this:
This particular logical structure in the image above is a Tree. If we look at this structure upside down and then it will resemble a real tree. The root here is at the top and we are branching out in a downward direction. The logical representation of the tree data structure is always like that. Root at the top and branch out in a downward direction.
=> Tree is an efficient way of storing and organizing data that is naturally hierarchical.
The tree data structure can be defined as a collection of entities called nodes linked together to simulate a hierarchy. The tree is a non-linear data structure. The topmost node in the tree is called the root of the tree. Each node will contain some data and this can be data of any type. In the image above, data is the name of the employee and their designation. We may have an object with two string fields to store that info.
Each node will contain some data and may contain a link or reference to some other nodes that can be called its children.
Various types of trees have been created throughout the past years, to suit certain apps and meet certain constraints or requirements. Some examples are binary search tree, B tree, red-black tree, splay tree, treap, AVL tree, and n-ary tree. Let’s take a closer look at some of them.
FURTHER READING: |
1. What Is Big O Notation? |
2. Stacks and Queues in Data Structures: An Overview in 2022 |
Binary Search Trees
A binary search tree (BST), as the name indicates, is a binary tree where data is organized in a hierarchical structure. This data structure stores values in sorted order. A BinaryBinary Tree is a Tree in which each node can have at most 2 children.
Every node in a binary search tree comprises four attributes.
- key: The value stored in the node.
- left: The pointer to the child on the left
- right: The pointer to the child on the right.
- p: The pointer to the parent node.
A binary search tree has a unique property that distinguishes it from other trees. This property is known as the binary-search-tree property.
Let’s assume that A is a node in a binary search tree.
- If B is a node in the left subtree of A, then B.key ≤ A.key
- If B is a node in the right subtree of A, then B.key ≥ A.key
Application of tree in Computer science:
- Storing naturally hierarchical data. For example, the files system in our computer disk driver is stored in the form of a Tree. The file and folder hierarchy is naturally hierarchical data.
- Organizing data for quick search, insertion, and deletion. Example: Binary search trees can give us O(log n) time for searching an element in it. This is so fast and effective when we want to look for a specific element.
- Trie: is a special kind of Tree used to store dictionaries. It’s really fast and efficient and is used for dynamic spell checking
- Network Routing algorithm
Heaps
A Heap is a special case of a binary tree where the parent nodes are compared to their children with their values and are arranged accordingly.
Let us see how we can represent heaps. Heaps can also be represented using trees as well as arrays. The following images show us how we can represent a binary heap using a binary tree and an array.
Heaps can be one of two types:
- Min Heap — the key of the parent is smaller than or equal to those of its children. This is known as the min-heap property. The root will contain the heap’s minimum value.
- Max Heap — the key of the parent is bigger than or equal to those of its children. This is known as the max-heap property. The root will contain the heap’s maximum value.
Applications of heaps
- Can be used in a heapsort algorithm.
- Can be used to implement priority queues as the priority values can be ordered according to the heap property where the heap can be implemented using an array.
- Queue functions can be developed using heaps with O(log n) time complexity.
- Can be used to find the káµ—Ê° smallest (or biggest) value in a given array.
For more articles like this, just follow our Facebook, LinkedIn, and Twitter.