Pohon Pengurutan Biner (Struktur Data Berantai-Java)

Pada bagian sebelumnya kita membahas tentang list berantai dari string, di mana string dijaga agar tetap dalam urutan menaik. Akan tetapi list berantai seperti ini bisa bekerja untuk jumlah yang tidak terlalu banyak. Untuk jumlah item yang sangat banyak, list berantai kurang efisien. Ketika kita menambahkan item ke dalam list, kita harus mencari dahulu posisi yang tepat di mana item akan disisipkan. Untuk melakukan pencarian, kita harus melihat paling tidak separuh dari seluruh list.

Jika string list diimplentasikan dalam bentuk array terurut, maka pencariannya bisa dilakukan lebih cepat, karena pencarian binerbisa digunakan. Akan tetapi untuk menyisipkan item ke dalam array terurut juga tidak efisien, karena kita harus memindahkan paling tidak setengah isi array untuk memberi tempat untuk item baru yang akan disisipkan.

Pohon biner bisa digunakan untuk menyimpan string list terurut (atau item jenis lain), sehingga pencarian dan penyisipan bisa dilakukan dengan mudah. Pohon biner ini disebut pohon pencarian biner.

Pohon pencarian biner adalah pohon biner yang memiliki sifat :
- Untuk setiap simpul pada pohon, item pada simpul tersebut lebih besar dari semua item di cabang kiri  pohon
- Dan simpul tersebut, lebih besar atau sama dengan semua item di cabang kanan pohon.

Berikut ini adalah contoh pohon pengurutan biner yang memiliki item bertipe String. (Dalam gambar ini pointer berisi null tidak digambarkan, sedangkan pointer yang tidak null dilambangkan dengan tanda panah)

Pohon pencarian biner memiliki sifat penting berikut : Penelusuran inorder akan mengolah item dalam urutan menaik. Misalnya, penelusuran inorder digunakan untuk mencetak isi pohon di atas dalam urutan alfabet. Penelusuran inorder menjamin bahwa semua item di cabang kiri pohon dari elemen "judy" akan dicetak sebelum "judy", dan semua item di cabang kanan pohon akan dicetak setelah "judy". Karena sifat pohon biner yang mengharuskan item di cabang kiri lebih kecil dari item pada simpul, maka keluarannya akan sama dengan mengurutkan isi pohon secara alfabet dalam urutan menaik.

Misalnya kita ingin mencari item di dalam pohon pencari biner. Pertama, bandingkan item dengan isi simpul akarnya. Jika isinya sama, maka kita selesai. Jika item yang kita cari kurang dari item pada simpul akar, kita harus mencari ke sebelah kiri pohon -- pohon sebelah kanan bisa diabaikan karena isinya hanya item yang lebih besar dari simpul akarnya. Demikian juga jika item yang kita cari lebih besar dari item pada simpul akar, maka kita akan mencari di sebelah kanan pohon. Untuk semua kasus, kita bisa menggunakan prosedur yang sama di setiap cabang pohon.

Bagaimana dengan memasukkan item baru ke dalam pohon. Mula-mula cari di posisi mana item tersebut akan dimasukkan. Jika posisinya ditemukan, buat simpul baru dan tempelkan simpul baru di tempat tersebut.

Pencarian dan penyisipan item adalah operasi yang efisien pada pohon pencarian biner, asalkan pohon tersebut berada dalam kondisi seimbang (balanced). Suatu pohon biner berada dalam kondisi seimbang jika jumlah simpul pada cabang kanan sama dengan jumlah simpul pada cabang kiri. Tidak semua pohon biner akan menjadi pohon seimbang, akan tetapi jika pohon ini dibuat secara acak, besar kemungkinan pohon tersebut akan menjadi seimbang.

Dalam pencarian dalam pohon pencarian biner, setiap pengujian yang kita lakukan akan membuang sebagian cabang pohon. Jika pohon tersebut dalam keadaan seimbang, maka akan semakin banyak elemen yang kita buang, dan dengan demikian pencarian akan dilakukan dengan lebih cepat. Ini mirip sekali dengan algoritma pencarian biner pada bagian sebelumnya.

Mari kita lihat bagaimana mengimplementasikan pohon pencarian biner.

Simpul pada pohon biner diekspresikan dalam kelas SimpulPohon berikut ini, beserta konstruktor untuk membuat simpul baru lebih mudah.

class SimpulPohon {
    // Objek SimpulPohon adalah satu simpul pada
    // pohon biner string
 
    String item;      // Data pada simpul ini
    SimpulPohon kiri;    // Pointer ke cabang kiri
    SimpulPohon kanan;   // Pointer ke cabang kanan
 
    SimpulPohon(String str) {
        // Konstruktor. Membuat simpul berisi str
        item = str;
    }
}  // akhir kelas SimpulPohon

Variabel statik dengan tipe SimpulPohon menunjuk pada pohon pencarian biner:

// Pointer ke simpul akar pohon
// Ketika pohon kosong, akar berisi null
static SimpulPohon akar;  

Subrutin rekursif bernama pohonBerisi digunakan untuk mencari item di dalam pohon. Subruin berikut melakukan pencarian pada pohon biner seperti didiskusikan di atas.

static boolean pohonBerisi( SimpulPohon simpul, String item ) {
    // Kembalikan true jika item ditemukan dalam pohon 
    if ( simpul == null ) {
        // Pohon kosong, jadi sudah pasti tidak ada item ini
        // di dalamnya
        return false;
    }
    else if ( item.equals(simpul.item) ) {
        // Item ini ditemukan di simpul akar
        return true;
    }
    else if ( item.compareTo(simpul.item) < 0 ) {
        // Jika item lebih kecil dari simpul, maka mungkin ada di
        // cabang kiri pohon. Kembalikan hasil pencarian di
        // cabang kiri pohon
        return pohonBerisi( simpul.kiri, item );
    }
    else {
        // Jika item sama atau lebih besar dari simpul, maka 
        // mungkin ada di cabang kanan pohon. Kembalikan hasil
        // pencarian di cabang kanan pohon
        return pohonBerisi( simpul.kanan, item );
    }
}  // akhir pohonBerisi()

Ketika subrutin ini dipanggil, parameter pertama adalah variabel anggota statik akar yang menunjuk pada akar seluruh pohonh pencarian biner.

Perlu dicatat bahwa rekursi bukan sesuatu yang penting dalam mengimplementasikan subrutin ini. Algoritma pohon pencarian biner yang tidak rekursif mengikuti aturan berikut : Turun ke bawah hingga kita menemukan item atau hingga mencapai null. Kita bisa menggunakan perulangan while, sehingga implementasinya menjadi :

static boolean pohonBerisiNR( SimpulPohon akar, String item ) {
    // Kembalikan true jika item ada di dalam pohon biner.
    SimpulPohon pointer;  // Pointer untuk menelusuri pohon
    pointer = akar;    // Mulai di akar simpul
    while (true) {
        if (pointer == null) {
            // Kita sudah sampai pada akhir pohon, dan item belum
            // ditemukan
            return false;
        }
        else if ( item.equals(pointer.item) ) {
            // Kita sudah menemukan item
            return true;
        }
        else if ( item.compareTo(pointer.item) < 0 ) {
            // Jika item lebih kecil, kemungkinan ada di cabang kiri
            // Teruskan penelusuran di cabang kiri pohon
            pointer = pointer.kiri;
        }
        else {
            // Jika item lebih besar, kemungkinan ada di cabang kanan
            // Teruskan penelusuran di cabang kanan pohon
            pointer = pointer.kanan;
        }
    }  // akhir while
} // akhir pohonBerisiNR();

Subrutin untuk menyisipkan item baru ke dalam pohon mirip dengan rutin pencari non-rekursif di atas. Selain itu rutin penyisipan harus bisa menguji apakah pohon kosong atau tidak. Jika pohon kosong, maka akar menunjuk pada simpul baru.

akar = new simpulPohon( itemBaru );

Akan tetapi, berarti akar tidak bisa diberikan sebagai parameter subrutin, karena kita tidak bisa mengubah nilai yang disimpan dalam parameter aktual. (Ini bisa dilakukan dalam bahasa pemrograman lain). Ada cari lainnya, akan tetapi cara lebih mudah adalah menggunakan rutin penyisipan non-rekursif yang mengakses variabel anggota akar secara langsung.

Perbedaan antara mencari dan menyisipkan item adalah kita harus berhati-hati untuk tidak jatuh dari pohon. ARtinya, kita harus selesai melakukan pencarian sebelum pointer bernilai null karena mencapai akhir pohon. Jika kita sampai pada tempat kosong, di situlah kita menempatkan simpul baru kita.

static void sisipPohon(String itemBaru) {
    // Tambahkan item ke dalam pohon pencarian biner, di mana
    // variabel "akar" berisi. (Catatan kita tidak bisa menggunakan
    // akar sebagai parameter, karena kita harus mengubah isi
    // variabel ini.)
    if ( akar == null ) {
        // Jika pohon kosong, set akar ke simpul baru
        // yang berisi itemBaru
        akar = new SimpulPohon( itemBaru );
        return;
    }
    SimpulPohon pointer; // Untuk menelusuri pohon
    pointer = akar;   // Mulai dari akar
    while (true) {
        if ( newItem.compareTo(pointer.item) < 0 ) {
            // Karena itemBaru kurang dari item dalam pohon
            // maka ia harus berada di cabang kiri pohon.
            // Jika ada ruang kosong di pointer.kiri maka simpul baru
            // bisa ditambah di sini. Jika tidak turun satu tingkat lagi ke kiri
            if ( pointer.kiri == null ) {
                pointer.kiri = new SimpulPohon( itemBaru );
                return;  // itemBaru sudah ditambahkan ke dalam pohon
            }
            else
                pointer = pointer.kiri;
        }
        else {
            // Karena itemBaru lebih besar dari item dalam pohon
            // maka ia harus berada di cabang kanan pohon.
            // Jika ada ruang kosong di pointer.kanan maka simpul baru
            // bisa ditambah di sini. Jika tidak turun satu tingkat lagi ke kanan
            if ( pointer.kanan == null ) {
                pointer.kanan = new SimpulPohon( itemBaru );
                return;  // itemBaru sudah ditambahkan ke dalam pohon
            }
            else
                pointer = pointer.kanan;
        }
    } // akhir while
}  // akhir sisipPohon()