AVL pokok java

Pokok AVL juga dikenali sebagai pokok perduaan pengimbangan diri yang digunakan untuk mengimbangi dan mengira perbezaan antara ketinggian masing-masing subpokok kiri dan kanan yang hasilnya tidak boleh keluar sebagai lebih daripada satu dalam keseluruhan pokok seimbang. Operasi pepohon Carian Binari membenarkan operasi pemasukan, pemadaman, carian, maks dan min yang diperlukan sebagai sebahagian daripada pepohon AVL juga. Semua operasi ini dianggap sebagai urusan yang mahal kerana jika perbezaan antara ketinggian semua BST dikekalkan maka kos dan kerumitan masa yang berkaitan dengannya dapat dikekalkan.

Mulakan Kursus Pembangunan Perisian Percuma Anda

Pembangunan web, bahasa pengaturcaraan, ujian perisian & lain-lain

Sintaks:

Tidak ada sintaks yang betul tetapi semasa melaksanakannya dalam pepohon AVL Java dianggap sebagai struktur data di mana sintaks diwakili seperti berikut:

Class Node_demo
{
int key, height_0;
Node left, right;
Node_demo (int d_1)
{
key = d_1;
height_0 = 1;
}
}
class AVLTree_demo1 {
Node root_0;
int height_0(Node N_1) {
if (N_1== null)
return 0;
return N_1.height;
}

Penjelasan:

Dalam aliran sintaks di sini Node_demo Kelas mengandungi kunci, ketinggian dan struktur yang menerangkan pasangan nilai kunci tempat elemen akan disimpan. Diikuti oleh AVL_Tree demo_1 nod yang mengandungi nod akar dan elemen yang berkaitan dengan pasangan nilai yang mempunyai ketinggian untuk dikekalkan di mana-mana dengan nilai sebagai nol.

Bagaimanakah pokok AVL berfungsi di java?

• Terdapat aliran yang betul di mana pokok AVL berfungsi di Jawa dan dicipta oleh GM Adelson pada tahun 1962.
• Pokok AVL ditakrifkan sebagai pepohon carian perduaan seimbang ketinggian di mana setiap nod dikaitkan dengan faktor keseimbangan yang dikira dengan menolak ketinggian pokok kecil kanannya daripada pokok kecil kirinya.
• Pokok dipanggil seimbang jika faktor keseimbangan terletak di antara -1 hingga 1 jika tidak, pokok itu perlu seimbang dari atas ke bawah.
• Oleh kerana pokok imbangan mengawal ketinggian pepohon carian binari maka ketinggiannya adalah O(h) sedangkan terdapat peruntukan di mana ia diperlukan untuk memanjangkan pepohon carian binari sebaik sahaja ia menjadi condong daripada dalam kes itu ia keluar sebagai (n-1) untuk manipulasinya.
• Apabila pokok senget menjadi terhad maka dalam kes itu ia mengenakan sempadan atas pada semua operasi yang keluar sebagai O (log n) dengan n ialah bilangan nod.
• Terdapat cara juga untuk memutarkan pokok AVL dan ia berlaku hanya dalam satu keadaan di mana jika faktor keseimbangan terletak di antara -1, 1, atau 0.
• Terdapat empat jenis Putaran iaitu seperti berikut:
• Putaran LL: Nod akan dimasukkan jika ia terletak di subpokok kiri pokok dengan nod D.
• Putaran RR: Nod akan dimasukkan jika ia terletak pada subpokok kanan pokok dengan nod D.
• Putaran LR: Nod akan dimasukkan jika ia dimasukkan ke dalam subpokok kanan subpokok kiri dengan nod D.
• Putaran RL: Nod akan dimasukkan jika ia dimasukkan ke dalam subpokok kiri subpokok kanan dengan nod D.

Di mana D bermaksud nod yang faktor ketinggian dan keseimbangannya terletak selain daripada -1, 1 dan 0 yang menyebabkan semua Putaran ini diperlukan untuk menjadikannya dalam format yang betul.

Terdapat banyak operasi yang wujud dan untuk itu, mesti ada putaran yang betul dengan analisis yang betul untuk manipulasi.

Contoh: Contoh ini menunjukkan pepohon AVL di mana sisipan, sisipan kiri dan kanan dengan prapesanan, pasca pesanan dan perwakilan pesanan rata seperti yang ditunjukkan dalam output di bawah.

import java. util.LinkedList;
import java.util.Queue;
class Node_8 {
int data_0, height_1;
Node_8 left_nd_0;
Node_8 right_nd_0;
Node_8(int d_2) {
data_0 = d_2;
height_1 = 1;
}
}
public class AVLTree_Demo
{
Node_8 root_0;
int height_1(Node_8 N) {
if (N == null)
return 0;
return N.height_1;
}
int max_2(int a_0,  int b_0) {
return (a_0 > b_0) ? a_0 : b_0;
}
Node_8 rightRotation_mode(Node_8 oldRoot_0) {
Node_8 newRoot_0 = oldRoot_0.left_nd_0;
Node_8 temp_0 = newRoot_0.right_nd_0;
newRoot_0.right_nd_0 = oldRoot_0;
oldRoot_0.left_nd_0 = temp_0;
newRoot_0.height_1 = max_2(height_1(newRoot_0.left_nd_0), height_1(newRoot_0.right_nd_0)) + 1;
oldRoot_0.height_1 = max_2(height_1(oldRoot_0.left_nd_0), height_1(oldRoot_0.right_nd_0)) + 1;
return newRoot_0;
}
Node_8 leftRotation_mode(Node_8 oldRoot_0) {
Node_8 newRoot_0 = oldRoot_0.right_nd_0;
Node_8 temp_0 = newRoot_0.left_nd_0;
newRoot_0.left_nd_0 = oldRoot_0;
oldRoot_0.right_nd_0 = temp_0;
newRoot_0.height_1 = max_2(height_1(newRoot_0.left_nd_0), height_1(newRoot_0.right_nd_0)) + 1;
oldRoot_0.height_1=max_2(height_1(oldRoot_0.left_nd_0), height_1(oldRoot_0.right_nd_0)) + 1;
return newRoot_0;
}
int balFactor_c(Node_8 root_0) {
if(root_0 == null)
return 0;
return height_1(root_0.left_nd_0) - height_1(root_0.right_nd_0);
}
Node_8 insert(Node_8 root_0, int data_0) {
if(root_0 == null)
return new Node_8(data_0);
else if(data_0 < root_0.data_0)
root_0.left_nd_0 = insert(root_0.left_nd_0, data_0);
else if(data_0 > root_0.data_0)
root_0.right_nd_0 = insert(root_0.right_nd_0, data_0);
else
return root_0;
root_0.height_1= max_2(height_1(root_0.left_nd_0), height_1(root_0.right_nd_0)) + 1;
int bal = balFactor_c(root_0);
if(bal > 1 && data_0 < root_0.left_nd_0.data_0)
return rightRotation_mode(root_0);
if(bal < -1 && data_0 > root_0.right_nd_0.data_0)
return leftRotation_mode(root_0);
if(bal > 1 && data_0 > root_0.left_nd_0.data_0) {
root_0.left_nd_0 = leftRotation_mode(root_0.left_nd_0);
return rightRotation_mode(root_0);
}
if(bal < -1 && data_0 < root_0.right_nd_0.data_0) {
root_0.right_nd_0 = rightRotation_mode(root_0.right_nd_0);
return leftRotation_mode(root_0);
}
return root_0;
}
void preOrder_traversal(Node_8 node) {
if (node != null) {
System.out.print(node.data_0 + " ");
preOrder_traversal(node.left_nd_0);
preOrder_traversal(node.right_nd_0);
}
}
void levelOrder_traversal(Node_8 root) {
Queue<Node_8> q_1 = new LinkedList<Node_8>();
q_1.add(root);
while(!q_1.isEmpty()) {
Node_8 current = q_1.peek();
System.out.print(current.data_0 + " ");
if(current.left_nd_0 != null)
q_1.add(current.left_nd_0);
if(current.right_nd_0 != null)
q_1.add(current.right_nd_0);
q_1.poll();
}
}
public static void main (String args[]) {
AVLTree_Demo tree = new AVLTree_Demo ();
tree. root_0 = tree.insert(tree.root_0, 15);
tree.root_0 = tree.insert(tree.root_0, 20);
tree.root_0 = tree.insert(tree.root_0, 19);
tree.root_0 = tree.insert(tree.root_0, 40);
tree.root_0 = tree.insert(tree.root_0, 50);
tree.root_0 = tree.insert(tree.root_0, 25);
System.out.println("order_of_Preorder_traversal_representation : ");
tree.preOrder_traversal(tree.root_0);
System.out.println();
System.out.println("Levelorder_of_traversal_representation : ");
tree.levelOrder_traversal(tree.root_0);
}
}

Output:

Penjelasan: Atur cara ini melakukan penyisipan elemen dalam tiang pepohon AVL yang terdapat beberapa susunan dengan cara di mana sesetengah menyemak seperti sama ada senarai yang diambil kosong atau tidak dan kemudian jika pepohon AVL mempunyai putaran yang akan dilakukan dalam format prapesanan, pasca pesanan atau pesanan peringkat. Semua elemen yang diberikan secara automatik mengambil input dan menyusunnya dalam susunan yang betul.

Kesimpulan

Pokok AVL di Java digunakan sebagai struktur data yang betul yang disukai oleh ramai pembangun kerana ia memberikan kelebihan dari segi operasi dan membantu dalam menjimatkan dan memakan masa-kerumitan yang dicipta oleh set besar kod. Pepohon AVL mempunyai keupayaan untuk mengendalikan operasi utama seperti penyisipan, pemadaman, penggiliran dan penyingkiran daripada keseluruhan subpokok jika ketinggian dikekalkan dengan betul.

Atas ialah kandungan terperinci AVL pokok java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!