Binary Search Tree

Binary Search Tree
Binary Search Tree (BST) adalah salah satu struktur data yang mendukung pencarian lebih cepat, penyortiran cepat, dan penyisipan dan penghapusan yang mudah. BST juga dikenal berbagai versi pohon biner Untuk simpul x dalam BST T,

• Subtree kiri (left) x berisi elemen yang lebih kecil dari yang disimpan dalam x
• Subtree kanan (right) x berisi semua elemen yang lebih besar dari yang disimpan dalam x

Operasi: Penghapusan

Ada 3 kasus yang harus dipertimbangkan:

• Jika kunci ada di leaf, hapus saja node tersebut.

• Jika kuncinya ada di node yang memiliki dua child, temukan child paling kanan dari subtree kirinya (node P), ganti kuncinya dengan kunci P dan hapus P secara rekursif. (atau secara bergantian Anda dapat memilih child  paling kiri dari sub pohon kanannya).

• Jika kunci ada di node yang memiliki satu child, hapus node itu dan sambungkan child-nya ke parent-nya.