AVL TREE and BINARY TREE

May 01, 2020

AVL TREE and BINARY TREE

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.

Fungsi dari Balanced BST adalah membuat tinggi dari BST menjadi seminimal mungkin, dengan begitu kecepatan berjalannya suatu fungsi akan optimal(O (log n)).

Note:

Cara menentukan Height and Balance Factor:

Height:

- Jika node (root) tidak memiliki subtree heightnya = 0

- Jika node adalah leaf, height = 1

- Jika internal node, maka height = height tertinggi dari anak + 1

Balance Factor:

- Selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.

OPERASI AVL TREE

Ada 4 kondisi yang harus diperhatikan saat rebalance:
*Note: misalkan X = node yang harus di rebalance

1. Node terendah ada pada SubTree kiri & merupakan anak kiri dari X

2. Node terendah ada pada SubTree kanan & merupakan anak kanan dari X

3. Node terendah ada pada SubTree kanan & merupakan anak kiri dari X

4. Node terendah ada pada SubTree kiri & merupakan anak kanan dari X

Untuk kondisi 1 & 2, kita perlu menerapkan single rotation.
Untuk kondisi 3 & 4, kita perlu menerapkan double rotation.

Jenis rotation:

· LL rotation (Left Rotation) : kesalahan muncul dari anak kanan SubTree kanan

· RR rotation (Right Rotation) : kesalahan muncul dari anak kiri SubTree kiri

· LR rotation (Left-Right): kesalahan muncul dari anak kiri SubTree kanan

· RL rotation (Right-Left) : kesalahan muncul dari anak kanan SubTree kiri

LL Rotation

The tree shown in following figure is an AVL Tree, however, we,need to insert an element into the left of the left sub-tree of A. the tree can become unbalanced with the presence of the critical node A.

The node whose balance factor doesn't lie between -1 and 1, is called critical node.

In order to rebalance the tree, LL rotation is performed as shown in the following diagram.

The node B becomes the root, with A and T3 as its left and right child. T1 and T2 becomes the left and right sub-trees of A.

Example :

Insert the node with value 12 into the tree shown in the following figure.

Solution:

12 will be inserted to the left of 25 and therefore, it disturbs the AVLness of the tree. The tree needs to be rebalanced by rotating it through LL rotation.

Here, the critical node 100 will be moved to its right, and the root of its left sub-tree (B) will be the new root node of the tree.

The right sub-tree of B i.e. T2 (with root node 75) will be place to the left of Node A (with value 100).

By following this procedure, the tree will be rebalanced and therefore, it will be an AVL tree produced after inserting 12 into it.

RR Rotation

If the node is inserted into the right of the right sub-tree of a node A and the tree becomes unbalanced then, in that case, RR rotation will be performed as shown in the following diagram.

While the rotation, the node B becomes the root node of the tree. The critical node A will be moved to its left and becomes the left child of B.

The sub-tree T3 becomes the right sub-tree of A. T1 and T2 becomes the left and right sub-tree of node A.

Example

Insert 90 into the AVL Tree shown in the figure.

Solution :

90 is inserted in to the right of the right sub-tree. In this case, critical node A will be 85, which is the closest ancestor to the new node, whose balance factor is disturbed. Therefore, we need to rebalance the tree by applying RR rotation onto it.

The node B will be the node 90 , which will become the root node of this sub-tree. The critical node 85 will become its left child, in order to produce the rebalanced tree which is now an AVL tree.

RL Rotation

RL rotations is to be performed if the new node is inserted into the left of right sub-tree of the critical node A. Let us consider, Node B is the root of the right sub-tree of the critical node, Node C is the root of the sub-tree in which the new node is inserted.

Let T1 be the left sub-tree of the critical node A, T2 and T3 be the left and right sub-tree of Node C respectively, sub-tree T4 be the right sub-tree of Node B.

Since, RL rotation is the mirror image of LR rotation. In this rotation, the node C becomes the root node of the tree with A and B as its left and right children respectively. Sub-trees T1 and T2 becomes the left and right sub-trees of A whereas, T3 and T4 becomes the left and right sub-trees of B.

The process of RL rotation is shown in the following image.

Example

Insert node with the value 92 into the tree shown in the following figure.

Solution :

inserting 92 disturbs the balance factor of the node 92 and it becomes the critical node A with 105 as the node B and 95 with

the node C. In RL rotation, C becomes the root of the tree (as shown in the figure) with node A (90) and B (105) as its left and right children respectively. The tree will be rotated as shown in the figure.

LR Rotation

LR rotation is to be performed if the new node is inserted into the right of the left sub-tree of node A.

In LR rotation, node C (as shown in the figure) becomes the root node of the tree, while the node B and A becomes its left and right child respectively.

T1 and T2 becomes the left and right sub-tree of Node B respectively whereas, T3 and T4 becomes the left and right sub-tree of Node A.

Example:

Insert the node with value 70 into the tree shown in the following data structure.

Solution

According to the property of binary search tree, the node with value 70 is inserted into the right of the left sub-tree of the root of tree.

As shown in the figure, the balance factor of the root node disturbed upon inserting 70 and this becomes the critical node A.

To rebalance the tree, LR rotation is to be performed. Node C i.e. 75 will become the new root node of the tree with B and A as its left and right child respectively.

Sub-trees T1, T2 become the left and right sub-tree of B while sub-trees T3, T4 become the left and right sub-tree of A.

The procedure is shown in the following figure.

Gambar AVL Tree

Penambahan node di AVL Tree

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation

Single Rotation

Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar 2.

Gambar 2

Double Rotation

Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 3. 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 ditambahkan akan menjadi child dari subtree T2 atau T3. Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar 3.

Gambar 3

Menghapus node di AVL Tree

Proses menghapus sebuah node di AVL tree hampir sama dengan BST. Penghapusan sebuah node dapat menyebabkan tree tidak imbang Setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus → root. Gunakan single atau double rotation untuk menyeimbangkan node yang tidak imbang. Pencarian node yang imbalance diteruskan sampai root.

Contoh soal: 5, 6, 7, 0, 4, 3, 8

First Step :

Second Step :

Third Step:

Third Step Change:

Fourth Step :

Fifth Step:

Fifth Step Change :

Sixth Step:

Sixth Step Change:

Seventh Step:

Contol Soal Delete:

Delete = 3,4,8

Delete First Step:

Delete First Step Change :

Delete Second Step :

Delete Third Step :

BINARY TREE (B-TREE)

Pengertian Tree dalam Struktur Data
Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemen KHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untuk jelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree.

· Parent : predecssor satu level di atas suatu node.

· Child : successor satu level di bawah suatu node.

· Sibling : node-node yang memiliki parent yang sama dengan suatu node.

· Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

· Size : banyaknya node dalam suatu tree.

· Height : banyaknya tingkatan/level dalam suatu tree.

· Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

· Leaf : node-node dalam tree yang tak memiliki seccessor.

· Degree : banyaknya child yang dimiliki suatu node.

Pengertian Binaary Tree dalam Struktur Data
Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Node pada Binary Tree
Jumlah maksimum node pada setiap tingkat adalah 2ⁿ, Node pada binary tree maksimumnya berjumlah 2ⁿ-1.

Ciri-ciri B-tree dari suatu M-way tree:

· Setiap node memiliki paling banyak M anak

· Setiap node kecuali root memiliki minimal M/2 anak

· root harus memiliki minimal 2 anak (bila dia bukan leaf)

· Suatu node yang bukan leaf dengan n jumlah anak, harus memiliki keys sebanyak n-1

· Setiap data disimpan secara teratur / sorted

· Setiap leaf berada level yang sama

Oprasi: Search BST

dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.

Bayangkan kita akan mencari value X.

Memulai Pencarian Dari Root
Jika Root adalah value yang kita cari , maka berhenti
Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan

Operasi: Insertion BST

Memasukan value (data) baru kedalam BST dengan rekrusif

Bayangkan kita menginsert value x :

Dimulai dari root
jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )

Contoh Insertion :

Kita ingin menambahkan value 35 kedalam BST yang sudah ada

yang berwarna hijau adalah root , setiap menginsert , mencari , atau delete selalu di mulai dari root.

dan new node berwarna orange yang memiliki value 35, kemudian kita cek dengan root(30), maka 30 .. 35 ? karena 30 < 35 maka , node lebih besar dari root kemudian kita arahkan ke sub-tree yang berada di kanan dan kemudian cek ulang kembali

Sekarang kita cek 35 dengan 37 , maka 35 < 37 jadi kita arahkan ke bagian kiri dan kita cek kembali , karena di bagian kiri sudah ada value yaitu 32

kemudian kita cek 32 dengan 35 , ternyata 35 > 32 jadi kita masukan ke kanan , dan ternyata kita sudah menemukan tempat kosong untuk mengisi new node(35) jadi kita masukan 35 di sebelah kanan dari node(32)

Operasi: Delete ( Remove )

akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :

Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan~~) atau dengan cari dari right sub-tree anak kiri paling terakhir(leaf) (kanan,kiri~~)