Binary Search Tree

Binary Search Tree merupakan struktur data pohon biner dengan menggunakan node. BST mempunyai ciri-ciri sebagai berikut :

•           Subtree sebelah kiri hanya berisi node yang memiliki key yang lebih kecil dari node itu sendiri
•           Subtree sebelah kanan hanya berisi node yang memiliki key yang lebih besar dari node itu sendiri
•           Subtree kiri kanan juga berupa BST
•           Tidak boleh ada node yang sama atau duplikat

Cara Searching key dalam Binary Search Tree adalah mencocokan key yang kita cari dengan key dalam root, jika key sesuai dengan root maka kita return root, jika key lebih kecil dari key dalam root, maka kita pindahkan pencarian ke subtree sebelah kiri, dan jika key lebih besar dari key dalam root, maka kita pindahkan pencarian ke subtree sebelah kanan.

Contoh dalam C :

struct node

{

    int key;

    struct node *left, *right;

};

   

struct node *newNode(int item)

{

    struct node *temp =  (struct node *)malloc(sizeof(struct node));

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

   

void inorder(struct node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        printf("%d \n", root->key);

        inorder(root->right);

    }

}

   

struct node* insert(struct node* node, int key)

{

    if (node == NULL) return newNode(key);

  

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);   

    return node;

}

   

int main()

{

    struct node *root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

   

    inorder(root);

   

    return 0;

}

Output :

20

30

40

50

60

70

80

Worst Case Time Complexity dari BST adalah O(n) dimana key yang kita cari ada di leaf paling bawah sehingga n adalah tinggi dari tree tersebut.

Single Linked List

Linked list merupakan sekumpulan node / data yang tersusun secara sekuensial,  saling menyambung dan dinamis. Linked list terbagi menjadi 3, single linked list, double linked list, dan circular linked list. Kali ini saya akan membahas tentang single linked list. Single linked list adalah linked list yang hanya mempunyai satu arah penunjuk, yaitu dari head ke tail. Kita tidak bisa menunjuk balik ke node sebelumnya jika kita sudah melewati node tersebut. Dalam linked list biasanya hanya ada 1 pointer penghubung yaitu next.

 Misalnya ada seorang pelamar kerja yang ingin menemui bos dari sebuah perusahaan. Saat datang ke gedung perusahaan tersebut, dia akan menemui resepsionis, lalu diarahkan ke sekretaris bos, dari sekretaris bos di cek apakah sudah ada janjinya, dan jika sudah baru bisa bertemu bos. Tapi dia tidak mungkin mencari sang resepsionis dan memulai pencariannya dari bertemu dengan bos perusahaan.

Contoh kodingannya adalah sebagai berikut :

struct node

 {

int data;

node *next;

}*head = NULL, *tail = NULL;

//PushHead

void pushHead( int data)

{

node *temp=(node*)malloc(sizeof(node));

temp->next=NULL;

temp->data=data;

if(!head)

{    

head==null

head=tail=temp;

}

else

{

temp->next=head;

head=temp;

}

}

//PushTail

void pushTail(int data)

{

node *temp=(node *)malloc(sizeof(node));

temp->next=NULL;

temp->data=data;

if(!head){

head=tail=temp;

}

else

{

(tail)->next = temp; 

tail=temp;

}

}

//pushMid

void pushMid( int data){

node *temp=(node*)malloc(sizeof(node));

node *curr=head;

temp->next=NULL;

temp->data=data;

if(!head)

{

*head=*tail=temp;

}

else

{

while (curr>next!=NULL) curr=curr>next;

temp->next=curr->next;

curr->next=temp;

if(curr==tail) tail=curr->next; 

}

}

Demikian adalah contoh untuk insert pada linked list.