This campaign is over.
Important terminologies
Let’s consider the following tree:
You can refer to this to understand the concept of trees in detail.
Binary tree
Types of binary trees
Read this to understand the types of binary trees in detail.
Binary tree properties
Let’s assume that the height of a tree is h.
Binary trees have some more properties that are used while programming. It is advisable to read this article that explains these properties. You can also solve problems for better understanding.
Structure of a Binary tree
One way to represent a node that contains data is to have two links. These links point to the left and the right children along with the data fields. The following code describes this scenario:
Binary search tree
This is another variant of a binary tree. As the name implies, the main task of this tree is searching.
In a binary search tree, all the left subtree keys must be less than the root key. Also, all the right subtree keys must be greater than the root key. This is called the binary search tree property.
Note: This property must be satisfied at every node in the tree.
You can perform the following two types of operations on a BST:
There is no difference between the regular binary tree declaration and binary search tree declaration. (You can refer to the provided one in the binary tree section.)
Let’s try to find an element in a binary search tree. It is a simple and straightforward operation in BST. It is performed as follows:
You start with the root and move continuously towards left or right using the BST property.
The program is as follows:
You can refer to this to understand these operations in detail.
Task
How will you find the maximum element in a binary search tree?
If you solve this problem, you can solve the practical problem easily!
Heap
A heap is a tree with the following property:
In the following diagram, the tree on the left is a heap (each element is greater than its children) whereas, the tree on the right is not a heap (since 2 is not greater than 4).
Types of heaps
Based on the property of heap, there are two types.
Binary heap representation
In a binary heap, each node can have at most two children.
Let’s assume that the elements are stored in arrays which start at index 1.
Element |
7 |
5 |
6 |
1 |
4 |
2 |
3 |
Index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Assuming that you are working with max heap, you can declare a heap in the following way:
Refer to this to learn about the various operations that you can perform on a binary heap.
Hashing
Hashing is a technique used for storing and retrieving information as quickly as possible. It is used to perform optimal search operations and in implementing symbol tables.
The hash table structure represents an unordered collection of associations between a key and a data value. The keys in a hash table are all unique. This allows a one-to-one relationship between a key and a value. You can perform the following operations:
Components of hashing
Hashing has the following four key components:
For more details, refer to this.
Hashing vs array
In many applications you require arrays that are associated with each other. Such data are very complex and require a key to access them. For example, the key can be a student ID and the data entry can be a collection of grades. Simply using an array can make this scenario cumbersome. Hence, you can use hashing—the process of mapping the keys to available main memory locations.
You can read this concept in detail by reading Concept of hashing.