AVL Tree | Java Development Journal

1
AVL Tree | Java Development Journal

Σε αυτό το άρθρο, θα καλύψουμε το δέντρο AVL και τι τα κάνει τόσο ξεχωριστά και τόσο δύσκολα στην εφαρμογή τους. Θα δούμε επίσης τον παράγοντα ισορροπίας και τις περιστροφές που απαιτούνται για να γίνει αυτό ένα ισορροπημένο δυαδικό δέντρο. Τέλος, θα κωδικοποιήσουμε το δέντρο AVL στην Java.

1. Τι είναι το AVL Tree;

Το δέντρο AVL πήρε το όνομά του από τους εφευρέτες του, Adelson-Velsky και Landis. Ανακάλυψαν το δέντρο AVL το 1962. Μπορούμε να ορίσουμε το δέντρο AVL ως ένα ισορροπημένο δυαδικό δέντρο του οποίου το ύψος είναι ισορροπημένο. Στο δέντρο AVL, κάθε κόμβος σχετίζεται με a παράγοντας ισορροπίας και το δέντρο λέγεται ότι είναι ισορροπημένο εάν ο συντελεστής ισορροπίας κάθε κόμβου του δέντρου AVL είναι μεταξύ -1 και 1. Εάν ο παράγοντας ισορροπίας δεν είναι σε αυτό το εύρος, τότε το δέντρο δεν είναι ισορροπημένο και πρέπει να εξισορροπηθεί μέσω περιστροφών (αργότερα σε αυτό το άρθρο).

Έτσι, όπως ίσως μαντέψατε, η βασική ιδιότητα του δέντρου AVL είναι να σταματήσει ένα δέντρο από το να γίνει λοξό. Ένα λοξό δέντρο έχει χρονική πολυπλοκότητα στη χειρότερη περίπτωση για λειτουργίες δέντρων, π.χ. O(n). Έτσι, διατηρώντας το δέντρο ισορροπημένο, το δέντρο AVL διασφαλίζει ότι οι χρονικές πολυπλοκότητες στη χειρότερη περίπτωση για τις λειτουργίες δέντρου θα είναι O(log n)όπου n είναι ο αριθμός των κόμβων στο δέντρο.

2. Συντελεστής ισορροπίας στο δέντρο AVL

Για να υπολογίσουμε τον συντελεστή ισορροπίας του κόμβου N του δέντρου, χρησιμοποιούμε τον ακόλουθο τύπο:

Balance Factor (N) = height (left(N)) - height (right(N))
  • Συντελεστής ισορροπίας 1 σημαίνει ότι το αριστερό υποδέντρο είναι υψηλότερο από το δεξί υποδέντρο κατά 1 επίπεδο.
  • Συντελεστής ισορροπίας 0 σημαίνει ότι το ύψος του αριστερού υποδέντρου και του δεξιού υποδέντρου είναι ίσα.
  • Συντελεστής ισορροπίας -1 σημαίνει ότι το δεξί υποδέντρο είναι υψηλότερο από το αριστερό υποδέντρο κατά 1 επίπεδο.

Εδώ είναι το αντικείμενο Node για το δέντρο μας

public class AVLNode {

    AVLNode left, right;
    int data;
    int height;

    public AVLNode() {
        left = null;
        right = null;
        data = 0;
        height = 0;
    }

    public AVLNode(int n) {
        left = null;
        right = null;
        data = n;
        height = 0;
    }
}

AVL Tree Structure

public class AVLTree {
    private AVLNode root;
    public AVLTree() {
        root = null;
    }


    /**
     *
     * @param avlNode
     * @return
     */
    private int height(AVLNode avlNode) {
        return avlNode == null ? -1 : avlNode.height;
    }

    /**
     *
     * @param lHeight
     * @param rHeight
     * @return
     */
    private int max(int lHeight, int rHeight) {
        return lHeight > rHeight ? lHeight : rHeight;
    }

    /**
     *
     * @param data
     */
    public void insert(int data) {
            root = insert(data, root);
        }

        ……….
}

3. Πολυπλοκότητα χρόνου και χώρου

Πολυπλοκότητα χρόνου/χώρου Μέση τιμή Κατισχύω
Εισάγετε O(log n) O(log n)
Διαγράφω O(log n) O(log n)
Αναζήτηση O(log n) O(log n)
Χώρος O(n) O(n)
Πολυπλοκότητα χρόνου και χώρου:

Διαφημίσεις

4. Πώς να εξισορροπήσετε ένα δέντρο AVL

Κάθε φορά που προσθέτουμε έναν νέο κόμβο στο δέντρο AVL ή διαγράφουμε έναν κόμβο από αυτό, ελέγχει τον παράγοντα ισορροπίας του κόμβου. Σε περίπτωση που ο συντελεστής ισορροπίας είναι μεγαλύτερος από 1 ή λιγότερο από -1το δέντρο θα εξισορροπηθεί ξανά. Υπάρχουν 4 λειτουργίες για την εξισορρόπηση ενός δέντρου AVL:

  1. Δεξιά περιστροφή.
  2. Αριστερή Περιστροφή.
  3. Περιστροφή αριστερά-δεξιά.
  4. Περιστροφή δεξιά-αριστερά

4.1. Δεξιά περιστροφή

Θα ξεκινήσουμε πρώτα με τη σωστή περιστροφή. ας πούμε ότι έχουμε ένα δυαδικό δέντρο αναζήτησης με το Α ως κόμβο ρίζας και B είναι το αριστερό παιδί του A και C είναι το αριστερό παιδί του B. Αυτό σημαίνει ότι A>B>C το οποίο είναι σωστό σύμφωνα με τις ιδιότητες του δέντρου δυαδικής αναζήτησης. Για τη σωστή περιστροφή, πρέπει να περιστρέψουμε το A με τέτοιο τρόπο που A>B>C επιμένει. Μετά τη σωστή περιστροφή, το νέο δέντρο θα έχει το Β ως κόμβο ρίζας και A είναι το αριστερό παιδί του B και C είναι το σωστό παιδί του Β και έχουμε ακόμα A>B>C

Δέντρο AVL
Δεξιά περιστροφή AVL Tree

Εδώ είναι το απόσπασμα κώδικα για να εκτελέσετε τη σωστή περιστροφή σε ένα δέντρο AVL.

private AVLNode rightRotation(AVLNode avlNode) {
    AVLNode node = avlNode.right;
    avlNode.right = node.left;
    node.left = avlNode;
    avlNode.height = max(height(avlNode.left), height(avlNode.right)) + 1;
    node.height = max(height(node.right), avlNode.height) + 1;
    return node;
}

4.2. Αριστερή Περιστροφή

Θα δούμε τώρα την αριστερή περιστροφή. ας πούμε ότι έχουμε ένα δυαδικό δέντρο αναζήτησης με το Α ως κόμβο ρίζας και το Β είναι το σωστό παιδί του Α και το C είναι το σωστό παιδί του Β. Αυτό σημαίνει ότι A<B<C το οποίο είναι σωστό σύμφωνα με τις ιδιότητες BST. Για την αριστερή περιστροφή, πρέπει να περιστρέψουμε το ΕΝΑ με τέτοιο τρόπο που A<B<C επιμένει. Μετά την αριστερή περιστροφή, το νέο δέντρο θα έχει το Β ως κόμβο ρίζας και ο κόμβος Α είναι το αριστερό παιδί του Β και το Γ είναι το δεξί παιδί του Β και έχουμε ακόμα A<B<C.

Δέντρο AVL αριστερής περιστροφής
AVL Tree Left Rotation
private AVLNode leftRotation(AVLNode avlNode) {
    AVLNode k1 = avlNode.left;
    avlNode.left = k1.right;
    k1.right = avlNode;
    avlNode.height = max(height(avlNode.left), height(avlNode.right)) + 1;
    k1.height = max(height(k1.left), avlNode.height) + 1;
    return k1;
}

4.3. Περιστροφή αριστερά-δεξιά

Η περιστροφή Αριστερά-Δεξιά ή διπλή περιστροφή είναι μια προηγμένη και σύνθετη έκδοση της απλής περιστροφής, όπως η αριστερή περιστροφή. Σε αυτήν την περιστροφή, εκτελούμε μια αριστερή περιστροφή ακολουθούμενη από μια δεξιά περιστροφή. Ας καταλάβουμε πώς να το εκτελέσουμε με το ακόλουθο παράδειγμα:

Περιστροφή αριστερά-δεξιά

Απόσπασμα κώδικα για περιστροφή αριστερά-δεξιά

Διαφημίσεις

private AVLNode leftRightRotation(AVLNode avlNode) {
    avlNode.left = rightRotation(avlNode.left);
    return leftRotation(avlNode);
}

4.4. Περιστροφή δεξιά-αριστερά

Στην Περιστροφή Δεξιά-Αριστερά, εκτελούμε μια δεξιά περιστροφή ακολουθούμενη από μια αριστερή περιστροφή. Ας καταλάβουμε πώς να το εκτελέσουμε με τη βοήθεια του παρακάτω παραδείγματος.

Περιστροφή αριστερά-δεξιά

Διαφημίσεις

private AVLNode rightLeftRotation(AVLNode avlNode) {
    avlNode.right = leftRotation(avlNode.right);
    return rightRotation(avlNode);
}

5. Εισαγάγετε έναν κόμβο στη δέντρο AVL

Για να εισαγάγουμε έναν νέο κόμβο, θα βρούμε την κατάλληλη θέση για αυτόν. Έτσι, θα ξεκινήσουμε με τον ριζικό κόμβο και θα συγκρίνουμε την τιμή του με τα ριζικά δεδομένα. Αν είναι μεγαλύτερο, θα πάμε δεξιά, ή αλλιώς θα πάμε αριστερά. Μόλις βρούμε τον γονικό κόμβο, θα προσθέσουμε αυτόν τον νέο κόμβο σύμφωνα με την τιμή του.

Αφού το κάνουμε αυτό, θα έχουμε ακόμα το BST, ωστόσο μπορεί να μην είναι δέντρο AVL, επομένως, θα ελέγξουμε τον παράγοντα ισορροπίας και με βάση την τιμή του (>1 ή <-1), θα εξισορροπήσουμε ξανά το BST για να το κάνουμε AVL Tree. Η χρονική πολυπλοκότητα του ένθετου είναι συνάρτηση του ύψους του δέντρου. Για το ισορροπημένο δέντρο, η χειρότερη χρονική πολυπλοκότητα θα ήταν O(log(N)).

Δεν επιτρέπεται διπλό κλειδί στην εισαγωγή δέντρου AVL

6. Διαγράψτε έναν Κόμβο

Παρόμοια με αυτό που κάναμε για να εισαγάγουμε έναν κόμβο σε ένα δέντρο AVL, και εδώ θα αναζητήσουμε πρώτα το στοιχείο προς διαγραφή. Μόλις το βρούμε, θα διαγράψουμε τον κόμβο. Αφού το κάνουμε αυτό, θα έχουμε ακόμα το BST, ωστόσο μπορεί να μην είναι δέντρο AVL, επομένως, θα ελέγξουμε τον παράγοντα ισορροπίας και με βάση την τιμή του (>1 ή <-1), θα εξισορροπήσουμε ξανά το BST για να το κάνουμε AVL Tree.

Η χρονική πολυπλοκότητα του ένθετου είναι συνάρτηση του ύψους του δέντρου. Για το ισορροπημένο δέντρο, η χειρότερη χρονική πολυπλοκότητα θα ήταν O(log(N)).

7. AVL Tree σε Java

Τέλος, ας δούμε πώς να εφαρμόσουμε ένα δέντρο AVL στην Java.

package com.javadevjournal.ds.tree.avl;

//AVL Tree Node
class AVLNode {

    AVLNode left, right;
    int data;
    int height;

    public AVLNode() {
        left = null;
        right = null;
        data = 0;
        height = 0;
    }

    public AVLNode(int n) {
        left = null;
        right = null;
        data = n;
        height = 0;
    }
}


// AVL Tree Class
package com.javadevjournal.ds.tree.avl;

class AVLTree {
    private AVLNode root;
    public AVLTree() {
        root = null;
    }


    /**
     *
     * @param avlNode
     * @return
     */
    private int height(AVLNode avlNode) {
        return avlNode == null ? -1 : avlNode.height;
    }

    /**
     *
     * @param lHeight
     * @param rHeight
     * @return
     */
    private int max(int lHeight, int rHeight) {
        return lHeight > rHeight ? lHeight : rHeight;
    }

    /**
     *
     * @param data
     */
    public void insert(int data) {
        root = insert(data, root);
    }


    /**
     *
     * @param data
     * @param avlNode
     * @return
     */
    private AVLNode insert(int data, AVLNode avlNode) {
        if (avlNode == null)
            avlNode = new AVLNode(data);
        else if (data < avlNode.data) {
            avlNode.left = insert(data, avlNode.left);
            if (height(avlNode.left) - height(avlNode.right) == 2)
                if (data < avlNode.left.data)
                    avlNode = leftRotation(avlNode);
                else
                    avlNode = leftRightRotation(avlNode);
        } else if (data > avlNode.data) {
            avlNode.right = insert(data, avlNode.right);
            if (height(avlNode.right) - height(avlNode.left) == 2)
                if (data > avlNode.right.data)
                    avlNode = rightRotation(avlNode);
                else
                    avlNode = rightLeftRotation(avlNode);
        } else
        ; // Duplicate; do nothing
        avlNode.height = max(height(avlNode.left), height(avlNode.right)) + 1;
        return avlNode;
    }

    /**
     *
     * @param avlNode
     * @return
     */
    private AVLNode leftRotation(AVLNode avlNode) {
        AVLNode k1 = avlNode.left;
        avlNode.left = k1.right;
        k1.right = avlNode;
        avlNode.height = max(height(avlNode.left), height(avlNode.right)) + 1;
        k1.height = max(height(k1.left), avlNode.height) + 1;
        return k1;
    }


    /**
     *
     * @param avlNode
     * @return
     */
    private AVLNode rightRotation(AVLNode avlNode) {
        AVLNode node = avlNode.right;
        avlNode.right = node.left;
        node.left = avlNode;
        avlNode.height = max(height(avlNode.left), height(avlNode.right)) + 1;
        node.height = max(height(node.right), avlNode.height) + 1;
        return node;
    }
    /**
     * left-right rotation
     * @param avlNode
     * @return
     */
    private AVLNode leftRightRotation(AVLNode avlNode) {
        avlNode.left = rightRotation(avlNode.left);
        return leftRotation(avlNode);
    }

    /**
     * right-left rotation
     * @param avlNode
     * @return
     */
    private AVLNode rightLeftRotation(AVLNode avlNode) {
        avlNode.right = leftRotation(avlNode.right);
        return rightRotation(avlNode);
    }

    /**
     *
     * @return
     */
    public int countNodes() {
        return countNodes(root);
    }

    /**
     *
     * @param avlNode
     * @return
     */
    private int countNodes(AVLNode avlNode) {
        if (avlNode == null)
            return 0;
        else {
            int l = 1;
            l += countNodes(avlNode.left);
            l += countNodes(avlNode.right);
            return l;
        }
    }

    /**
     *
     * @param data
     * @return
     */
    public boolean search(int data) {
        return search(root, data);
    }

    /**
     *
     * @param avlNode
     * @param data
     * @return
     */
    private boolean search(AVLNode avlNode, int data) {
        boolean found = false;
        while ((avlNode != null) && !found) {
            int rval = avlNode.data;
            if (data < rval)
                avlNode = avlNode.left;
            else if (data > rval)
                avlNode = avlNode.right;
            else {
                found = true;
                break;
            }
            found = search(avlNode, data);
        }
        return found;
    }

    /**
     *
     */
    public void inorder() {
        inorder(root);
    }

    /**
     *
     * @param avlNode
     */
    private void inorder(AVLNode avlNode) {
        if (avlNode != null) {
            inorder(avlNode.left);
            System.out.print(avlNode.data + " ");
            inorder(avlNode.right);
        }
    }
}

// Helper class to run the AVL code
package com.javadevjournal.ds.tree.avl;

import java.util.Scanner;

public class AVLTreeHelper {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        AVLTree avlTree = new AVLTree();

        char ch;
        do {
            System.out.println("\nAVLTree Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. search");
            System.out.println("3. count nodes");
            int choice = scanner.nextInt();
            switch (choice) {
                case 1:
                    System.out.println("Enter integer element to insert");
                    avlTree.insert(scanner.nextInt());
                    break;
                case 2:
                    System.out.println("Enter integer element to search");
                    System.out.println("Search result : " + avlTree.search(scanner.nextInt()));
                    break;
                case 3:
                    System.out.println("Nodes = " + avlTree.countNodes());
                    break;
                default:
                    System.out.println("Wrong Entry \n ");
                    break;
            }

            System.out.print("\nIn order : ");
            avlTree.inorder();

            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scanner.next().charAt(0);
        } while (ch == 'Y' || ch == 'y');
    }
}

Περίληψη

Σε αυτό το άρθρο, καταλάβαμε ότι τι είναι ένα δέντρο AVL, γιατί είναι τόσο ιδιαίτερο. Έχουμε μάθει επίσης τον παράγοντα ισορροπίας του δέντρου AVL. Έχουμε δει επίσης και τους 4 τύπους υποστηριζόμενων περιστροφών με παραδείγματα. Στο τέλος, είδαμε κώδικα για εισαγωγή, διαγραφή και επανεξισορρόπηση του δέντρου AVL. Τέλος, είδαμε τον πλήρη κώδικα ενός δέντρου AVL. Ο πηγαίος κώδικας για αυτό το άρθρο είναι διαθέσιμος στην ιστοσελίδα μας Αποθετήριο GitHub.

Schreibe einen Kommentar