Last week we answered the question, what is a Data structure? And today we will continue going over some more examples of the different types of data structures.
Binary Tree Data Structure
A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right children.
A Binary Tree node contains the following parts.
- Data
- Pointer to left child
- Pointer to the right child
Binary Search Tree
This is a node-based binary tree data structure that has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
Heap Data Structure
A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Generally, Heaps can be of two types:
- Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
- Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
Hashing Data Structure
Hash Table is a data structure that stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Accessing data becomes very fast if we know the index of the desired data.
Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses a hash technique to generate an index where an element is to be inserted or is to be located.
Hashing:
Hashing is a technique or process of mapping keys, values into the hash table by using a hash function. It is done for faster access to elements. The efficiency of mapping depends on the efficiency of the hash function used.
This is all for today, I’ll see you in the next round. Happy coding.