• Document: Struktur Data dan Algoritma
  • Size: 981.38 KB
  • Uploaded: 2019-04-15 21:47:27
  • Status: Successfully converted


Some snippets from your converted document:

Struktur Data dan Algoritma Binary Search Tree Suryana Setiawan, Ruli Manurung & Ade Azurat (acknowledgments: Denny)‫‏‬ Fasilkom UI SUR – HMM – AA Fasilkom UI - IKI20100/ IKI80110P 2009/2010 – Ganjil – Minggu 9 Tujuan  Memahami sifat dari Binary Search Tree (BST)‫‏‬  Memahami operasi-operasi pada BST  Memahami kelebihan dan kekurangan dari BST SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 2 Outline  Properties of Binary Search Tree (BST)‫‏‬  Operation  Insert  find  remove SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 3 Properties of Binary Search Tree  Untuk setiap node X pada tree, nilai elemen pada subtree sebelah kiri selalu lebih kecil dari elemen node X dan nilai elemen pada subtree sebelah kanan selalu lebih besar dari elemen node X.  Jadi object elemen harus comparable. X <X >X SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 4 Binary Search Tree 7 2 1 5 6 3 9 SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 5 Binary Search Tree 7 9 2 1 5 3 6 SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 6 Binary Search Tree 3 3 1 1 2 1 2 3 3 1 2 2 2 1 3 SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 7 Basic Operations  insert  findMin and findMax  remove  cetak terurut SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 8 Print InOrder class BinaryNode { void printInOrder( )‫‏‬ { if( left != null )‫‏‬ left.printInOrder( ); // Left System.out.println( element ); // Node if( right != null )‫‏‬ right.printInOrder( ); // Right } } class BinaryTree { public void printInOrder( )‫‏‬ { if( root != null )‫‏‬ root.printInOrder( ); } } SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 9 Insertion  Penyisipan sebuah elemen baru dalam binary search tree, elemen tersebut pasti akan menjadi leaf 10 15 2 1 5 12 3 6 14 SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 10 Insertion: algorithm  Menambah elemen X pada binary search tree:  mulai dari root.  Jika X lebih kecil dari root, maka X harus diletakkan pada sub-tree sebelah kiri.  jika X lebih besar dari root, then X harus diletakkan pada sub-tree sebelah kanan.  Ingat bahwa: sebuah sub tree adalah juga sebuah tree. Maka, proses penambahan elemen pada sub tree adalah sama dengan penambahan pada seluruh tree. (melalui root tadi)  Apa hubungannya?  permasalahan ini cocok diselesaikan secara rekursif. SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 11 Insertion BinaryNode insert(int x, BinaryNode t) { if (t == null) { t = new BinaryNode (x, null, null); } else if (x < t.element) { t.left = insert (x, t.left); } else if (x > t.element) { t.right = insert (x, t.right); } else { throw new DuplicateItem(“exception”); } return t; } SUR – HMM – AA Fasilkom UI – IKI20100/IKI80110P 2009/2010 – Ganjil – Minggu 9 12 FindMin  Mencari node yang memiliki nilai terkecil.  Algorithm:  ke kiri terus sampai buntu….:)‫‏‬  Code: BinaryNode findMin (BinaryNode t) { if (t == null) throw exception; while (t.left != null) { t = t.left; } return t; } SUR – HMM – AA Fasilkom UI –

Recently converted files (publicly available):