Python BST

Pada modul sebelumnya kita harus memilih node untuk dilakukan balancing, tentu akan lebih mudah jika ada fungsi untuk melakukan auto balancing pada imbalance node. Untuk itu kita perlu membuat beberapa helper dan fungsi untuk melakukan balancing pada setiap imbalance node. Pertama kita buat fungsi helper pada class Node untuk menghitung perbedaan tinggi. Fungsi ini dimodifikasi … Read more

Melanjutkan dari modul sebelumnya, pada modul ini akan diimplementasikan dalam Python. Buat fungsi baru diluar class dengan nama rotateRight dan rotateLeft. Berikut isi lengkap program tree. Jika dijalankan maka sesuai ekspektasi program diatas berhasil melakukan rebalancing. Bagaimana dengan left-right unbalanced tree? Seperti yang sudah dibahas dimodul sebelumnya, kita cukup melakukan rotasi left rotation yang kemudian … Read more

Pada modul sebelumnya dibahas bagaimana mendeteksi imbalance tree, pada modul ini akan dibahas bagaimana rebalancing tree tersebut. Ada 4 macam imbalance tree, yaitu left-left, right-right, left-right dan right-left imbalance. Untuk jelasnya lihat gambar berikut. Untuk melakukan balancing padan tree, digunakan rotasi. Berdasarkan tipe imbalance tree, terdapat 4 cara rotasi: left-left, lakukan right rotation. right-right, lakukan … Read more

Kondisi tree yang balanced akan membuat proses searching pada tree lebih cepat. Jadi apa yang dimaksud dengan imbalance tree? Kondisi imbalance atau tidak seimbang dari tree adalah jika salah satu kaki memiliki kedalaman >= 2 dibanding kaki lainnya. Kondisi unbalanced pada tree dilihat dari perspektif root node. Kita pun bisa melihat imbalance pada tingkat node. … Read more