Skip to main content
TREE

AVL Tree
AVL tree adalah Binary Search Tree (BST) yang dapat menyeimbangkan diri sendiri di mana perbedaan antara ketinggian subtree kiri dan kanan tidak boleh lebih dari satu untuk semua node.
Pohon di atas adalah AVL karena perbedaan antara ketinggian sub pohon kiri dan kanan untuk setiap node kurang dari atau sama dengan 1.

Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penyisipan, kita harus menambah operasi penyisipan BST standar untuk melakukan penyeimbangan ulang.

Waktu yang diperlukan untuk melakukan insertion, deletion, search, atau operasi lainnya bergantung pada ketinggian pohon, ini berarti mereka dapat menjadi O (n) dalam kondisi terburuk.

Balance factor:
Perbedaan ketinggian subtree KIRI dan subtree KANAN.

Single Rotation
Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar tersebut. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0).




Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada tersebut. T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4, tinggi subtree T2 harus sama dengan T3. Node yang ditambahkan akan menjadi child dari subtree T2 atau T3. 

















Comments

Post a Comment

Popular posts from this blog

DATA STRUCT HEAP and TRIES Binary Heap Binary Heap adalah Complete Binary Tree di mana item disimpan dalam urutan khusus sedemikian sehingga nilai dalam simpul parent lebih besar (atau lebih kecil) dari nilai-nilai dalam dua node child-nya. Yang pertama disebut sebagai max heap dan yang terakhir disebut min heap. Heap dapat diwakili oleh binary tree atau array. 1) Max Heap  Selalu menyimpan nilai maksimum pada simpul root dan setiap simpul induk harus memiliki nilai simpul child yang lebih besar atau sama. 2) Min Heap  Selalu menyimpan nilai minimum pada simpul root itu dan setiap simpul induk harus memiliki nilai yang lebih kecil atau sama dengan nilai simpul child itu. Heap Sort Algorithm untuk mengurutkan dalam urutan yang meningkat: 1. Buat tumpukan maksimum dari data input. 2. Pada titik ini, item terbesar disimpan di root heap. Ganti dengan item terakhir heap diikuti dengan mengurangi ukuran heap oleh 1. Contoh di atas menunjukkan dua sk...
Post a Comment
Read more
Doubly Linked List  Doubly Linked List  adalah elemen-elemen yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan (head) atau belakang (tail). Doubly Linked List berisi pointer tambahan, biasanya disebut pointer sebelumnya, bersama dengan pointer berikutnya dan data yang ada di Single Linked List.   Elemen-Elemen Dalam Doubly Linked List    -  Data - Pointer Next ( *next ) - Pointer Prev ( *prev ) Doubly Linked List: Insertion Sebuah node dapat ditambahkan dengan empat cara: - Di bagian depan Doubly Linked List - Setelah node yang diberikan - Di bagian belakang  Doubly Linked List - Sebelum node yang diberikan InsertionFront (push depan) void insertFront(int num){           struct data *curr = (struct data *)malloc(sizeof (struct data));         curr->num = num;         curr->next = NULL;         if(...
Post a Comment
Read more
B inary Search Tree Binary Search Tree merupakan sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node. Selain itu, terdapat juga aturan dimana anak kiri dari parent selalu memiliki nilai lebih kecil dari nilai parent dan anak kanan selalu memiliki nilai lebih besar dari parent. Binary Search Tree adalah struktur data pohon biner berbasis node yang memiliki properti berikut: Subtree kiri dari sebuah node hanya berisi node dengan kunci lebih rendah dari kunci node. Subtree kanan sebuah node hanya berisi node dengan kunci lebih besar dari kunci node. Subtree kiri dan kanan masing-masing juga harus berupa pohon pencarian biner. Binary Search Tree memiliki 3 oprasi dasar, yaitu : Find(x)     : find value x didalam BST ( Search ) Insert(x)   : memasukan value baru x ke BST ( Push ) Remove(x)  : menghapus key x dari BST ( Delete ) Search BST Bayangkan kita akan...
Post a Comment
Read more