• Implementasi Priority Queue

    Karena sifatnya itu maka struktur heaptree bermanfaat untuk mengimplementasikan priority queue. Sebagai suatu priority queue maka diperlukan spesifikasi abstraks dari heaptree:
     

    • heapify(CBT a)

    • metoda menginisialisasi suatu CBT a secara umum menjadi heaptree.
    • Key x = remove()

    • metoda mengambil mengambil data paling besar, yaitu root dari heaptree.
    • add(Key x)

    • metoda menambahkan satu key baru ke dalam heaptree.
    • reheapify()

    • metoda untuk menyusun ulang menjadi heaptree kembali setelah dilakukan remove/add.


    Kriteria yang penting untuk dipenuhi adalah bahwa setiap metoda di atas beroperasi pada tree yang selalu berbentuk CBT karena struktur level lebih rendahnya tetap merupakan suatu array.

    Algoritma Pengurutan Heapsort

    Contoh penggunaan heaptree dalam priority queue di dalam adalah dalam algoritma pengurutan Heapsort.  Algoritma pengurutan ini mengurutkan isi suatu array masukan a. Secara konseptual setiap array dapat dipandang sebagai suatu complete binary tree. Dengan metoda heapify maka complete binary tree ini dapat dikonversi menjadi suatu heaptree. Metoda add() tidak diperlukan dalam masalah ini. Setelah dilakukan heapify dan menjadi suatu suatu priority queue maka dengan mengambil data root satu demi satu disertai dengan proses reheapify maka key-key dari data root yang kita ambil secara berturutan itu akan terurut mengecil sampai habis jadi output dituliskan dalam array hasilnya dari kanan ke kiri.

    Karena setiap iterasi remove ukuran heaptree berkurang satu dan array hasilny bertambah satu maka untuk optimasi tempat masukan dan keluaran menempati array yang sama dan.operasi remove dimodifikasi sebagai operasi menukarkan isi root dengan elemen terakhir dalam heaptree (setelah penukaran maka elemen terakhir ini bukan lagi menjadi bagian dari heaptree.

    •
  •  
    Algoritma utamanya:

    heapify();
    for (i = 0; i < n; i++) {
       remove();
       reheapify();

    }

    Algoritma Metoda Heapify()
    Ide secara intuitif mungkin adalah melakukan operasi heapify ini dari root ke arah leaf. Namun ide ini tidak efisien dalam kenyataannya karena akan terjadi operasi rutun-naik mirip algoritma bubble-sort. Ide yang efisien adalah membentuk heaptree-heaptree mulai dari subtree-subtree yang paling bawah. Jika subtree-subtree suatu node sudah membentuk heap maka tree dari node tersebut mudah dijadikan heaptree dengana mengalirkannya ke bawah.

    Jadi algoritma utamanya beriterasi mulai dari internal node paling kanan-bawah (atau berindeks array paling besar) hingga root lalu ke kiri dan naik ke level di atasnya, dan seterusnya hingga root (sebagai array [0..N-1] maka iterasi dilakukan mulai j = N/2, berkurang satu-satu hingga j = 0.
     

    • pada internal node itu pemeriksaan hanya dilakukan pada node anaknya langsung (tidak pada level-level lain di bawahnya, mengapa?), dan
    • pada saat berada di level yang lebih tinggi, subtree-subtreenya selalu sudah membentuk heap. Jadi paling buruk restrukturisasi hanya mengalirkan node tersebut ke arah bawah.
    • Algoritma ini melakukan sebanyak N/2 kali iterasi, dan pada setiap interasi paling buruk akan melakukan pertukaran sebanyak log2(N) kali.


    Algoritma Metoda remove()

    • Algoritma hanya menukarkan elemen array[0] dengan elemen array terakhir dalam heaptree. Secara lojik node paling bawah-kanan dipindahkan ke root menggantikan node root yang akan diambil. Setelah reheapify panjang array yang menjadi bagian heaptree berkurang satu node dan elemen array ybs. digunakan untuk menyimpan hasil pengurutan hingga saat itu.


    Algoritma Metoda reheapify()

    • Melakukan restrukturisasi dari atas ke bawah seperti haalnya iterasi terakhir dari heapify() (karena baik subtree kiri maupun kanannya merupakan heap, jadi tidak perlu dilakukan seperti heapify).

    Contoh pada pengurutan dalam suatu array masukkan dengan data 11, 9, 8, 27, 16, 25, 12, 13, 34, 43. Array ini dapat dipandang sebagai suatu CBT sbb.
    sayang, anda harus menggunakan browser yang java 1.1.* enable.....
    Heapify dilakukan dengan iterasi dari subtree node ke 4, ke 3, dst. berturut-turut hingga root menghasilkan operasi-operasi penukaran sbb.

    • Subtree node ke 4: pertukaran 16 dengan 43
    • Subtree node ke 3: pertukaran 27 dengan 34
    • Subtree node ke 2: pertukaran 8 dengan 25
    • Subtree node ke 1: pertukaran 9 dengan 43, lalu 9 dengan 16
    • Subtree node ke 0: pertukaran 11 dengan 43, lalu 11 dengan 34, akhirnya 11 dengan 27

    perubahan-perubahan tersebut digambarkan sebagai berikut.
    sayang, anda harus menggunakan browser yang java 1.1.* enable..... sayang, anda harus menggunakan browser yang java 1.1.* enable..... sayang, anda harus menggunakan browser yang java 1.1.* enable..... sayang, anda harus menggunakan browser yang java 1.1.* enable..... sayang, anda harus menggunakan browser yang java 1.1.* enable.....
    Semua perubahan di atas terjadi dalam array ybs hingga diperoleh tree terakhir yang merupakan heaptree. Dalam iterasi yang melakukan remove() dan reheapify() maka akan terjadi:

    • Setelah 43 di remove dan 9 menggantikan 43 terjadi reheapify: penukaran 9 dengan 34, 9 dengan 27, dan 9 dengan 13:
      sayang, anda harus menggunakan browser yang java 1.1.* enable..... menjadi sayang, anda harus menggunakan browser yang java 1.1.* enable..... dan data yang telah terurut: 43
    • Setelah 34 di remove dan 11 menggantikan 34 terjadi reheapify: penukaran 11 dengan 27, 11 dengan 16:
      sayang, anda harus menggunakan browser yang java 1.1.* enable..... menjadi sayang, anda harus menggunakan browser yang java 1.1.* enable..... dan data yang telah terurut: 34, 43
    • Setelah 27 di remove dan 9 menggantikan 27 terjadi reheapify: penukaran 9 dengan 25, 9 dengan 12:
      sayang, anda harus menggunakan browser yang java 1.1.* enable..... menjadi sayang, anda harus menggunakan browser yang java 1.1.* enable..... dan data yang telah terurut: 27, 34, 43
    • Dan seterusnya anda dapat melanjutkannya sebagai latihan.

    Representasi Alokasi Dinamis

    Node-node saling berhubungan dengan pointer. Minimal digunakan dua pointer pada setiap node untuk menunjuk masing-masing ke cabang kiri dan cabang kanan. Dalam bahasa C misalnya dideklarasikan dengan: class BinaryTreeNode {
       KeyType Key;
       InfoType Info;
       BinaryTreeNode Left, Right;

        // metoda-metoda }

    •
  • left dan right berharga NULL apabila tidak ada lagi cabang pada arah yang bersangkutan. Beberapa varian dari struktur ini memanfaatkan pointer untuk menunjuk ke node pada suksesor/predesesornya dalam penelusuran inordernya.

    Struktur dari binary tree termasuk hubungan-hubungan antara node secara eksplisit direpresentasikan oleh left dan right. Bila diperlukan penelusuran  naik (backtrack) maka bisa dilakukan dengan

  • penelusuran ulang dari root, atau
  • penggunaan algoritma-algoritma rekursif, atau
  • penggunaan stack.
    •


    Alternatif lain, deklarasi ditambah dengan field ketiga untuk merefer node ayah tsb. namun hal ini berakibat bertambahnya jumlah tahapan pada proses-proses penambahan/penghapusan node.

    •

  • Traversal Binary Tree

    Traversal adalah proses menelusuri satu persatu elemen-elemen data pada struktur. Penelusuran ini tentunya disertai suatu proses tertentu pada node yang didatangi misalnya pencetakan, pencarian, komputasi, atau lain sebagainya. Proses-proses apa pun itu secara umum dapat kita sebut proses “mengunjungi”.

    Cara-cara Penelusuran
    penelusuran preorder:

    • pertama mengunjungi root dari tree (subtree) tersebut
    • kemudian secara rekursif penelusuran preorder node-node subtree kiri
    • dan secara rekursif penelusuran preorder node-node subtree kanan.


    penelusuran postorder:

    • pertama secara rekursif penelusuran postorder node-node subtree kiri,
    • kemudian secara rekursif penelusuran postorder node-node subtree kanan,
    • dan mengunjungi root dari tree (subtree) tersebut.


    penelusuran inorder:

    • pertama secara rekursif penelusuran preorder node-node subtree kiri
    • kemudian mengunjungi root dari tree (subtree) tersebut
    • dan secara rekursif penelusuran preorder node-node subtree kanan.

    Contoh pada binary tree berikut ini dilakukan traversal:
    sayang, anda harus menggunakan browser yang java 1.1.* enable.....

    • Preorder traversal menghasilkan urutan: z, a, f, l, n, w, t, u, d, s, v, h, m
    • Inorder traversal menghasilkan urutan: f, a, n, l, t, w, u, z, s, h, v, d, m
    • postorder traversal menghasilkan urutan: f, n, t, u, w, l, a, h, v, s, m, d, z

    Perbedaan penelusuran ini dapat dimanfaatkan untuk konversi infix ke postfix ekspresi matematis. Contoh: (a+b) * ((d + e - f) / g) sebagai notasi infix digambarkan dalam represetnasi tree sbb.
    sayang, anda harus menggunakan browser yang java 1.1.* enable.....
    Postorder traversal pada tree akan menghasilkan ekspresi postfixnya:

  • a b + d e + f - g / *


    • Implementasi
    Pada repr. Alokasi Dinamis

    preOrder() {

  • visit();
    if (left != NULL) left.preOrder();
    if (right != NULL) right.preOrder();
    •

    }

    postOrder() {

  • if (left != NULL) left.preOrder();
    if (right != NULL) right.preOrder();
    visit();
    •

    }

    inOrder() {

  • if (left != NULL) left.preOrder();
    visit();
    if (right != NULL) right.preOrder();
    •

    }
     

    Dari metoda-metoda penelusuran ini diperoleh terminologi baru:
     

    • suksesor inorder node atau key tepat berikutnya jika ditelusuri secara inorder
    • predesesor inorder node atau key tepat sebelumnya jika ditelusuri secara inorder
    • suksesor preorder node atau key tepat berikutnya jika ditelusuri secara preorder
    • predesesor preorder node atau key tepat sebelumnya jika ditelusuri secara preorder
    • suksesor postorder node atau key tepat berikutnya jika ditelusuri secara postorder
    • predesesor postorder node atau key tepat sebelumnya jika ditelusuri secara postorder
    •
  • Bagaimana caranya traversal pada representasi sikuensial?

    • Handout berikutnya, atau sebelumnya, atau kembali ke halaman utama

    •