AVL Tree

AVL Tree
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi 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 di persingkat dan lebih sederhana.

contoh:

subtree dari 12 yang sebelah kanan ada maksnya ada 2 dan di sebelah kiri maksnya ada 3 sehingga memiliki beda tinggi hanya 1. ini masih diperbolehkan karena beda tinggi hanya 1

Penambahan node di AVL Tree

single rotation
single rotation dilakukan bila kondisi AVL tree saat akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut. T1,T2, dan T3 adalah sub tree yang urutannya harus seperti demikian serta height-nya harus sama (>=0).

double rotation
Double rotation dilakukan bila kondisi AVL Tree saat akan ditambahkan node baru dan posisi node baru seperti pada gambar brikut. T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4 (>=0). tinggi subtree T2 harus sama dengan T3 (>=0). Node yang akan ditambahkan akan menjadi child dari subtree T2 atau T3.



source: http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html