5 - binary search tree - 2101656755 - Wantika Aprilia Wangke

Selamat datang di pertemuan ke-lima dengan topik Binary Search three

Binary Search Tree sendiri adalah tree yang dipergunakan untuk memudahkan dan mempercepat komputer dalam melakukan perncarian suatu data.

Sub Topics

- Operations: Search, Insertion, Deletion

- Program Example

- Expression Tree Concept

- Create Exp. Tree from prefix

- Create Exp. Tree from postfix

- Create Exp. Tree from Infix

- Prefix, Postfix, Infix Traversal

 

1.  Operations

Binary search tree memiliki beberapa basic operation:
- find(x) = search / cari "x" BST
- insert(x)= push / masukkan '"x" ke dalam BST
- remove(x) = pop / hapus "x" dari BST
 

Search:

 

Pencarian (Searching) dimulai dari rootnya (di gambar adalah angka 50). Jika angka yang dicari belum ditemukan, maka pencarian akan dilanjutkan, jika angka yang dicari lebih kecil dari root, maka pencarian akan ke sebelah kiri root, jika sebaliknya maka akan dicari ke sebelah kanan root. Begitu seterusnya samapi ditemukan angka yang dicari.
Misal jika angka yang dicari adalah 23, maka pencarian akan dimulai dari:

• 23 != root, maka 23 dibandingkan dengan root
• 23 < 50, maka pencarian dilanjutkan ke sebelah kiri
• 23 != 17, maka 23 dibandingkan dengan 17
• 23 > 17, maka pencarian dilanjutkan ke sebelah kanan
• 23 == 23, maka pencarian telah berhasil dan selesa

Insertion

Data yang lebih kecil daripada root / parent, diletakan di sebelah kiri.

Data yang lebih besar daripada root / parent  diletakan disebelah kanan.

contoh:

insert 35 kedalam BST. Maka 35 akan diletakan di sebelah kanan 32.

 

Deletion

 

Ada 3 cases yang harus diperhatikan:

-       Jika kuncinya adalah leaf, hapus saja nodenya

-        Jika kuncinya adalah node yang hanya mempunyai satu anak, hapus nodenya dan konek anaknya kepada orangtuanya.

-        Jika kuncinya adalah node mempunyai dua anak, temukan anak yang paling benar yang mempunyai sub tree disebelah kiri, gantikan kuncinya dengan kunci P’s dan hapus P secara recursive.

Demikian blog hari ini trima kasih!