Hashing and hash table, Trees and binary tree

Hashing
hashing is a technique used for storing and retrieving keys in a rapid manner. in hashing a value is transformed into a shorter value in a way in which it represent a key to that specific value, it is used to index and retrieve data in a way that it is faster that to search manually. hashing can also be defined as a concept of distributing keys in a table(array) using a hash function.
Hash function
some method to hash a function includes:-
- mid-square:-
* square the string and then use the appropriate number of bits from the middle of the square to obtain the hash-key
- Division :-
* divide the string using the modulus operator
- folding :-
* partition the string into several parts, then add the part together to obtain the hash key
- digit extraction :-
* predefined the digit of the given number is considered as the hash address
- rotating hash :-
* use any method of hashing then shift the digits to get a new address
Collision
there will be cases in which a certain hash address be similar with another data, it is called collision.
There are two ways we can handle this.
- linear probing :-
* when a collision happen, we should iterate the cell to find a new empty cell, due to iterating, this has a bad search complexity, another way to do this is to,
- chaining :-
* we store each data in a chain(linked list), if there is a collision we iterate through the chain.

I tried to make a hash table with chaining, i may be wrong but its worth taking a look.
https://drive.google.com/file/d/1v00aMBAhcp-G5CCdA32MpioGLjUEOaBz/view?usp=sharing

Tree and Binary Tree
A tree is a non linear data structure that represent the hierarchal relationship among objects.
A tree is a collection of one or more nodes
concept :-
the top is called as the root
a line connecting two nodes is an edge
nodes which don't have children is called a leaf
nodes that have the same parent is called sibling
degree of node is the total sub tree of the node
depth is the max degree of nodes

A binary tree is a rooted tree data structure in which each node has at most 2 children
types :-
- perfect (every leaf have the same depth
- complete (every level is completely filled)
- skewed( in which each binary tree node has 1 child)
- balanced (no leaf is far from the root)
property of the binary tree
maximum number of nodes on level k of a binary tree is 2^k
height of the tree is the total number of levels

implementation

struct node {
    int data;
    struct node *left;
    struct node *right;
    struct node *parent;
};

threaded binary tree concept
in a normal binary tree, nodes contains a null pointer, when null pointers can be used to store a more relevant piece of data, for example these pointer can point to the predecessor or parent. these special pointers are called thread.

advantages
- it enables linear traversal of elements in the tree
- linear traversal eliminates the use of stacks which will consume more memory space and time
- it make ease to find parent without explicitly using the parent pointer
- it enables moving forward or backward.