MORENO

Definition

Binary search tree adalah sebuah struktur data yang memungkinkan pencarian cepat, penyortiran cepat, serta penyisipan dan penghapusan data yang mudah.

Binary serach tree (BST) juga dikenal sebagai sorted version of binary tree atau versi binary tree yang terurut.

Aturan node pada BST :

• Tangan kanan pada node akan menunjuk ke anak node dengan key lebih besar dari dia
• Tangan kiri  pada node akan menunjuk ke anak node dengan key lebih kecil dari dia

BST Operations

BST memiliki 3 operasi dasar:

• search( ) : untuk mencari key tertentu dalam BST
• insert( ) : untuk memasukkan key baru ke dalam BST
• remove( ) :  untuk menghilangkan key tertentu dalam BST

Seacrh Operation

Operasi search dilakukan mulai dari root (node pertama). Jika root adalah node yang dicari maka operasi search selesai. Jika tidak, maka cek key dari node yang dicari apakah lebih besar atau lebih kecil dari root. Bila key yang dicari lebih kecil, maka search dilakukan secara rekursif pada sub-tree sebelah kiri dan kebalikannya jika key lebih besar.

Insert Operation

Operasi insert dilakukan mulai dari root (node pertama). Node baru akan dimasukkan pada leaf (bagian dari tree yang belum memiliki child node sama sekali) dan menjadi leaf baru. Jika key dari node baru tersebut lebih kecil dari root maka dia akan melakukan rekursif hingga menemukan leaf pada sub-tree sebelah kiri. Berlaku kebalikan jika key dari node baru lebih besar dari root.

Delete Operation

Operasi delete sedikit lebih rumit daripada operasi search dan insert. Dalam operasi delete kita harus memperhatikan 3 kondisi:

• Jika key yang ingin dihapus ada pada leaf, langsung hapus node tersebut
• Jika key yang indin dihapus memiliki 1 child node, maka child node tersebut harus menggantikan posisi parent node yang akan dihapus.
• Jika key yang ingin dihapus memiliki 2 child node, maka pilih salah satu cara untuk menggantikan node tersebut. Cara pertama adalah dengan memilih node paling kanan dari sub-tree sebelah kiri, cara kedua adalah dengan memilih node paling kiri dari sub-tree sebelah kanan.