Bagaimana untuk melaksanakan algoritma pokok AVL menggunakan java

. dalam skop yang lebih kecil. Dalam artikel ini, kita akan belajar cara melaksanakan algoritma pepohon AVL menggunakan Java dan memberikan contoh kod konkrit.

1. Penerangan asas dan ciri pokok AVL:

Pokok AVL dicadangkan oleh G. M. Adelson-Velsky dan Evgenii Landis pada tahun 1962. Dalam pokok AVL, bagi setiap nod, subpokok kiri dan subpokok kanan Perbezaan ketinggian tidak boleh melebihi 1. Jika melebihi 1, operasi putaran diperlukan untuk pengimbangan automatik. Berbanding dengan pokok carian binari biasa, pokok AVL mempunyai prestasi carian, sisipan dan pemadaman yang lebih baik.

2. Pelaksanaan nod pepohon AVL:

Di Java, kami boleh menggunakan kelas nod tersuai untuk melaksanakan pepohon AVL. Setiap nod mengandungi nilai dan rujukan kepada subpokok kiri dan kanan, serta pembolehubah untuk merekod ketinggian nod.

class AVLNode {
    int val;
    AVLNode left, right;
    int height;

    AVLNode(int val) {
        this.val = val;
        this.height = 1;
    }
}

3. Kira ketinggian nod:

Sebelum melaksanakan algoritma pokok AVL, kita memerlukan fungsi untuk mengira ketinggian nod. Fungsi ini memperoleh ketinggian nod semasa dengan mengira ketinggian subpokok kiri dan subpokok kanan secara rekursif, kemudian mengambil nilai yang lebih besar daripada kedua-dua dan menambah 1.

int getHeight(AVLNode node) {
    if (node == null) {
        return 0;
    }
    return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}

4 Laksanakan operasi putaran pokok AVL:

Apabila operasi memasukkan dan memadam, pokok AVL perlu diputar untuk mengekalkan keseimbangan pokok. Kami akan melaksanakan kedua-dua operasi kiri dan kanan. . menjadi subpokok kanan bagi nod akar asal. . nod akar menjadi asal Subpokok kiri nod akar.

AVLNode leftRotate(AVLNode node) {
    AVLNode newRoot = node.right;
    AVLNode temp = newRoot.left;

    newRoot.left = node;
    node.right = temp;

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;

    return newRoot;
}

5. Pelaksanaan operasi sisipan:
Apabila memasukkan nod baharu, ia mula-mula dimasukkan mengikut peraturan pepohon carian binari, dan kemudian dilaraskan mengikut faktor keseimbangan nod pada laluan sisipan termasuk operasi putaran dan pengemaskinian nod.

AVLNode rightRotate(AVLNode node) {
    AVLNode newRoot = node.left;
    AVLNode temp = newRoot.right;

    newRoot.right = node;
    node.left = temp;

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;

    return newRoot;
}

6. Pelaksanaan operasi pemadaman:
Apabila memadamkan nod, ia pertama kali dipadamkan mengikut peraturan pepohon carian binari, dan kemudian dilaraskan mengikut faktor keseimbangan nod pada laluan pemadaman operasi dan mengemas kini ketinggian nod.

AVLNode insert(AVLNode node, int val) {
    if (node == null) {
        return new AVLNode(val);
    }

    if (val < node.val) {
        node.left = insert(node.left, val);
    } else if (val > node.val) {
        node.right = insert(node.right, val);
    } else {
        // 如果节点已经存在，不进行插入
        return node;
    }

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    int balanceFactor = getBalanceFactor(node);

    // 左左情况，需要进行右旋
    if (balanceFactor > 1 && val < node.left.val) {
        return rightRotate(node);
    }

    // 左右情况，需要进行左旋后再进行右旋
    if (balanceFactor > 1 && val > node.left.val) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 右右情况，需要进行左旋
    if (balanceFactor < -1 && val > node.right.val) {
        return leftRotate(node);
    }

    // 右左情况，需要进行右旋后再进行左旋
    if (balanceFactor < -1 && val < node.right.val) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;
}

7. Contoh ujian:
1. Untuk mengesahkan ketepatan algoritma pokok AVL yang kami laksanakan, kami boleh menggunakan contoh berikut untuk menguji:
   

   AVLNode delete(AVLNode node, int val) {
       if (node == null) {
           return node;
       }
   
       if (val < node.val) {
           node.left = delete(node.left, val);
       } else if (val > node.val) {
           node.right = delete(node.right, val);
       } else {
           if (node.left == null || node.right == null) {
               node = (node.left != null) ? node.left : node.right;
           } else {
               AVLNode successor = findMin(node.right);
               node.val = successor.val;
               node.right = delete(node.right, node.val);
           }
       }
   
       if (node == null) {
           return node;
       }
   
       node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
   
       int balanceFactor = getBalanceFactor(node);
   
       // 左左情况，需要进行右旋
       if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
           return rightRotate(node);
       }
   
       // 左右情况，需要进行左旋后再进行右旋
       if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
           node.left = leftRotate(node.left);
           return rightRotate(node);
       }
   
       // 右右情况，需要进行左旋
       if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
           return leftRotate(node);
       }
   
       // 右左情况，需要进行右旋后再进行左旋
       if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
           node.right = rightRotate(node.right);
           return leftRotate(node);
       }
   
       return node;
   }
   
   AVLNode findMin(AVLNode node) {
       while (node.left != null) {
           node = node.left;
       }
       return node;
   }

Hasil output:

10 20 25 30 40 50

2. 
   
Artikel ini memperkenalkan Cara menggunakan Java untuk melaksanakan algoritma pepohon AVL, dengan contoh kod khusus disediakan. Dengan melaksanakan operasi sisipan dan pemadaman, kami boleh memastikan bahawa pepohon AVL sentiasa seimbang, menghasilkan prestasi carian, sisipan dan pemadaman yang lebih baik. Saya percaya bahawa dengan mengkaji artikel ini, pembaca boleh lebih memahami dan menggunakan algoritma pepohon AVL.

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