AVL & B Tree

Review Material

Structure

·       Is user-defined datatype

·       In struct or the struct member can be predefined datatype, array, or struct.

·       Can be made as variable or array;

Ex:

      Struct name{

                  Int x;

                  Char y[10];

      }

            Struct name a, b[10];

DataStruct

Is an arrangement of data, either in the computer’s memory or on the disk storage.

Common example of data structure :

1.     Array               = collection of the same data type

2.     Linked List      =  dynamic datastruct which element/ node can be     

    added or deleted from anywhere at will.

3.     Queues                        = data struct first element in , first out.

4.     Stacks              = data struct first element in , last out.

5.     Binary trees     = data struct which defined as a collection of elements

called nodes. Every node contains a left pointer, a right pointer, and a data element

6.     Hash tables

Link List

Link list                                                                 vs                                 Array

·       Linear collection of nodes                                                  Linear collection of data elements

·       Doen’t store in consecutive memory location                    store value in consecutive memory

·       Can be accessed only in a sequential manner                     can be random in accessing of data

Type of link list:

1.     Single Link List

Only have pointer to point on next node

2.     Double Link List

Have pointers that point on next and previous node.

The first node of link list is called head, the last node is called tail. Inserting value to link list is called push, and removing value from link list is called pop. There is 2 common push and pop in link list, push head & push tail and pop head & pop tail.

If one node lost connection to other node, the node from the lost one until the tail is lost too.

Stack & Queue

            Stack and queue can be created using array or linklist but usually using linklist because the size of array is fixed. The difference between stack and Queue is in the order of element is processed. Stack is first in, last out / processed. Queue is first in, first out / processed.

There are other type of queue, priority queue, circular queue and deques .  Priority queue is the same as queue, but the insertion of new node is based on priority. While circular queue is queue that have L and R, where R is the max or last node and also act as the place to insert new node if the position is empty, and where L is the first node and act as a sign for the first node to be removed or processed. Deques have 2 type: Input restricted deque, where insertions can be done only at one dequeue while deletion can be done in both ends, and Output restricted deque, where deletion can be done only at one of the dequeue while insertion can be done on both ends.

Hashing & Hash Table

Hashing is a technique used to access value in database or array faster.

The way hashing works is the original string of characters are transformed in to short length value or key called Hash Key, that represent the original string or as index to access original value stored in array called Hash Table or database.

The way to hash a string is called Hash Function. There is some important methods to construct hash function :

·       Mid-square

square the string / identifier and extract the middle r bits of the result.

·       Division ( most common )

Divide the string /identifier using modulus operator by value M (can be any value but usually prime number, table size or the size of memory used.

·       Folding

Divide each value into number of part with the same number of digits. Sum all of the part. If there is last carry in hash value, the last carry will be ignored.

·       Digit Extraction

Predefined digit of the give number is considered as the hash address. Ex: if x =14568, we exteact 1^st, 3^rd, and 5^th digit, and the has code of 158

·       Rotating Hash

Use hash method, after get the hash address/key, rotate the address by shifting the digit to get new hash address/key.

Collision is when the different string have the exact same hash address. If this thing happens there is  2 general way to handle this:

-          Linear Probing: search the next empt slot and put the string there

-          Chaining            : put the string in a slot as a chained link ( linked list).

Implementation of Hash Table in Block Chain:

The data in Hash Table is divided and stored in the different node, while in the block chain the data is saved like the hash Table but the data is not divided in blockchain, in blockchain all node have the copy of all the data. As far as i can find, hash table is not used in Block Chain.

Binary Tree

            Is a rooted tree data structure in which each node has at most two children. Those two children that have the same parent are called sibling. The nodes that doesn’t have children is called leaf.

Type of binary tree:

·       PERFECT binary tree is a binary tree in which every level are at the same depth.

         

·       COMPLETE binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A perfect binary tree is a complete binary tree.

       

·       SKEWED binary tree is a binary tree in which each node has at most one child.

       

·       BALANCED binary tree is a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

Maximum number of nodes on level k of a binary tree is 2^k.

Representation in Array

Index on array represents node number

Index 0 is Root node

Index Left Child is 2p + 1, where p is parent index

Index Right Child is 2p + 2

Index Parent is (p-1)/2

Representation in linklist

struct node {         

               int data;

               struct node *left;

               struct node *right;

               struct node *parent;

};

struct node *root = NULL;

Binary Search Tree

            Is sorted binary search tree. Left subtree contain value grater that x(parents) while right subtree contain value grater than x.

BST basic operator:

·       Find(x) : find key x in BST

Search begin at root. If root contains x then terminate the search. If x is less than root’s key then search recursively on left subtree, otherwise search recrusively on right subtree.

·       Insert(x) : insert new key x into BST

Insert begin at the root. If x is less than node’s key then insert x into left subtree, otherwise insert x into right subtree. Repeat until we found an empty node to put x ( x will always be a new leaf)

·       Remove(x): remove key x from BST

If the key is in a leaf, just delete that node. If the key is in a node which has one child, delete that node and connect its child to its parent. If the key is in a node which has two children, find the right most child of its left sub tree (node P), replace its key with P’s key and remove P recrusively. (or alternately you can choose the left most child of its subtree)

Code for assignment

.cpp file can be downloaded in binus forum.


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int total=0;
struct LL{

int qty;
char item[50];

struct LL *next;

}*headLL=NULL, *currLL=NULL;

struct DLL{
int price;

struct DLL *next;
struct DLL *prev;
}*headDLL= NULL, *currDLL = NULL,*tailDLL;

void popTailLL(){
if(headLL != NULL){
if(headLL->next ==NULL){
// if 1 data only
free(headLL);
headLL = NULL;
}
else{
// more than 1 data
currLL = headLL;
while(currLL->next != NULL){
currLL = currLL->next;
}
struct LL *temp= headLL;
while(temp->next != currLL){
temp = temp->next;
}
temp->next = NULL;
free(currLL);
}
}
}

void popHeadLL(){
if(headLL != NULL){
if(headLL->next ==NULL){
// if 1 data only
free(headLL);
headLL = NULL;
}
else{
// more than 1 data
currLL = headLL;
headLL= headLL->next;
free(currLL);
}
}
}

void pushTailLL(int qty, char item []){ 
currLL = (struct LL*)malloc(sizeof(struct LL));
strcpy(currLL->item,item);
currLL->qty = qty;
currLL->next = NULL;

if( headLL == NULL){
headLL=currLL;
}
else{
struct LL *temp = (struct LL*)malloc(sizeof(struct LL));
temp = headLL;
  while (temp->next != NULL){
temp = temp->next;
}
temp->next = currLL;
}
}

void popheadDLL(){
currDLL=headDLL;
if(currDLL){
if(headDLL == tailDLL){
free(headDLL);
headDLL= NULL;
}
}
else{
headDLL= headDLL->next;
free(currDLL);
headDLL->prev=NULL;
}
}

void pushTailDLL(int x){
currDLL = (struct DLL*)malloc(sizeof(struct DLL));
currDLL->price = x;
currDLL->next = NULL;
currDLL->prev = NULL;

if(headDLL == NULL){
headDLL = tailDLL =currDLL;
}
else{
tailDLL->next = currDLL;
currDLL->prev = tailDLL;
tailDLL= currDLL;
}
}

void popTailDLL(){
currDLL=headDLL;
if(currDLL){ // ll is not empty
if(headDLL == tailDLL){  // 1 node left
free(headDLL);
headDLL = NULL;
}
else{ // >1 node
struct DLL* temp =tailDLL;
tailDLL = tailDLL->prev;
free(temp);
tailDLL->next = NULL;
}
}
}

void printData(){
int index=1;
printf("Item List\n");
printf("=====================================================================\n");
currLL= headLL;
while(currLL != NULL){
printf("%d. %-50s  Qty: %d\n",index,currLL->item, currLL->qty);
currLL= currLL->next;
index++;
}
printf("=====================================================================\n");
}

void addData(){
int qty = 0;
char item[50];

printf("Item Name: ");
scanf("%[^\n]",item);getchar();
printf("Quantity: ");
scanf("%d",&qty);

pushTailLL(qty, item);
int price = rand() %1000;
pushTailDLL(price);
total++;
}

void remove(){
int rem=0;
printf("Which one you want to remove? ");
scanf("%d",&rem);
int idx=1;
currLL=headLL;
currDLL=headDLL;
while(idx<=rem && currDLL!=NULL){
printf("%d\n",idx);
if(rem==1){
popHeadLL();
popheadDLL();
total--;
break;
}
else if(rem==total){
popTailLL();
popTailDLL();
total--;
break;
}
else if(idx==rem-1){
struct LL*temp=currLL->next;
currLL->next=currLL->next->next;
free(temp);
printf("heeed");

struct DLL *tem = currDLL->next;
currDLL->next=tem->next;
tem->next->prev=currDLL;
free(tem);
total--;
break;
}
currDLL = currDLL->next;
currLL = currLL->next;
printf(" lol");
}

}

void checkout(){

int index=1;
int total = 0;
printf("CheckOut\n");
printf("==========================================================================\n");
currLL= headLL;
currDLL = headDLL;
while(currLL != NULL){
printf("%d. %-50s  Qty: %d     Price/Unit : %d\n",index,currLL->item, currLL->qty,currDLL->price);;
total +=(currLL->qty * currDLL->price);
currLL= currLL->next;
currDLL= currDLL->next;
index++;
}
printf("Total:  %d\n",total);
printf("==========================================================================\n");


}

int main(){
int choice=0;
do{
system("cls");
printData();
printf("\nMenu:\n1. Add item\n2. Remove Item\n3. Checkout\n");
printf("Your Choice : ");
scanf("%d",&choice); getchar();

if(choice == 1){
addData();
}
else if(choice == 2){
remove();
}
else if(choice ==3){
checkout();
int pick=0;
printf("Pay?\n1. Yes\n2. No\n>> ");
scanf("%d",&pick);
if(pick==1){
printf("Total\n>>>>>Gratis \"Kindess is free\"<<<<<");
}
else if(pick>2 || pick<1){
printf("Wrong choice!");
}
}
else{
printf("Wrong choice!");
}
}while(choice!=3);


}