Binary Search Tree

Nama : Sofyan Adrianto

NIM : 2301869121

Jurusan : TI dan Statistika

Binary Search Tree

hari selasa saya belajar dari pak Henry Chong,dan beberapa tambahan dari internet:

Konsep binary tree dengan binary search tree yang kita pelajari minggu lalu pada dasarnya sama,selama dia ada kata binary,artinya kakinya ada 2,bi artinya 2.Ternary artinya 3 kaki, ada yang namanya ternary tree, yang kakinya 4 juga ada.

Apa bedanya binary tree sama binary search tree?

kakinya sama yaitu, di binary search tree ada kata search tree yang berarti mencari pohon.Kalo di Binary Tree gaad aturan penempatan,semua bebas taro mana aja(gaharus sebelah kiri lebih kecil,dan disebelah kanan harus lebih besar). Kalo di Binary search tree ada aturannya. Aturan yang biasa dipakai di binary search tree yaitu :

1. Sebelah kiri lebih kecil dari parentnya.

2. Sebelah kanan lebih besar dari parentnya.

Kalo di beberapa buku(biasanya buku lama) ketemu sebelah kanan lebih kecil, kiri lebih besar. Itu sama aj,konsepnya sama, yang penting konsisten.

Ada beberapa fungsi:

1. Find

untuk mencari tree

dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.

Bayangkan kita akan mencari value X.

• Memulai Pencarian Dari Root
• Jika Root adalah value yang kita cari , maka berhenti
• Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
• Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan

2. Insert

Biasanya kita mengenal insert dengan fungsi "push" untuk memasukkan data.

Operasi: Insertion BST

Memasukan value (data) baru kedalam BST dengan rekrusif

Bayangkan kita menginsert value x :

• Dimulai dari root
• jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
• jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
• Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )

3. Delete

Biasanya kita mengenal delete dengan fungsi "pop" untuk membuang data.

akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :

• Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
• Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
• jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan) atau dengan cari dari right sub-tree anak kiri paling terakhir(leaf) (kanan,kiri).

Binary Search Tree: proses pencarian (SEARCHING) berbasis binary tree

Tree traversal adalah cara kunjungan node-node pada pohon biner. Ada tiga cara

kunjungan dalam tree:

• Pre-order

• In-order

• Post-order

1. Pre-order

a. Cetak data pada root

b. Secara rekursif mencetak seluruh data pada subpohon kiri

c. Secara rekursif mencetak seluruh data pada subpohon kanan

2. In-order

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Cetak data pada root

c. Secara rekursif mencetak seluruh data pada subpohon kanan

3. Post-order

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Secara rekursif mencetak seluruh data pada subpohon kanan

c. Cetak data pada root