Binary tree a tree whose at most 2 children. since each element in a binary tree can have only 2 children, we typically name them the left and right child.
A binary tree contains the Following part:
1. Data
2.Pointer to left child
3.Pointer to right child
Tree vocabulary: the topmost node is called root of the tree The element that are directly under an element are called its children and directly above something its called parents. Element with no children are called leaves.
For example:
A<---- this is a root
/ \
B C
/ \ / \
E F G H<---- leaves
why Binary Tree??
1. if we want to store information that naturally forms a hierarchy then we will use binary tree.
2. trees provide moderate access/search (quicker than linked list but slower than array)
3. Trees Provide moderate insertion /deletion ( Quicker than array and slower than unordered Linked list)
4. Trees don't have an upper limit on number of nodes as nodes are linked using pointers.
main application of trees include:
1. Manipulate hierarchy data
2. Make information easy to search
3. Manipulate sorted Lists of data
4. as a workflow for composing digital images for visual effects.
5. Router algorithms
6. form of a mullti-stage decision -making
this is the example of Binary Tree in C:
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* right;
struct node* left;
};
//allocate a new node with the given data and NULL left and right Pointers
struct node* newNode(int data){
struct node* node=(struct node*)malloc(sizeof(struct node);
node->data=data;
node->left = NULL;
node->right=NULL;
return(node);
}
int main(){
//make a root
struct node* root =newNode(1);
root->left =newNode(2);
root->right=newNode(3);
root->left->left = new node (4)
//the tree would be like this
/*
*/
return 0;
}
Hashing
Hash table is a data structure that stores data in an associative. in a hash table data is stored in an array format, where each data value has its own unique index value.
Hashing is a technique to convert a range of key values into a range of index of an array
there are 3 basic operations for hash table:
1. search-searches an element in a hash table.
2. insert- inserts an element in a hash table.
3. delete - Deletes an element from a hash table.
I got this code from: https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/
hash fucntion will return integer 0-19
vector <string> hashTable[20];
int hashTableSize=20;void insert(string s)
{
// Compute the index using Hash Function
int index = hashFunc(s);
// Insert the element in the linked list at the particular index
hashTable[index].push_back(s);
}void search(string s)
{
//Compute the index by using the hash function
int index = hashFunc(s);
//Search the linked list at that specific index
for(int i = 0;i < hashTable[index].size();i++)
{
if(hashTable[index][i] == s)
{
cout << s << " is found!" << endl;
return;
}
}
cout << s << " is not found!" << endl;
}Algoritma hash digunakan dalam block chain untuk memastikan data yang dituliskan valid, sehinggga perubahan data secara sepihak akan sulit dilakukan. terutama jika block chain diimplementasikan pada sistem terdistribusi dengan konsensus tertentu, jika ada perubahan data pada suatu blok akan menghasilkan hash yang berbeda sehingga blok blok selanjutnya menjadi tidak valid.
teknologi teknologi block chain yang sekarang diketahui masih menggunakan fungsi hash yang lama, contohnya bitcoin yang masih menggunakan SHA-12, ada beberapa algoritma hash yang baru dan cukup populer yaitu KECCAK dan BLAKE2, kedua algoritma ini merupakan finalis dalam penentuan SHA-3
