Panduan untuk Pohon AVL di Jawa

1. Perkenalan

Dalam tutorial ini, kami akan memperkenalkan Pohon AVL dan kami akan melihat algoritme untuk memasukkan, menghapus, dan mencari nilai.

2. Apakah Pohon AVL itu?

Pohon AVL, dinamai menurut penemunya Adelson-Velsky dan Landis, adalah pohon pencarian biner yang menyeimbangkan diri (BST).

Pohon self-balancing adalah pohon pencarian biner yang menyeimbangkan ketinggian setelah penyisipan dan penghapusan sesuai dengan beberapa aturan penyeimbangan.

Kompleksitas waktu kasus terburuk dari BST adalah fungsi dari ketinggian pohon. Secara khusus, jalur terpanjang dari akar pohon ke sebuah simpul. Untuk BST dengan N node, katakanlah bahwa setiap node hanya memiliki nol atau satu anak. Oleh karena itu tingginya sama dengan N, dan waktu pencarian dalam kasus terburuk adalah O (N). Jadi tujuan utama kita dalam BST adalah menjaga ketinggian maksimum mendekati log (N).

Faktor keseimbangan simpul N adalah tinggi (kanan (N)) - tinggi (kiri (N)) . Dalam Pohon AVL, faktor keseimbangan dari sebuah node hanya bisa salah satu dari nilai 1, 0, atau -1.

Mari kita definisikan objek Node untuk pohon kita:

public class Node { int key; int height; Node left; Node right; ... }

Selanjutnya, mari kita tentukan AVLTree :

public class AVLTree { private Node root; void updateHeight(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); } int height(Node n) { return n == null ? -1 : n.height; } int getBalance(Node n) { return (n == null) ? 0 : height(n.right) - height(n.left); } ... }

3. Bagaimana Menyeimbangkan Pohon AVL?

Pohon AVL memeriksa faktor keseimbangan dari node-nya setelah penyisipan atau penghapusan sebuah node. Jika faktor keseimbangan sebuah node lebih besar dari satu atau kurang dari -1, pohon tersebut akan menyeimbangkan dirinya sendiri.

Ada dua operasi untuk menyeimbangkan kembali pohon:

  • rotasi yang tepat dan
  • rotasi kiri.

3.1. Rotasi Kanan

Mari kita mulai dengan rotasi yang benar.

Asumsikan kita memiliki BST yang disebut T1, dengan Y sebagai simpul akar, X sebagai anak kiri dari Y, dan Z sebagai anak kanan X. Mengingat karakteristik sebuah BST, kita tahu bahwa X <Z <Y.

Setelah rotasi kanan Y, kita memiliki pohon yang disebut T2 dengan X sebagai akar dan Y sebagai anak kanan dari X dan Z sebagai anak kiri Y. T2 tetaplah BST karena mempertahankan urutan X <Z <Y .

Mari kita lihat operasi rotasi yang tepat untuk AVLTree kita :

Node rotateRight(Node y) { Node x = y.left; Node z = x.right; x.right = y; y.left = z; updateHeight(y); updateHeight(x); return x; }

3.2. Operasi Rotasi Kiri

Kami juga memiliki operasi rotasi kiri.

Asumsikan BST disebut T1, dengan Y sebagai simpul akar, X sebagai anak kanan dari Y, dan Z sebagai anak kiri X. Mengingat hal ini, kita tahu bahwa Y <Z <X.

Setelah rotasi kiri Y, kita memiliki pohon bernama T2 dengan X sebagai akar dan Y sebagai anak kiri X dan Z sebagai anak kanan Y. T2 tetap BST karena menjaga urutan Y <Z <X .

Mari kita lihat operasi rotasi kiri untuk AVLTree kita :

Node rotateLeft(Node y) { Node x = y.right; Node z = x.left; x.left = y; y.right = z; updateHeight(y); updateHeight(x); return x; }

3.3. Teknik Penyeimbangan Ulang

Kita dapat menggunakan rotasi kanan dan operasi rotasi kiri dalam kombinasi yang lebih kompleks untuk menjaga AVL Tree tetap seimbang setelah ada perubahan pada node-nya . Dalam struktur yang tidak seimbang, setidaknya satu node memiliki faktor keseimbangan sama dengan 2 atau -2. Mari kita lihat bagaimana kita bisa menyeimbangkan pohon dalam situasi ini.

Ketika faktor keseimbangan node Z adalah 2, subtree dengan Z sebagai root berada di salah satu dari dua status ini, dengan mempertimbangkan Y sebagai anak kanan dari Z.

Pada kasus pertama tinggi badan anak kanan Y (X) lebih besar dari tinggi anak kiri (T2). Kita dapat menyeimbangkan kembali pohon dengan mudah dengan rotasi kiri Z.

Untuk kasus kedua, tinggi anak kanan Y (T4) lebih kecil dari tinggi anak kiri (X). Situasi ini membutuhkan kombinasi operasi rotasi.

Dalam kasus ini, pertama kita putar Y ke kanan, sehingga pohon memiliki bentuk yang sama seperti kasus sebelumnya. Kemudian kita bisa menyeimbangkan kembali pohon dengan rotasi kiri Z.

Juga, ketika faktor keseimbangan simpul Z adalah -2, subpohonnya berada di salah satu dari dua keadaan ini, jadi kita menganggap Z sebagai akar dan Y sebagai anak kirinya.

Tinggi anak kiri Y lebih besar dari anak kanannya, jadi kita seimbangkan pohon dengan rotasi kanan Z.

Atau pada kasus kedua anak kanan Y memiliki tinggi badan yang lebih besar dari anak kirinya.

Jadi, pertama-tama kita mengubahnya menjadi bentuk sebelumnya dengan rotasi kiri Y, lalu kita menyeimbangkan pohon dengan rotasi kanan Z.

Mari kita lihat operasi penyeimbangan untuk AVLTree kami :

Node rebalance(Node z) { updateHeight(z); int balance = getBalance(z); if (balance > 1) { if (height(z.right.right) > height(z.right.left)) { z = rotateLeft(z); } else { z.right = rotateRight(z.right); z = rotateLeft(z); } } else if (balance  height(z.left.right)) z = rotateRight(z); else { z.left = rotateLeft(z.left); z = rotateRight(z); } } return z; }

Kami akan menggunakan rebalance setelah memasukkan atau menghapus node untuk semua node di jalur dari node yang diubah ke root.

4. Masukkan Node

Saat kita akan memasukkan kunci ke pohon, kita harus menemukan posisi yang tepat untuk melewati aturan BST. Jadi kita mulai dari root dan membandingkan nilainya dengan kunci baru. Jika kuncinya lebih besar, kita lanjutkan ke kanan - jika tidak, kita pergi ke anak kiri.

Setelah kita menemukan node induk yang tepat, selanjutnya kita tambahkan kunci baru sebagai node ke kiri atau kanan, tergantung nilainya.

Setelah menyisipkan node, kita memiliki BST, tapi mungkin bukan Pohon AVL. Oleh karena itu, kami memeriksa faktor keseimbangan dan menyeimbangkan kembali BST untuk semua node di jalur dari node baru ke root.

Mari kita lihat operasi penyisipan:

Node insert(Node node, int key) { if (node == null) { return new Node(key); } else if (node.key > key) { node.left = insert(node.left, key); } else if (node.key < key) { node.right = insert(node.right, key); } else { throw new RuntimeException("duplicate Key!"); } return rebalance(node); }

Penting untuk diingat bahwa kunci itu unik di pohon - tidak ada dua node yang berbagi kunci yang sama.

Kompleksitas waktu dari algoritma penyisipan adalah fungsi dari ketinggian. Karena pohon kita seimbang, kita dapat mengasumsikan bahwa kompleksitas waktu dalam kasus terburuk adalah O (log (N)).

5. Hapus sebuah Node

Untuk menghapus kunci dari pohon, pertama-tama kita harus menemukannya di BST.

Setelah kita menemukan node (disebut Z), kita harus memperkenalkan kandidat baru untuk menjadi penggantinya di pohon. Jika Z adalah daun, kandidat kosong. Jika Z hanya memiliki satu anak, maka anak tersebut adalah calon, tetapi jika Z memiliki dua anak, prosesnya sedikit lebih rumit.

Assume the right child of Z called Y. First, we find the leftmost node of the Y and call it X. Then, we set the new value of Z equal to X ‘s value and continue to delete X from Y.

Finally, we call the rebalance method at the end to keep the BST an AVL Tree.

Here is our delete method:

Node delete(Node node, int key) { if (node == null) { return node; } else if (node.key > key) { node.left = delete(node.left, key); } else if (node.key < key) { node.right = delete(node.right, key); } else { if (node.left == null || node.right == null) { node = (node.left == null) ? node.right : node.left; } else { Node mostLeftChild = mostLeftChild(node.right); node.key = mostLeftChild.key; node.right = delete(node.right, node.key); } } if (node != null) { node = rebalance(node); } return node; }

The time complexity of the delete algorithm is a function of the height of the tree. Similar to the insert method, we can assume that time complexity in the worst case is O(log(N)).

6. Search for a Node

Searching for a node in an AVL Tree is the same as with any BST.

Start from the root of the tree and compare the key with the value of the node. If the key equals the value, return the node. If the key is greater, search from the right child, otherwise continue the search from the left child.

Kompleksitas waktu pencarian adalah fungsi dari ketinggian. Kita dapat mengasumsikan bahwa kompleksitas waktu dalam kasus terburuk adalah O (log (N)).

Mari kita lihat kode contoh:

Node find(int key) { Node current = root; while (current != null) { if (current.key == key) { break; } current = current.key < key ? current.right : current.left; } return current; }

7. Kesimpulan

Dalam tutorial ini, kami telah menerapkan Pohon AVL dengan operasi penyisipan, penghapusan, dan pencarian.

Seperti biasa, Anda dapat menemukan kodenya di Github.