{"id":2388,"date":"2022-10-26T21:53:58","date_gmt":"2022-10-26T14:53:58","guid":{"rendered":"http:\/\/student-activity.binus.ac.id\/himmat\/?p=2388"},"modified":"2022-10-26T21:53:58","modified_gmt":"2022-10-26T14:53:58","slug":"apa-itu-avl-tree","status":"publish","type":"post","link":"https:\/\/student-activity.binus.ac.id\/himmat\/2022\/10\/apa-itu-avl-tree\/","title":{"rendered":"Apa Itu AVL Tree?"},"content":{"rendered":"

AVL Tree<\/span><\/em> adalah salah satu bentuk <\/span>self-balancing tree<\/span><\/em> dari sebuah <\/span>binary search tree<\/span><\/em>. <\/span>AVL Tree<\/span><\/em> dikatakan <\/span>balance <\/span><\/em>(seimbang) apabila nilai absolut dari <\/span>balance factor<\/span><\/em> dalam masing-masing <\/span>node<\/span><\/i> tidak melebihi satu. Apabila nilai tersebut lebih dari satu, maka <\/span>node <\/span><\/i>tersebut akan dinyatakan sebagai tidak seimbang<\/span>. Karena terdapat sebuah <\/span>node <\/span><\/i>yang tidak seimbang<\/span>\u00a0maka <\/span>node <\/span><\/i>tersebut telah melakukan pelanggaran sifat <\/span>self-balancing tree<\/span><\/em> dari sebuah <\/span>AVL Tree<\/span><\/em>, maka perlu dilakukan perbaikan pada <\/span>tree<\/span><\/em> tersebut.\u00a0<\/span><\/p>\n

Balance factor <\/span><\/em>sebuah <\/span>node <\/span><\/i>dapat dihitung dengan mengurangi nilai <\/span>height subtree <\/span><\/em>anak kiri dengan nilai <\/span>height subtree <\/span><\/em>anak kanan dari <\/span>node tersebut<\/span><\/i>, sedangkan <\/span>height <\/span><\/em>sendiri adalah jumlah <\/span>edge<\/span><\/em> yang ada dari <\/span>root <\/span><\/em>menuju <\/span>leaf<\/span><\/em> node <\/span><\/i>paling bawah (<\/span>level <\/span><\/i>tertinggi).<\/span><\/i><\/p>\n

\"\"<\/a>
\nContoh tidak <\/b>balance<\/i><\/b><\/p>\n

 <\/p>\n

\"\"<\/a>
\nContoh <\/b>balance<\/i><\/b><\/p>\n

 <\/p>\n

Untuk memperbaiki tree yang melanggar sifat <\/span>self-balancing tree<\/span><\/em>, maka dilakukanlah <\/span>rotation<\/span><\/em>. <\/span>Ketika melakukan rotation<\/em> pada <\/span>node X, Y, <\/span><\/i>dan <\/span>Z<\/span><\/i>, <\/span>node<\/span><\/i> Y <\/span><\/i>sebagai titik putar dikatakan sebagai <\/span>pivot <\/em>node<\/span><\/i>, sehingga putaran bertumpu pada <\/span>pivot node<\/span><\/i> tersebut. <\/span>Untuk kasus yang tidak berat sebelah (<\/span>balance factor<\/span><\/em> node<\/span><\/i> yang tidak <\/span>balance <\/span><\/em>berbeda tanda dengan <\/span>balance <\/span><\/em>factor<\/span><\/i> anak <\/span>node<\/span><\/i>). Maka dilakukan <\/span>double rotations<\/span><\/em>.<\/span><\/p>\n

 <\/p>\n

Referensi<\/span><\/p>\n

https:\/\/www.tutorialspoint.com\/data_structures_algorithms\/avl_tree_algorithm.html\u00a0<\/span><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

AVL Tree adalah salah satu bentuk self-balancing tree dari sebuah binary search tree. AVL Tree dikatakan balance (seimbang) apabila nilai absolut dari balance factor dalam masing-masing node tidak melebihi satu. Apabila nilai tersebut lebih dari satu, maka node tersebut akan dinyatakan sebagai tidak seimbang. Karena terdapat sebuah node yang tidak seimbang\u00a0maka node tersebut telah melakukan […]<\/p>\n","protected":false},"author":15,"featured_media":2392,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[87,25,66,86,88],"class_list":["post-2388","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-articles","tag-avl-tree","tag-computer-science","tag-node","tag-rotation","tag-tree"],"_links":{"self":[{"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/posts\/2388","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/users\/15"}],"replies":[{"embeddable":true,"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/comments?post=2388"}],"version-history":[{"count":1,"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/posts\/2388\/revisions"}],"predecessor-version":[{"id":2393,"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/posts\/2388\/revisions\/2393"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/media\/2392"}],"wp:attachment":[{"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/media?parent=2388"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/categories?post=2388"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/student-activity.binus.ac.id\/himmat\/wp-json\/wp\/v2\/tags?post=2388"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}