Binary Search Tree
- Ryan Frederick Muliawan
- Mar 21, 2020
- 1 min read
Binary Search Tree merupakan sebuah binary tree dalam struktur data dimana node subtree bagian kiri hanya tersusun dari nodes yang besarnya masing-masing kurang dari parent nodenya, dan subtree bagian kanannya hanya tersusun dari nodes yang besarnya masing-masing lebih dari parent nodenya. Masing-masing subtree bagian kiri dan kanan harus merupakan binary tree juga yang artinya hanya memiliki 2 cabang atau keturunan.
Dalam binary search tree, terdapat 3 operasi mendasar:
1. Search
Ketika kita ingin mencari suatu nilai dalam binary sarch tree, kita selalu memulai dari root. Jika data yang diinginkan kurang dari key value rootnya, maka kita cari hanya di bagian kiri subtreenya. Jika lebih besar maka kita cari di bagian kanan subtree.
Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.
2. Insert
Ketika kita ingin memasukkan data baru dalam tree, pertama kita mulai dari rootnya. JIka data lebih kecil dari root maka carilah bagian atau cabang kosong di subtree kiri, jika data lebih besar maka masukkan di bagian kanan.
3. Delete
Untuk mendelete sebuah data dalam binary search tree, ada 3 kondisi yang perlu dipertimbangkan:
a. Jika data yang ingin dihapus merupakan leaf, maka langsung hapus data tersebut.
b. Jika data memiliki 1 cabang atau anak, maka hapus data dan hubungkan anak dari data yang dihapus ke parent node data yang dihapus.
c. Jika data memiliki 2 cabang atau anak, cari cabang paling kanan data tersebut dan gantikan dengan data yang ingin dihapus, kemudian hapus data tersebut.
Comments