AVL TREE 2301869853

Stephen Jasper - 2301869853
AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.

·         Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.

·         anggap T adalah node yang harus diseimbangkan kembali
– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :

Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :

Maka akan dilakukan single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :

Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :

BTREE

B-tree adalah struktur data pohon self-balancing yang memelihara data yang diurutkan dan memungkinkan pencarian, akses sekuensial, penyisipan, dan penghapusan dalam waktu logaritmik . B-tree menggeneralisasikan pohon pencarian biner , memungkinkan untuk node dengan lebih dari dua anak. Tidak seperti pohon pencarian biner self-balancing lainnya , B-tree sangat cocok untuk sistem penyimpanan yang membaca dan menulis blok data yang relatif besar, seperti disk. Ini biasanya digunakan dalam database dan sistem file.

Pohon-B orde m adalah pohon yang memenuhi sifat-sifat berikut:

1. Setiap simpul paling banyak memiliki anak.
2. Setiap simpul non-daun (kecuali root) memiliki setidaknya ⌉ m / 2⌉ simpul anak.
3. Akar memiliki setidaknya dua anak jika bukan simpul daun.
4. Node tanpa daun dengan k anak-anak berisi kunci k -1.
5. Semua daun muncul di tingkat yang sama dan tidak membawa informasi.

Simpul internal

Node internal adalah semua node kecuali node daun dan simpul akar. Mereka biasanya direpresentasikan sebagai kumpulan elemen dan pointer anak. Setiap simpul internal berisi maksimal anak U dan minimum anak L. Dengan demikian, jumlah elemen selalu 1 kurang dari jumlah pointer anak (jumlah elemen adalah antara L- 1 dan U- 1). U harus 2 L atau 2 L −1; oleh karena itu setiap simpul internal setidaknya setengah penuh. Hubungan antara U dan L menyiratkan bahwa dua node setengah penuh dapat bergabung untuk membuat simpul hukum, dan satu simpul penuh dapat dibagi menjadi dua simpul hukum (jika ada ruang untuk mendorong satu elemen ke dalam induk). Properti ini memungkinkan untuk menghapus dan memasukkan nilai-nilai baru ke dalam B-tree dan menyesuaikan pohon untuk mempertahankan properti B-tree.

Simpul root

Jumlah anak root node memiliki batas atas yang sama dengan node internal, tetapi tidak memiliki batas bawah. Misalnya, ketika ada kurang dari L −1 elemen di seluruh pohon, root akan menjadi satu-satunya simpul di pohon tanpa anak sama sekali.

Node daun

Dalam terminologi Knuth, simpul daun tidak membawa informasi apa pun. Node internal yang satu tingkat di atas daun adalah apa yang akan disebut "daun" oleh penulis lain: node ini hanya menyimpan kunci (paling banyak m -1, dan setidaknya m / 2-1 jika bukan root) dan pointer ke node yang tidak membawa informasi.