5 - Binary Search Tree - 2101637541 - Vick Koesoemo Santoso


5 - Binary Search Tree - 2101637541 - Vick Koesoemo Santoso

* BST = Binary Search Tree

Binary Search Tree Operations

·       Binary Search Tree memiliki operasi dasar sebagai berikut:
–     find(a)           : menemukan data a di BST
–     insert(a)        : Memasukkan data a ke BST
–     remove(a)     : Menghapus data a dari BST

Operations: Search
·       Karena konsep dari BST, menemukan/mencari di BST sangat mudah.
·       Misalkan data yang kita ingin cari adalah a.
Ø  Kita mulai dari root
Ø  Jika root memuat maka a , maka a berhasil ditemukan
Ø  Jika a lebih kecil dari root maka lakukan pencarian secara rekursif di kiri sub tree, sebaliknya jika a lebih besar dari root maka lakukan pencarian secara rekrusif di kanan subtree.
Algorithm Search:
struct node* search (struct data *curr, int a) {
  if ( curr == NULL ) return NULL;
  // a is found
  if ( X == curr->data ) return curr;
  // a is located in left sub tree
  if ( X  < curr->data ) return find(curr->left, a);
  // a is located in right sub tree
  return find(curr->right, X);
}

Operations: Insertion
·       Memasukkan data ke BST dilakukan secara rekursif.
·       Jika a lebih kecil dari nilai node, maka masukkan a ke dalam kiri sub tree, sebaliknya masukkan a kedalam kanan sub tree.
·       Lakukan terus sampai sama kita menemukan node kosong untuk memasukkan nilai a(a selalu menjadi leaf baru).
Algorithm Insertion:
Step 1:         IF TREE = NULL, then 
                              Allocate memory for TREE
                              SET TREE->DATA = VAL
                    SET TREE->LEFT = TREE ->RIGHT = NULL
          ELSE
                    IF VAL < TREE->DATA
                                        Insert(TREE->LEFT, VAL)
                    ELSE
                                        Insert(TREE->RIGHT, VAL)
                    [END OF IF]
          [END OF IF]
Step 2: End



Operations: Deletion
Ada 3 kasus yang harus dipertimbangkan :
•        Jika data tersebut di leaf maka, langsung hapus node tersebut
•        Jika data didalam node tersebut memiliki 1 child, hapus node tersebut dan sambungkan node si child dengan node si parent.
•        Jika data didalam node memiliki 2 child temukan anak paling kanan di kiri sub tree(node S) ganti data tersebut dengan dengan data S dan hapus node P secara rekursif.(atau kalian bisa memilih node paling kiri di kanan sub tree).
Algorithm:
Step 1: IF TREE = NULL, then 
               Write “VAL not found in the tree”
        ELSE IF VAL < TREE->DATA
               Delete(TREE->LEFT, VAL)
        ELSE IF VAL > TREE->DATA
               Delete(TREE->RIGHT, VAL)
        ELSE IF TREE->LEFT AND TREE->RIGHT
               SET TEMP = findLargestNode(TREE->LEFT)
               SET TREE->DATA = TEMP->DATA
               Delete(TREE->LEFT, TEMP->DATA)
Algorithm:
ELSE
     SET TEMP = TREE
     IF TREE->LEFT = NULL AND TREE ->RIGHT = NULL
               SET TREE = NULL
     ELSE IF TREE->LEFT != NULL
               SET TREE = TREE->LEFT
     ELSE
               SET TREE = TREE->RIGHT
     FREE TEMP
Step 2: End


Vick Koesoemo Santoso
2101637541

Komentar

Posting Komentar

Postingan populer dari blog ini

4 - Introduction to Tree, Binary Tree And Expression Tree - 2101637541 - Vick Koesoemo Santoso

Gambar
4 - Introduction to Tree, Binary Tree And Expression Tree - 2101637541 - Vick Koesoemo Santoso  Tree Concept Tree adalah Kumpulan kumpulan dari satu atau lebih nodes. ·        Node yang diatas disebut root . ·        Garis yang menghubungkan parent dengan childnya disebut edge . ·        Node yang tidak mempunyai children disebut leaf . ·        Nodes yang mempunyai parent yang sama disebut sibling . ·        Degree adalah total subtree dari node. ·        Height/Depth adalah maksimal degree dari nodes dalam sebuah tree. ·        Jika ada garis yang menghubungkan a dengan b, maka a disebut ancestor dari b, dan b disebut descendant dari a. Degree dari Tree = 4 Degree dari Nick = 3 Height = 4 Parent dari John = Bob Children dari Bob = Mary, John, Joe Sibling dari Sama = Jo Ancestor dari Nick = Joe dan Bob Descendant dari Mary = Beth dan James Binary Tree Concept ·        Binary tree adalah struktur data pohon berakar di mana s
Baca selengkapnya

2 - Linked List Implementation I - 2101637541 - Vick Koesoemo Santoso

Gambar
2 - Linked List Implementation I  - 2101637541 - Vick Koesoemo Santoso Single Linked List Single linked list adalah sekumpulan node yang terhubung ke node lain melalui pointer. Single linked list Insert (PushHead) = jika kita ingin memasukkan node baru dari depan struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode)); node->value = x; node->next   = head; head = node; Single linked list delete // if x is in head node if ( head->value == x ) {           head = head->next;           free(curr); } // if x is in tail node else if(tail->value == x){           while(curr->next!=tail) curr = curr->next;           free(tail); tail = curr;           tail->next = NULL; } // if x is not in head node, find the location else {           while ( curr->next->value != x ) curr = curr->next;           struct tnode *del = curr->next;           curr->next = del->next;           fre
Baca selengkapnya