Sebelum membahas Binary Search Tree (BST), mari kita pahami dahulu definisi dari tree.
Tree adalah data structure dengan aturan:
- Sebuah tree hanya memiliki 1 root node.
- Setiap node dapat memiliki child >= 0.
- Setiap node hanya memiliki 1 parent, kecuali root.
- Setiap node tidak dapat menjadi parent terhadap dirinya sendiri.
Beberapa Fitur Tree (optional):
- Setiap node dari tree umumnya akan dikaitkan dengan data, contoh tree directory akan berisi folder dan file.
- Memiliki aturan berapa children yang bisa dimiliki.
- Memiliki aturan bagaimana node terhubung berdasarkan data yang dimiliki.
Binary Search Tree (BST)
BST memiliki aturan seperti berikut:
- Setiap node hanya memiliki maksimal 2 children, kiri (left) dan kanan (right).
- Setiap node memiliki nilai numeric.
- Nilai dari left children harus lebih kecil dari parentnya.
- Nilai dari right children harus lebih besar dari parentnya.
- Tidak memiliki duplikat value.
Jika Anda perhatikan gambar diatas pada bagian BST Numeric Order, dapat dilihat, jika kita sisir tree dari kiri ke kanan, maka menjadi urutan angka dengan nilai ascending.