Binary Search Tree
Pengertian
binary search tree (BST) atau yang terkadang disebut juga sebagai sorted binary tree, merupakan semacam container struktur data, yang menyimpan informasi seperti bilangan atau nama yang ada di dalam memory. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.
Binary search tree menempatkan key tersebut secara urut, yang memungkinkan pencarian dengan cara binary search. Binary tree terdiri dari node utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut.
Aturan Dalam Membangun BST
Agar data benar-benar tersusun dalam struktur data BST, dua aturan yang
harus dipenuhi pada saat data diatur dalam BST adalah sebagai berikut:
- Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.
- Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.
BST berikut adalah sebuah BST berukuran 9 dengan kedalaman 3 dengan
node daun (leaf) adalah 1, 4, 7 dan 13.
daftar pustaka :
Contoh Aplikasi BST
- Membangun daftar vocabulary yang merupakan bagian dari inverted index (sebuah struktur data yang digunakan oleh banyak mesin pencari seperti Google.com, Yahoo.com dan Ask.com)
- Banyak digunakan dalam bahasa pemrograman untuk mengelola dan membangun dynamic sets.
Contoh Implementasi BST
Comments
Post a Comment