Summary dan Review Data Structure

-
Jadi pada setengah semster ini, saya sudah mempelajari tentang :
-The diferrence between Circular Single Linked List, Doubly Linked List , and Circular Doubly Linked List atau perbedaan pada Circular Single Linked List, Doubly Linked List , dan Circular Doubly Linked List.
- Single Linked List (Push and Pop)
-Hashing Table and Binnary Tree. The Implementation in Blokchain
-Binary Search Tree

 Jadi, mari kita review ulang satu per satu.

 A. Perbedaan pada Circular Single Linked List, Doubly Linked List , dan Circular Doubly Linked List.

 1. Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL.Ada 2 type circular linked list yaitu circular single linked list dan circular double linked list.Contohnya yaitu :

a. Circular Single Linked List

b.Circular Double Linked List


2. Doubly Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.Contohnya yaitu :


 Sedangkan,

3.Circular Doubly Linked List merupakan linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut. Contohnya yaitu :



B.  Single Linked List (Push and Pop)

Implement a stack using linked list concept. all the linked list operations perform based on Stack operations LIFO(last in first out) and with the help of that knowledge we are going to implement a stack using  linked list. 

Stack operations:
push() : Insert the element into linked list nothing but which is the top node of Stack.
pop() : Return top element from the Stack and move the top pointer to the second node of linked list or Stack

Example of push and pop using linked list in c:

Single linked list:

  • push_front: 5, 3, 7, 9 the output are: 9 ->7 ->3 -> 5 -> NULL
  • void push_front(int number){
  • current=(struct data*)malloc(sizeof(struct data));
  • current->number = number; 
  • if(head==NULL){
  • head=tail=current;
  • tail->next=NULL;
  • }
  • else{
  • current->next=head;
  • head=current;
  • }
  • }

void show (){
current=head;
while(current!=NULL){
printf("%d ",current->number);
current=current->next;
}
}

  • int main (){
  •  push_front(5);
  •  push_front(3);
  •  push_front(9);
  •  push_front(7);
  • show();
  • getchar();
  • return 0;
  • }

  • push_back: 200, 10, 5, 50 the output are: 200 ->50 ->10 ->10 -> NULL
  • void push_back (int number){
  • current=(struct data*)malloc(sizeof(struct data));
  • current->number = number; 
  • if(head==NULL){
  • head=tail=current;
  • tail->next=NULL;
  • }
  • else{
  • tail->next=current;
  • tail=current;
  • tail->next=NULL;
  • }
  • }

  • void show (){
  • current=head;
  • while(current!=NULL){
  • printf("%d ",current->number);
  • current=current->next;
  • }
  • }
  • int main (){
  •  push_back(200);
  •  push_back(10);
  •  push_back(5);
  •  push_back(50);
  • show();
  • getchar();
  • return 0;
  • }

  • pop_front : 10,2,3,4,5 the output are  : 2->3->4->5->NULL
  • void pop_front(){
  • if(head!=NULL){
  • current=head;
  • head=head->next;
  • free(current);
  • }
  • }
  • void show (){
  • current=head;
  • while(current!=NULL){
  • printf("%d ",current->number);
  • current=current->next;
  • }
  • }

  • int main (){
  •  pop_front(10);

  • show();
  • getchar();
  • return 0;
  • }
C. Hashing Table and Binnary Tree. The Implementation in Blokchain
Hash Table: An array that stores pointers to records corresponding to a given phone number. An entry in hash table is NIL if no existing phone number has hash function value equal to the index for the entry.

Collision Handling: Since a hash function gets us a small number for a big key, there is possibility that two keys result in same value. The situation where a newly inserted key maps to an already occupied slot in hash table is called collision and must be handled using some collision handling technique. Following are the ways to handle collisions:
  • Chaining:The idea is to make each cell of hash table point to a linked list of records that have same hash function value. Chaining is simple, but requires additional memory outside the table.
  • Open Addressing: In open addressing, all elements are stored in the hash table itself. Each table entry contains either a record or NIL. When searching for an element, we one by one examine table slots until the desired element is found or it is clear that the element is not in the table.
Implementation In C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define SIZE 20

struct DataItem {
   int data;   
   int key;
};

struct DataItem* hashArray[SIZE]; 
struct DataItem* dummyItem;
struct DataItem* item;

int hashCode(int key) {
   return key % SIZE;
}

struct DataItem *search(int key) {
   //get the hash 
   int hashIndex = hashCode(key);  
 
   //move in array until an empty 
   while(hashArray[hashIndex] != NULL) {
 
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex]; 
   
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }        
 
   return NULL;        
}

void insert(int key,int data) {

   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }
 
   hashArray[hashIndex] = item;
}

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
 
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
   
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      }
  
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }      
 
   return NULL;        
}

void display() {
   int i = 0;
 
   for(i = 0; i<SIZE; i++) {
 
      if(hashArray[i] != NULL)
         printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);
      else
         printf(" ~~ ");
   }
 
   printf("\n");
}

int main() {
   dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
   dummyItem->data = -1;  
   dummyItem->key = -1; 

   insert(1, 20);
   insert(2, 70);
   insert(42, 80);
   insert(4, 25);
   insert(12, 44);
   insert(14, 32);
   insert(17, 11);
   insert(13, 78);
   insert(37, 97);

   display();
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }

   delete(item);
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }
}
Output:
~~  (1,20)  (2,70)  (42,80)  (4,25)  ~~  ~~  ~~  ~~  ~~  ~~  ~~ (12,44)  (13,78)  (14,32)  ~~  ~~  (17,11)  (37,97)  ~~ 
Element found: 97
Element not found


Binary Tree:Binary tree is the data structure to maintain data into memory of program. There exists many data structures, but they are chosen for usage on the basis of time consumed in insert/search/delete operations performed on data structures. Binary tree is one of the data structures that are efficient in insertion and searching operations. Binary tree works on O (logN) for insert/search/delete operations.Binary tree is basically tree in which each node can have two child nodes and each child node can itself be a small binary tree.

Example source code:
#include<stdlib.h>
#include<stdio.h>

struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

void deltree(node * tree)
{
    if (tree)
    {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

node* search(node ** tree, int val)
{
    if(!(*tree))
    {
        return NULL;
    }

    if(val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if(val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if(val == (*tree)->data)
    {
        return *tree;
    }
}

void main()
{
    node *root;
    node *tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);

    /* Printing nodes of tree */
    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);

    /* Search node into tree */
    tmp = search(&root, 4);
    if (tmp)
    {
        printf("Searched node=%d\n", tmp->data);
    }
    else
    {
        printf("Data Not found in tree.\n");
    }

    /* Deleting all nodes of tree */
    deltree(root);
}
Output :
 $./a.out
Pre Order Display
9
4
2
6
15
12
17
In Order Display
2
4
6
9
12
15
17
Post Order Display
2
6
4
12
17
15
9 
Searched node=4

Hashing Table Implementation in Blockchain

Hashing Table Implementation in Blockchain:

Hashing in blockchain refers to the process of having an input item of whatever length reflecting an output item of a fixed length. If we take the example of blockchain use in cryptocurrencies, transactions of varying lengths are run through a given hashing algorithm, and all give an output that is of a fixed length. This is regardless of the length of the input transaction. The output is what we call a hash. A good example is Bitcoin’s Secure Hashing Algorithm 256 (commonly shortened to SHA-256). Hashing using SHA-256 always gives an output result of a fixed length, which has a 256-bits length (the output is 32 bytes). This is always the case whether the transaction is just a single word or a complex transaction with huge amounts of data. What this means is that keeping track of a transaction becomes easier when you can recall/trace the hash. The size of the hash will depend on the hash function utilized, but the out using a particular hashing algorithm will be of a specific size. 

Example:
When you take a YouTube video of say 50 megabytes and hash it using SHA-256, the output will be a hash of 256-bits in length. Similarly, if you take a text message of 5 kilobytes, the output hash will still be 256-bits. The only difference between the two will be the hash pattern. Let’s summarize the above information as follows: Hashing is the umbrella term for Cryptographic hash functions

Cryptographic hash functions

A hash function, will take any transaction/data input and rehash it to produce an output of a fixed size. The process of using a given hash function to process a transaction is called hashing. The transactional output of that given hash function is what we call a hash. And that should be it. There is more we need to expound on to demystify hashing in blockchain. At this point, I want to emphasize that it is good to remember that the basic characteristic of any given hash function lies in the size of its output. This is what gives us the different hash functions (we will get to that in a moment).

Characteristics of cryptographic hash functions

For a cryptographic hash function to be considered secure, it has to portray certain characteristics or properties. It is these properties that make the hash function suitable for cryptocurrencies like Bitcoin or Ethereum that utilize blockchain technology. Let me explain each one in simple terms for us all.

Deterministic

A hash function needs to have a fixed or specific output. What this means is that it doesn’t matter what number of times you process a given input using a hash function; the result is always of the same length. The hashes will be random and of different patterns, but the same size/length. Why is this important? Imagine getting different results for every transaction you record. It simply means it will be impossible for you to keep track of every input data using the hash

Quick Computation

In blockchain technology, a good hash function would be one that performs quick computations for every data input. It may be difficult to find the input data for a hash, but computing or calculating the hash should be ideally very fast. For instance, you can have the hash result of a simple “hi” within a fraction of a second. Similarly, the hash of a very large file will be received within a fraction of a second.

Pre-image resistance

One of the important properties of secure cryptographic hash functions is they are one-way. Let’s take it this way: given a hash of a particular transaction, it should be virtually impossible or practically infeasible to determine the original input data using this output. This property lends a level of security to the blockchain. When given a particular hash, the only possible way of finding what the original input data is if you hashed all the possible combinations of inputs until you eventually hash the correct or corresponding input. However, because the input data is randomized, hashing it is practically impossible.

Different hashes for every input (Randomized)

Hash functions produce different outputs for every input, even if the input data differs by only a digit or letter. For instance, the hash of the word “Alpha” should be completely different from the hash of the word “Alpha1”. If the patterns were to be similar and differ only at the end, then deciphering them would be easy.

Collision resistant

Cryptographic hash functions are also supposed to have collision resistant properties. Collisions can occur in cases where a hash function gives similar outputs for different inputs. For example, if “pic1” is photo and “pic2” is a video, but a hash function produces the same output, then we call that a collision. Normally, this should not happen. However, it could be a result of a “Birthday Box”.

Cryptographic hash functions

  • SHA 256: an output of a 256-bit hash and currently in use on the Bitcoin network
  • Keccak-256: an output of a 256-bit hash; currently in on the Ethereum network

Blockchains and Hashing - where is it used?

Hashing is applied in blockchain as seen in some of the examples used above. Here are more examples.
  • Addresses on the blockchain are derived from hashing e.g. Bitcoin addresses use SHA2-256 and RIPEMD 160.
  • Hashing helps in defining cryptographic signatures that help determine valid transactions.
  • The hash of a transaction makes it easy to keep track of transactions on the blockchain. Instead of looking for a transaction that was the “1030th in block 14573”, it is easier just to copy the hash into a blockchain explorer from where you can view the transaction details.
  • Hashing functions are crucial in crypto mining where a valid nonce is discovered by computing several hashes. This helps to form a consensus on the blockchain.
  • The use of “hash of the data” helps to store large amounts of data on the blockchain. This data is time-stamped and can be hashed for future reference. It makes the permanent data storage less bulky or simply more economical.
  • Hashrate- determining how fast and smoothly-running the mining process is. It is vital in determining difficulty levels during mining.

Conclusion

The cryptographic hash function is an integral part of the blockchain innovation. It is essentially a feature that gives security capabilities to the processed transactions, making them immutable. Hashing is also at the center of “Merkle Trees”, which is an advanced approach to blockchain hashing. It is useful in issues of scalability, and mobile/light wallets
D. Binary Search Tree
Binary Tree Binary Tree adalah struktur data yang mirip dengan Linked List. Bila Linked List dianalogikan sebagai rantai yang linier maka Binary Tree dianalogikan sebagai pohon. Binary Tree dikelompokkan menjadi tree yang tidak berurut (unordered Binary Tree) dan tree yang terurut (ordered Binary Tree). Binary Tree dapat digambarkan berdasarkan kondisinya, yaitu: 

Binary Search Tree (BST) merupakan tree yang terurut (ordered Binary Tree) yang memiliki kelebihan bila dibanding dengan struktur data lain. Diantaranya adalah proses pengurutan (sorting) dan pencarian (searching) dapat dilakukan bila data sudah tersusun dalam struktur data BST. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam  struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list seperti contoh berikut:



Agar data benar-benar tersusun dalam struktur data BST, dua aturan yang harus dipenuhi pada saat data diatur dalam BST adalah sebagai berikut: 1. Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri. 2. Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t. BST berikut adalah sebuah BST berukuran 9 dengan kedalaman 3 dengan node daun (leaf) adalah 1, 4, 7 dan 13.


Contoh Aplikasi BST 1. Membangun daftar vocabulary yang merupakan bagian dari inverted index (sebuah struktur data yang digunakan oleh banyak mesin pencari seperti Google.com, Yahoo.com dan Ask.com) 2. Banyak digunakan dalam bahasa pemrograman untuk mengelola dan membangun dynamic sets. Pembentukan BST Bila diketahui sederetan data 5, 3, 7, 1, 4, 6, 8, 9 maka pemasukan data tersebut dalam struktur data BST, langkah per langkah, adalah sebagai berikut: 
 Langkah 1: Pemasukan data 5 sebagai root  
Langkah 2: Pemasukan data 3 disebelah kiri simpul 5 karena 3 < 5. 
Langkah 3: Pemasukan data 7 disebelah kanan simpul 5 karena 7 > 5.  
Langkah 4: Pemasukan data 1. Karena data 1 lebih kecil dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kiri root. Kemudian karena disebelah kiri sudah ada daun dengan nilai 3 dan data 1 lebih kecil dari data 3 maka data 1 disisipkan disebelah kiri simpul 3. 
Langkah 5: Pemasukan data 4.
Langkah 6: Pemasukan data 6. Karena data 6 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan data 6 lebih kecil dari data 7 maka data 6 disisipkan disebelah kiri simpul 7. 
Langkah 7: Pemasukan data 8. Karena data 8 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan karena data 8 lebih besar dari data 7 maka data 8 disisipkan disebelah kanan simpul 7. 
Langkah 8: Pemasukan data 9. Karena data 9 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan bukan merupakan daun yaitu simpul dengan nilai 7 dan karena data 9 lebih besar dari data 7 penelusuran terus dilanjutkan kesebelah kanan. Selanjutnya ditemukan daun dengan nilai 8, karena data 9 lebih besar dari 8 maka data 9 disisipkan disebelah kanan simpul 8. 

Berikut adalah contoh implementasi Binary Search Tree pada C beserta searching datanya :
#include <stdio.h>
#include <stdlib.h>

//inisialisasi struct
struct data{
 int number;
 //pointer untuk menampung percabangan kiri dan kanan
 data *left, *right;
}*root;

//fungsi push untuk menambah data
void push(data **current, int number){
 //jika pointer current kosong maka akan membuat blok data baru
 if((*current)==NULL){
  (*current) = (struct data *)malloc(sizeof data);
  //mengisi data
  (*current)->number=number;
  (*current)->left = (*current)->right = NULL;
 //jika tidak kosong, maka akan dibandingkan apakah angka yang 
 //ingin dimasukkan lebih kecil dari pada root
 //kalau iya, maka belok ke kiri dan lakukan rekursif 
 //terus menerus hingga kosong
 }else if(number < (*current)->number){
  push(&(*current)->left, number);
 //jika lebih besar, belok ke kanan
 }else if(number >= (*current)->number){
  push(&(*current)->right, number);
 }
}

//preOrder : cetak, kiri, kanan
void preOrder(data **current){
 if((*current)!=NULL){
  printf("%d -> ", (*current)->number);
  preOrder(&(*current)->left);
  preOrder(&(*current)->right);
 }
}

//inOrder : kiri, cetak, kanan
void inOrder(data **current){
 if((*current)!=NULL){
  inOrder(&(*current)->left);
  printf("%d -> ", (*current)->number);
  inOrder(&(*current)->right);
 }
}

//postOrder : kiri, kanan, cetak
void postOrder(data **current){
 if((*current)!=NULL){
  postOrder(&(*current)->left);
  postOrder(&(*current)->right);
  printf("%d -> ", (*current)->number);
 }
}

//searching data
void search(data **current, int number){
 //jika pointer current memiliki data
 if((*current)!=NULL){
  //cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
  if(number<(*current)->number){
   search(&(*current)->left,number);
  //jika lebih besar, maka belok ke kanan
  }else if(number>(*current)->number){
   search(&(*current)->right,number);
  //jika sama dengan, maka angka ketemu
  }else{
   printf("Found : %d", (*current)->number);
  }
 //jika tidak ada data lagi (not found)
 }else{
  printf("Not Found.");
 }
}

void main(){
 push(&root, 11);
 push(&root, 22);
 push(&root, 13);
 push(&root, 15);
 push(&root, 9);
 inOrder(&root);
 printf("\n");
 preOrder(&root);
 printf("\n");
 postOrder(&root);
 printf("\n");
 search(&root,91);
 getchar();
}
Berikut adalah codingan saya saat melakukan latihan tentang Binary Search membuat sebuah program menu tentang insert data, search data, delete data, view data, exit & pop all data.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct data{
int value;
struct data *left,*right;
}*root;

struct data *tnode(int value){
struct data *newNode = (struct data*)malloc(sizeof(data));
newNode->left=NULL;
newNode->right=NULL;
newNode->value= value;
return newNode;
}

void insert(int value){
struct data *newNode = tnode(value);
if(root==NULL){
root= newNode;
}
else{
struct data *curr= root;
while(curr){
if(value < curr->value){
if(curr->left)curr=curr->left;
else{
curr->left=newNode;
break;
}
}
else{
if(curr->right)curr=curr->right;
else{
curr->right=newNode;
break;
}
}
}
}
}

void inOrder(struct data *curr){
if(curr){
inOrder(curr->left);
printf("%d ",curr->value);
inOrder(curr->right);
}
}

void postOrder(struct data *curr){
if(curr){
inOrder(curr->left);
inOrder(curr->right);
printf("%d ",curr->value);
}
}

void preOrder(struct data *curr){
if(curr){
printf("%d ",curr->value);
inOrder(curr->left);
inOrder(curr->right);
}
}

int search(int key){
if(root!=NULL){
struct data *curr= root;
while(curr){
if(curr->value==key){
return 1;
}
else if(key<curr->value)curr=curr->left;
else curr=curr->right;
}
return -1;
}
else{
return 0;
}
}

void deleteNode(struct data *curr, struct data *parent){
if(curr->left==NULL && curr->right==NULL){//KALO TIDAK ADA ANAK KIRI DAN KANAN
if(parent==NULL){
free(curr);
root=NULL;
}
else{
if(parent->left==curr){
parent->left=NULL;
}
else{
parent->right=NULL;
}
free(curr);
}
}
else if(curr->left!=NULL && curr->right==NULL){//PUNYA ANAK KIRI TIDAK PUNYA KANAN
if(parent==NULL){
root=curr->left;
}
else{
if(parent->left==curr){
parent->left=curr->left;
}
else{
parent->right=curr->left;
}
free(curr);
}
}
else if(curr->left==NULL && curr->right!=NULL){//PUNYA ANAK KANAN TIDAK PUNYA KIRI
if(parent==NULL){
root=curr->right;
}
else{
if(parent->left==curr){
parent->left=curr->right;
}
else{
parent->right=curr->right;
}
free(curr);
}
}
else{//PUNYA 2 ANAK KIRI KANAN
struct data *temp= curr;//BUAT NYIMPEN POINTER POSISI YANG MAU DIGANTI NILAINYA
struct data *parent2= curr;//BUAT NYIMPEN POINTER PARENT YANG MAU DIDELETE
curr=curr->left;
while(curr->right){//LOOP SAMPE KIRI TERBESAR
curr=curr->right;
}
int tempValue =curr->value;
deleteNode(curr,parent2);
temp->value= tempValue;
}
}

void searchDelete(int key){
if(root!=NULL){
struct data *curr=root;
struct data *parent= NULL;
while(curr){
if(curr->value==key)break;
parent =curr;
if(key<curr->value)curr=curr->left;
else curr=curr->right;
}
if(curr){
deleteNode(curr,parent);
}
else {
printf("Key not found\n");
}
}
else {
printf("No Data\n");
}
}

void popAll(){
while(root!=NULL){
searchDelete(root->value);
}
printf("Success pop ALL");
getchar();
}

int main(){
int menu,value,result,key;
do{
system("cls");
printf("LATIHAN BST\n");
printf("1.Insert Data\n");
printf("2.Search Data\n");
printf("3.Delete Data\n");
printf("4.View Data\n");
printf("5.Exit & PopAll\n");
printf("Choose : ");
scanf("%d",&menu);getchar();
switch(menu){
case 1:
printf("Input data: ");
scanf("%d",&value);getchar();
insert(value);
break;
case 2:
printf("Input key: ");
scanf("%d",&key);getchar();
result = search(key);
if(result ==1){
printf("Data Found");
}
else if(result==-1){
printf("Key Not Found");
}
else{
printf("No Data");
}
getchar();
break;
case 3:
printf("Input key to delete: ");
scanf("%d",&key);
searchDelete(key);
getchar();
break;
case 4:
inOrder(root);
printf("\nEnter to continue...");
getchar();
break;
case 5:
popAll();
}
}while (menu!=5);
return 0;
}


Referensi:
http://setyowahyudr.blogspot.com/2009/06/double-linked-list-circular.html






Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

-
Gambar
AVL TREE ---English Version--- Before we start to AVL Tree let's review Binary Search Tree (BST). Binary Search Tree This picture is the example of a skewed Binary Search Tree (BST). The left BST is inserted by 2, 5, 7, 8, and 13 respectively.  The right BST is inserted by 9, 1, 6, 3, and 4 respectively. AVL Tree AVL Tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one of all nodes. Height of a node: The height of an empty subtree is 0. The height of a leaf is 1. The height of an internal node is the maximum height of its children plus 1. Balance factor: The difference height of its LEFT subtree and its RIGHT subtree. The balance factor of all nodes in the AVL Tree should be at most 1. AVL Tree has two operations such as: 1. Insertion 2. Deletion AVL Tree Operation (Insertion) Look at the picture above, isn't it co...
Baca selengkapnya

Binary Search Tree

-
Gambar
Binary Tree Binary Tree adalah struktur data yang mirip dengan Linked List. Bila Linked List dianalogikan sebagai rantai yang linier maka Binary Tree dianalogikan sebagai pohon. Binary Tree dikelompokkan menjadi tree yang tidak berurut (unordered Binary Tree) dan tree yang terurut (ordered Binary Tree). Binary Tree dapat digambarkan berdasarkan kondisinya, yaitu:  Binary Search Tree (BST) merupakan tree yang terurut (ordered Binary Tree) yang memiliki kelebihan bila dibanding dengan struktur data lain. Diantaranya adalah proses pengurutan (sorting) dan pencarian (searching) dapat dilakukan bila data sudah tersusun dalam struktur data BST. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam  struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(...
Baca selengkapnya

Heaps dan Tries

-
Gambar
Heaps dan Tries Heap Heap adalah struktur data berbasis pohon biner lengkap yang memenuhi properti heap. Heap properti terbagi menjadi 3 bagian yaitu Min-Heap, Max-Heap, dan Min-Max Heap. Mari kita bahas satu persatu seperti dibawah ini: Aplikasi Heap Priority Queue Selection Algorithms (menemukan elemen min / maks, median, elemen kth-terbesar, dll). Dijkstra’s Algorithm (menemukan jalur terpendek dalam grafik) Prim Algorithm (menemukan minimum spanning tree) Heap Sort An O(n.lg(n)) algorithm. Implementasi Array  Heap biasanya diimplementasikan didalam array. Elemen-elemen nya tersimpan secara berurutan adri index 1 sampai N dari atas sampai bawah dan dari kiri ke kanan dari node of the tree . Root tersimpan dari index 1 (kita biarkan index 0 kosong/tidak terpakai, demi kenyamanan) Setiap hubungan node dengan orang tuanya, anak kiri dan anak kanan dalam implementasi array dapat dihitung dengan mudah. Biarkan indeks simpul saat ini menjadi x. I...
Baca selengkapnya