Επεξήγηση εισαγωγής, περιστροφής και ισορροπίας δέντρου AVL

Τι είναι το δέντρο AVL;

Ένα δέντρο AVL είναι ένας δευτερεύων τύπος δέντρου δυαδικής αναζήτησης. Ονομάστηκαν από τους εφευρέτες του Adelson, Velskii και Landis, τα δέντρα AVL έχουν την ιδιότητα της δυναμικής αυτο-εξισορρόπησης επιπλέον όλων των ιδιοτήτων που εκτίθενται από δυαδικά δέντρα αναζήτησης.

Το BST είναι μια δομή δεδομένων που αποτελείται από κόμβους. Διαθέτει τις ακόλουθες εγγυήσεις:

  1. Κάθε δέντρο έχει έναν ριζικό κόμβο (στην κορυφή).
  2. Ο ριζικός κόμβος έχει μηδενικούς, έναν ή δύο θυγατρικούς κόμβους.
  3. Κάθε θυγατρικός κόμβος έχει μηδέν, έναν ή δύο θυγατρικούς κόμβους και ούτω καθεξής.
  4. Κάθε κόμβος έχει έως και δύο παιδιά.
  5. Για κάθε κόμβο, οι αριστεροί απόγονοί του είναι μικρότεροι από τον τρέχοντα κόμβο, ο οποίος είναι μικρότερος από τους σωστούς απογόνους.

Τα δέντρα AVL έχουν μια επιπλέον εγγύηση:

  1. Η διαφορά μεταξύ του βάθους του δεξιού και του αριστερού υποδένδρου δεν μπορεί να είναι περισσότερες από μία. Προκειμένου να διατηρηθεί αυτή η εγγύηση, η εφαρμογή ενός AVL θα περιλαμβάνει έναν αλγόριθμο για την εξισορρόπηση του δέντρου κατά την προσθήκη ενός πρόσθετου στοιχείου που θα ενοχλούσε αυτήν την εγγύηση.

Τα δέντρα AVL έχουν τη χειρότερη περίπτωση αναζήτησης, εισαγωγής και διαγραφής χρόνου του O (log n).

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

AVL Tree Right Rotation

Αριστερή περιστροφή

AVL Tree Left Rotation

Διαδικασία εισαγωγής AVL

Θα κάνετε μια εισαγωγή παρόμοια με μια κανονική εισαγωγή δέντρου δυαδικής αναζήτησης. Μετά την εισαγωγή, διορθώνετε την ιδιότητα AVL χρησιμοποιώντας περιστροφές αριστερά ή δεξιά.

  • Εάν υπάρχει ανισορροπία στο αριστερό παιδί του δεξιού υποδέντρου, τότε εκτελείτε περιστροφή αριστερά-δεξιά.
  • Εάν υπάρχει ανισορροπία στο αριστερό παιδί του αριστερού υποδέντρου, τότε εκτελείτε μια δεξιά περιστροφή.
  • Εάν υπάρχει ανισορροπία στο δεξί παιδί του δεξιού υποδέντρου, τότε εκτελείτε μια αριστερή περιστροφή.
  • Εάν υπάρχει ανισορροπία στο δεξί παιδί του αριστερού υποδέντρου, τότε εκτελείτε περιστροφή δεξιά-αριστερά.

Ένα δέντρο AVL είναι ένα δέντρο δυαδικής αναζήτησης αυτο-εξισορρόπησης. Ένα δέντρο AVL είναι ένα δέντρο δυαδικής αναζήτησης που έχει τις ακόλουθες ιδιότητες: -> Τα δευτερεύοντα δέντρα κάθε κόμβου διαφέρουν σε ύψος το πολύ κατά ένα. -> Κάθε δευτερεύον δέντρο είναι δέντρο AVL.

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

Περιστροφή δέντρων AVL

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

Οι λειτουργίες περιστροφής χρησιμοποιούνται για να ισορροπήσουν ένα δέντρο. Υπάρχουν τέσσερις περιστροφές και ταξινομούνται σε δύο τύπους:

Μονή αριστερή περιστροφή (περιστροφή LL)

Στην περιστροφή LL κάθε κόμβος μετακινεί μία θέση προς τα αριστερά από την τρέχουσα θέση.

Μονή δεξιά περιστροφή (περιστροφή RR)

Στην περιστροφή RR κάθε κόμβος μετακινεί μία θέση προς τα δεξιά από την τρέχουσα θέση.

Αριστερή δεξιά περιστροφή (περιστροφή LR)

Η περιστροφή LR είναι συνδυασμός περιστροφής απλής αριστεράς ακολουθούμενης από περιστροφή μονής δεξιάς. Στην περιστροφή LR, πρώτα κάθε κόμβος μετακινείται μία θέση προς τα αριστερά και μία θέση προς τα δεξιά από την τρέχουσα θέση.

Περιστροφή δεξιού αριστερού (περιστροφή RL)

Η περιστροφή RL είναι συνδυασμός περιστροφής μονής δεξιάς ακολουθούμενης από περιστροφή μονού αριστερού. Στην περιστροφή RL, πρώτα κάθε κόμβος μετακινεί μία θέση προς τα δεξιά και μία θέση προς τα αριστερά από την τρέχουσα θέση.

Ανάλυση χρόνου των δέντρων AVL

Το δέντρο AVL είναι δέντρο δυαδικής αναζήτησης με πρόσθετη ιδιότητα που η διαφορά μεταξύ ύψους αριστερού δευτερεύοντος δέντρου και δεξιού υποδέντρου οποιουδήποτε κόμβου δεν μπορεί να είναι μεγαλύτερη από 1.

Μέσος αλγόριθμος Χειρότερη περίπτωση: Διάστημα:, O(n)Ώρα:O(n)

Εφαρμογή των δέντρων AVL

Τα δέντρα AVL είναι ευεργετικά στις περιπτώσεις όπου σχεδιάζετε κάποια βάση δεδομένων όπου οι εισαγωγές και οι διαγραφές δεν είναι τόσο συχνές, αλλά πρέπει συχνά να αναζητάτε τα αντικείμενα που υπάρχουν εκεί.