1. Nilai root < nilai anak kanan
2. Nilai root > nilai anak kiri
Binary search tree mepercepat pencarian dibandingkan sequential search
BST
Waktu terlama = tinggi binary search tree
jika ada n data, waktu ( t ) = log ( n+ 1) // dengan basis 2
= log n ( O ) // dengan basis 2
Sequential search
waktu ( t ) = n ( O )
Operasi delete
Prinsip : setelah operasi delete hasil harus binary search tree lagi
Ada 3 operasi :
1. Jika delete node yang tidak punya anak : tidak ada perubahan
2. Jika delete node yang memiliki 1 anak : anaknya sebagai pengganti
3. Jika delete node yang memiliki 2 anak :
jika pengganti dari kiri, ambil node tertinggi
Jika pengganti dari kanan, ambil node terendah
Untuk source code :
| http://download.gilaupload.com/filepointer.php?fid=a1315ef67274eed20268babaf129c501 |
Untuk animasi :
http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/
