Hashing & Binary Tree
Hashing Data Structure
Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for fster access of elements.
Example:
list of values are [11,12,13,14,15] it will be stored at index {1,2,3,4,5} apart from the regular starting from 0.
An example of hash table.
Given a limited range array contains both positive and non-positive numbers.
Since range is limited, we can use index mapping (or trivial hashing). We use values as the index in a big array, therefore we can search and insert elements in O(1) time.
Binary Tree
Unlinke arrays, linked lists, stack and queues, which are linear data structures, trees are hierarchical data structures.
The topmost node is called a root of the tree, elements that are directly under an element are called its children so to speak.
Why do we use binary trees in our data structure?
the first reason is to you want to store information that naturally forms a hierarchy.
For example:
Main applications of binary trees include :
1. manipulate hierarchical data.
2. make information easy to search.
3. manipulate sorted lists of data.
4. as a workflow for compositing digital images for visual effects.
5. router algorithms.
6. Form a multi-stage decision-making.
A binary tree is 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 child.
Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for fster access of elements.
Example:
list of values are [11,12,13,14,15] it will be stored at index {1,2,3,4,5} apart from the regular starting from 0.
An example of hash table.
Given a limited range array contains both positive and non-positive numbers.
Since range is limited, we can use index mapping (or trivial hashing). We use values as the index in a big array, therefore we can search and insert elements in O(1) time.
Binary Tree
Unlinke arrays, linked lists, stack and queues, which are linear data structures, trees are hierarchical data structures.
The topmost node is called a root of the tree, elements that are directly under an element are called its children so to speak.
Why do we use binary trees in our data structure?
the first reason is to you want to store information that naturally forms a hierarchy.
For example:
file system
-----------
/ <-- root
/ \
... home
/ \
ugrad course
/ / | \
... cs101 cs112 cs113
Main applications of binary trees include :
1. manipulate hierarchical data.
2. make information easy to search.
3. manipulate sorted lists of data.
4. as a workflow for compositing digital images for visual effects.
5. router algorithms.
6. Form a multi-stage decision-making.
A binary tree is 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 child.
Comments
Post a Comment