Binary Search Tree

Binary search tree adalah salah satu struktur data yang faster searching, rapid sorting, and easy insertion and deletion. Binary search tree juga dikenal sebagai versi binary tree yang disort.

Aturan pada 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.

Binary search tree memiliki beberapa basic operator - find(x): mencari kunci x pada binary search tree - remove(x): mendelete kunci x pada binary search tree - insert(x): memasukkan kunci baru pada binary search tree

INSERTION OPERATION

---

Dimulai dari root. jika x kurang dari node maka insert x ke sub tree, atau masukkan x ke sub tree kanan ulang terus sampai menemukan empty node untuk meletakkan X (X akan selalu menjadi leaf baru)

DELETION

---

jika key hanya leaf tinggal delete saja nodenya

jika key memiliki 1 child delete node dan connect child ke parentnya

Jika key ada dinode yang memiliki dua child, temukan child paling kanan dari sub tree kirinya (simpul P), ganti kuncinya dengan kunci P dan hapus P secara rekursif. (atau secara bergantian Anda dapat memilih anak paling kiri dari sub tree kanannya)

nama: Antonio Michael Kurniawan

NIM : 2301924063