Binary Search Tree (BST)

Binary Search Tree (BST)

Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya, Berarti, binary tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja, berikut contoh Binary tree :

Binary Search Tree (BST) adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node, Tujuan struktur BST untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat berikut contoh Binary search tree :

Aturan main Binary Search Tree :

-        Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.

-        Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :

-        PreOrder : Print data, telusur ke kiri, telusur ke kanan

-        InOrder : Telusur ke kiri, print data, telusur ke kanan

-        Post Order : Telusur ke kiri, telusur ke kanan, print data