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

3 - Linked List Implementation II - 2101637541 - Vick Koesoemo Santoso

Gambar
3 - Linked List Implementation II - 2101637541 - Vick Koesoemo Santoso Stack Concept Stack merupakan data struktur yang penting yang menyimpan elementnya secara teratur. Analogi : Seperti tumpukan piring dimana jika kita ingin mengambil piring maka kita harus mengambilnya dari yang paling atas. Ø   Stack adalah linear data struktur yang bisa diimplementasikan dengan array atau linked list Ø   Element dalam stack bisa ditambah atau dikurangkan dari data yang paling akhir yang biasa disebut “Top” Ø   Data tersebut disimpan dalam konsep (LIFO) Last In First Out. Array Representation Stack punya 2 variable : Ø   TOP digunakan untuk menyimpan alamat element paling atas dari Stack Ø   MAX digunakan untuk menyimpan data maksimal yang bisa ditampung oleh Stack Ø   Jika TOP = NULL maka data dalam Stack kosong Ø   Jika TOP = Max-1, maka data dalam Stack penuh Yang membedakan Array dengan Linked list , didalam array kita harus meme...
Baca selengkapnya

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...
Baca selengkapnya