09-03-2008 (19:12)
από Aris -
Αλλαγή σειράς 19 από:
σε:
Πρόσθεση σειρών 23-24:
09-03-2008 (18:58)
από Aris -
Πρόσθεση σειρών 17-22:
Ένα δέντρο βαθμού @@d@@ και ύψους @@h@@ μπορεί να έχει το πολύ
(:eqn:) [=
sum_(i=0)^(h-1)=(d^h-1)/(d-1)
=]
09-03-2008 (18:51)
από Aris -
Αλλαγή σειρών 11-12 από:
σε:
:'''Βάθος''':Το μέγιστο επίπεδο των κόμβων ενός δέντρου λέγεται βάθος ή ύψος του δέντρου.
:'''Υποδέντρο''':Υποδέντρο ονομάζεται το δέντρο που σχηματίζεται αν ως ρίζα ληφθεί οποιοσδήποτε κόμβος.
09-03-2008 (18:48)
από Aris -
Πρόσθεση σειρών 3-12:
'''Δέντρο''' είναι ένα σύνολο ''κόμβων'' που συνδέονται με ''ακμές''. Υπάρχει ένας μόνο κόμβος που ονομάζεται ρίζα και στον οποίο δεν καταλήγουν, αλλά μόνο ξεκινούν ακμές. Από κάθε κόμβο μπορούν να ξεκινήσουν καμία, μία ή περισσότερες ακμές. Σε κάθε κόμβο (εκτός της ρίζας) καταλήγει μία μόνο ακμή.
:'''Πατέρας - Παιδί''':Ένας κόμβος @@α@@ είναι ο ''πατέρας'' των κόμβων @@β@@ και @@γ@@, όταν από τον @@α@@ αρχίζουν ακμές που καταλήγουν στους @@β@@ και @@γ@@. Αντίστοιχα, οι @@β@@ και @@γ@@ είναι τα ''παιδιά'' του @@α@@. Η ορολογία αυτή επεκτείνεται προς τα πάνω ή κάτω με παππούδες και εγγονούς και γενικότερα προγόνους και απογόνους. Οι κόμβοι που έχουν παιδιά ονομάζονται και '''''εσωτερικοί''''' ή '''''μη τερματικοί''''' ή '''''κλαδιά'''''. Οι κόμβοι που δεν έχουν παιδιά ονομάζονται '''''τερματικοί''''' ή '''''φύλλα'''''.
:'''Βαθμός Κόμβου - Δεντρου''':''Βαθμός'' ενός ''κόμβου'' είναι ο αριθμός των παιδιών του. ''Βαθμός'' ενός ''δέντρου'' είναι ο μέγιστος από τους βαθμούς των κόμβων του.
:'''Επίπεδο''':Επίπεδο ενός κόμβου είναι ο αριθμός των προγόνων του μέχρι τη ρίζα συν 1.
:'''Βάθος'''
28-02-2008 (18:27)
από Aris -
Αλλαγή σειρών 1-446 από:
%define=frame block bgcolor=#ddddff border="1px dashed blue"%
! AVL Δέντρα (Ισορροπημένα)
Ένα δέντρο AVL είναι ένας ειδικός τύπος δυαδικού δέντρου που είναι πάντα "μερικώς" ισορροπημένο. Το κριτήριο που χρησιμοποιείται για να καθορίσει το βαθμό ισορροπίας είναι η διαφορά μεταξύ των υψών των υποδέντρων κάθε κόμβου. Το κριτήριο, λοιπόν, ισορροπίας είναι το ακόλουθο:
->Ένα δέντρο είναι ''ισορροπημένο'' αν και μόνο αν {+για κάθε+} κόμβο η διαφορά του ύψους των δύο υποδέντρων του διαφέρει το πολύ κατά 1 (απόλυτη τιμή).
Τη διαφορά αυτή, εδώ, τη συμβολίζουμε με:
>>center<<
B(x)=H'_R_'-H'_L_'
>><<
->όπου '''x''' ο κόμβος (π.χ. a, b, c ή 5, 2, 7 κλπ)\\
'''H'_R_'''' το ύψος του δεξιού υποδέντρου του κόμβου, και\\
'''H'_L_'''' το ύψος του αριστερού υποδέντρου
Η τιμή αυτή μπορεί να είναι -1, 0 ή 1. Τιμή -1 σημαίνει ότι το αριστερό υποδέντρο έχει μεγαλύτερο ύψος από το δεξί, η τιμή 0 ότι τα δύο υποδέντρα έχουν το ίδιο ύψος και η τιμή 1 ότι το δεξί υποδέντρο έχει μεγαλύτερο ύψος.
Αν η ισορροπία ενός κόμβου γίνει -2 ή 2, αυτό σημαίνει ότι ο κόμβος χρειάζεται εξισορρόπηση. Αυτό επιτυγχάνεται κάνοντας τις κατάλληλες [[#Rotations | περιστροφές]].
Η εισαγωγή/διαγραφή κόμβων γίνεται όπως στα δυαδικά δέντρα. Αν η ενέργεια διαταράξει την ισορροπία κόμβων πρέπει αυτή να αποκατασταθεί. Η αποκατάσταση γίνεται κάνοντας περιστροφή των κόμβων των οποίων η ισορροπία διαταράχθηκε. Πριν δούμε, λοιπόν, την εισαγωγή και τη διαγραφή, θα δούμε πρώτα τις δυνατές περιστροφές.
!! [[#Rotations]]Περιστροφές
!!! [[#LL]]Απλή Αριστερή Περιστροφή (LL)
Έχουμε το παρακάτω τμήμα ενός δέντρου.
[[#Figure1]]
%frame%[@
a B(a)=1-0 => B(a)=1
\
b B(b)=0
@]
Σχήμα 1
Αν γίνει εισαγωγή κόμβου ως δεξί παιδί του @@b@@, το δέντρο γίνεται:
%frame%[@
a B(a)=2-0 => B(a)=2
\
b B(b)=1-0 => B(c)=1
\
c B(c)=0
@]
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@a@@ η οποία λύνεται με τα παρακάτω βήματα:
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Το αριστερό παιδί του κόμβου @@b@@ γίνεται δεξί παιδί του κόμβου @@a@@\\
Σε αυτή την περίπτωση δεν υπάρχει αριστερό παιδί στον @@b@@
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@b@@
Έτσι, το δέντρο γίνεται:
%frame%[@
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(b)=0
@]
Γενικεύοντας την περίπτωση, μπορούμε να πούμε ότι [[#LL | απλή αριστερή περιστροφή]] έχουμε όταν η ισορροπία του "παππού" του νέου κόμβου (@@c@@ στο παράδειγμα), γίνει 2 και η ισορροπία του "πατέρα" του νέου κόμβου γίνει 1.
Σε περίπτωση που η εισαγωγή κόμβου στο [[#Figure1 | σχήμα 1]] γίνει αριστερό παιδί του @@b@@, τότε έχουμε την περίπτωση της [[#LR | Αριστερής - Δεξιάς Περιστροφής]].
!!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
Ας, υποθέσουμε ότι έχουμε το παρακάτω τμήμα ενός δέντρου.
[[#Figure2]]
%frame%[@
c B(c)=0-1 => B(c)=-1
/
b B(b)=0
@]
Σχήμα 2
Αν γίνει εισαγωγή κόμβου ως αριστερό παιδί του κόμβου @@b@@, έχουμε το παρακάτω δέντρο.
%frame%[@
c B(c)=0-2 => B(c)=-2
/
b B(b)=0-1 => B(b)=-1
/
a B(a)=0
@]
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@c@@ η οποία λύνεται με τα παρακάτω βήματα
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@\\
Σε αυτή την περίπτωση δεν έχουμε αριστερό παιδί του κόμβου @@b@@
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
Έτσι, το δέντρο γίνεται:
%frame%[@
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(c)=0
@]
Γενικεύοντας και εδώ την περίπτωση, μπορούμε να πούμε ότι [[#RR | απλή δεξιά περιστροφή]] έχουμε όταν η ισορροπία του "παππού" του νέου κόμβου (@@c@@ στο παράδειγμα), γίνει -2 και η ισορροπία του "πατέρα" του νέου κόμβου γίνει -1.
Σε περίπτωση που η εισαγωγή κόμβου στο [[#Figure2 | σχήμα 2]] γίνει δεξί παιδί του @@b@@, τότε έχουμε την περίπτωση της [[#RL | Δεξιάς - Αριστερής Περιστροφής]].
!!! [[#LR]]Αριστερή - Δεξιά Περιστροφή (ή "Διπλή Αριστερή")
Μερικές φορές η [[#LL | απλή αριστερή περιστροφή]] δεν είναι αρκετή για να αποκαταστήσει την ισορροπία του δέντρου. Ας δούμε την παρακάτω περίπτωση.
[[#Figure3]]
%frame%[@
a Β(a)=1-0 => B(a)=1
\
c B(c)=0
@]
Σχήμα 3
Το δέντρο είναι ισορροπημένο. Η εισαγωγή ενός κόμβου ως δεξί παιδιού του κόμβου @@c@@ οδηγεί στην περίπτωση της [[#LL | απλής αριστερής περιστροφής]]. Τι γίνεται όμως με εισαγωγή ενός κόμβου που θα γίνει αριστερό παιδί του @@c@@. Σ' αυτή την περίπτωση έχουμε το παρακάτω σχήμα.
%frame%[@
a Β(a)=2-0 => B(a)=2
\
c B(c)=0-1 => B(c)=-1
/
b
@]
Αυτό το δέντρο δεν είναι ισορροπημένο. Η ισορροπία του @@a@@ ("παππού" του @@b@@) είναι θετική και ίση με 2. Αν δοκιμάσουμε να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]], ακολουθούμε τα γνωστά βήματα και:
# Ο κόμβος @@c@@ γίνεται η νέα ρίζα
# Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@c@@
Έτσι, το δέντρο γίνεται:
%frame%[@
c B(c)=0-2 => B(c)=-2
/
a B(a)=1-0 => B(a)=1
\
b B(b)=0
@]
Βλέπουμε ότι η περιστροφή δεν έλυσε το πρόβλημα. Μία προσπάθεια [[#RR | απλής δεξιάς περιστροφής]] (ισορροπία "παππού" -2) δε θα λύσει πάλι το πρόβλημα. Θα φτάσουμε στην προηγούμενη κατάσταση.
Η διαδικασία που ακολουθούμε σε αυτή την περίπτωση είναι η εξής:
* Κάνουμε [[#RR | απλή δεξιά περιστροφή]] στο υποδέντρο με ρίζα τον κόμβο @@c@@
%frame%[@
a Β(a)=2-0 => B(a)=2
\
b B(c)=1-0 => B(c)=1
\
c B(c)=0
@]
Βλέπουμε ότι έχουμε @@B(a)=2@@ και @@B(b)=1@@, άρα, αυτό που έχουμε είναι να
* Κάνουμε [[#LL | απλή αριστερή περιστροφή]] στο δέντρο με ρίζα τον κόμβο @@a@@
%frame%[@
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(c)=0
@]
Βλέπουμε ότι αυτή η διαδικασία αποκαθιστά την ισορροπία. Γενικεύοντας την περίπτωση, αν η ισορροπία του "παππού" του νέου κόμβου είναι 2 και η ισορροπία του "πατέρα" είναι -1, τότε κάνουμε Αριστερή-Δεξιά Περιστροφή.
!!! [[#RL]]Δεξιά - Αριστερή Περιστροφή (ή "Διπλή Δεξιά")
Αυτή η περίπτωση είναι όμοια με την [[#LR | Αριστερή - Δεξιά Περιστροφή]] με την έννοια ότι είναι συμμετρική της. Ας δούμε την παρακάτω περίπτωση.
[[#Figure4]]
%frame%[@
c Β(c)=0-1 => B(c)=-1
/
a B(a)=0
@]
Σχήμα 4
Το δέντρο είναι ισορροπημένο. Η εισαγωγή ενός κόμβου ως αριστρερού παιδιού του κόμβου @@a@@ οδηγεί στην περίπτωση της [[#RR | απλής δεξιάς περιστροφής]]. Με την εισαγωγή ενός κόμβου που θα γίνει δεξί παιδί του @@a@@, έχουμε το παρακάτω σχήμα.
%frame%[@
c B(c)=0-2 => B(c)=-2
/
a B(a)=1-0 => B(a)=1
\
b B(b)=0
@]
Αυτό το δέντρο δεν είναι ισορροπημένο. Η ισορροπία του @@c@@ ("παππού" του @@b@@) είναι αρνητική και ίση με -2. Αν δοκιμάσουμε να κάνουμε μία [[#RR | απλή δεξιά περιστροφή]], ακολουθούμε τα γνωστά βήματα και:
# Ο κόμβος @@a@@ γίνεται η νέα ρίζα
# Το δεξί παιδί του κόμβου @@a@@ γίνεται αριστερό παιδί του κόμβου @@c@@
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@
Έτσι, το δέντρο γίνεται:
%frame%[@
a B(a)=2-0 => B(c)=2
\
c B(a)=0-1 => B(a)=-1
/
b B(b)=0
@]
Βλέπουμε πάλι ότι η περιστροφή δεν έλυσε το πρόβλημα. Επίσης, μία προσπάθεια [[#LL | απλής αριστερής περιστροφής]] (ισορροπία "παππού" 2) δε θα λύσει πάλι το πρόβλημα. Θα φτάσουμε στην προηγούμενη κατάσταση.
Η διαδικασία που ακολουθούμε σε αυτή την περίπτωση είναι η εξής:
* Κάνουμε [[#LL | απλή αριστερή περιστροφή]] στο υποδέντρο με ρίζα τον κόμβο @@a@@
%frame%[@
c Β(c)=0-2 => B(a)=-2
/
b B(b)=0-1 => B(b)=-1
/
a B(a)=0
@]
Βλέπουμε ότι έχουμε @@B(c)=-2@@ και @@B(b)=-1@@, άρα, αυτό που έχουμε είναι να
* Κάνουμε [[#RR | απλή δεξιά περιστροφή]] στο δέντρο με ρίζα τον κόμβο @@c@@
%frame%[@
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(c)=0
@]
Βλέπουμε ότι αυτή η διαδικασία αποκαθιστά την ισορροπία. Γενικεύοντας την περίπτωση, αν η ισορροπία του "παππού" του νέου κόμβου είναι -2 και η ισορροπία του "πατέρα" είναι 1, τότε κάνουμε Δεξιά - Αριστερή Περιστροφή.
!!! Ανακεφαλαίωση
Συγκεντρώνοντας τις παραπάνω παρατηρήσεις, δημιουργούμε τον παρακάτω πίνακα αποφάσεων.
||border=1
||! Ισορροπία ||||! Περιστροφή
||! Παππού ||! Πατέρα || ||
|| 2 || 1 || [[#LL | Απλή Αριστερή]] ||
|| 2 || -1 || [[#LR | Αριστερή - Δεξιά]] ||
|| -2 || -1 || [[#RR | Απλή Δεξιά]] ||
|| -2 || 1 || [[#RL | Δεξιά - Αριστερή]] ||
Στην πραγματικότητα οι περιστροφές είναι δύο. Οι άλλες δύο είναι συμμετρικές αυτών. Αν πάρουμε για παράδειγμα τις δεξιές περιστροφές, τότε έχουμε
* απλή δεξιά με συμμετρική την απλή αριστερή
* δεξιά - αριστερή με συμμετρική την απλή αριστερή
[[#Case1]]
http://users.sch.gr/fergadis/images/RR.jpg
'''(α) Αρχική κατάσταση σε ισορροπία'''
Τα υποδέντρα @@1@@ και @@2@@ του κόμβου @@Α@@ έχουν ύψος h. Το αριστερό υποδέντρο του κόμβου @@Β@@ έχει ύψος @@1+h@@. Το ένα προκύπτει από τον κόμβο @@Α@@. Έτσι, έχουμε:
>>center<<
'''H'_L_'=h+1'''
>><<
Το ύψος του δεξιού υποδέντρου του κόμβου @@Β@@ είναι h. Δηλαδή:
>>center<<
'''H'_R_'=h'''
>><<
Η ισορροπία του κόμβου @@Β@@ είναι:
>>center<<
'''Β(Β)=H'_R_'-H'_L_'=h-(h+1) => B(B)=-1'''
>><<
'''(β) Γίνεται εισαγωγή του κόμβου @@Χ@@'''
Η εισαγωγή γίνεται ως παιδί του υποδέντρου @@1@@ του κόμβου @@Α@@. Αν γίνει εισαγωγή στο υποδέντρο @@2@@, τότε έχουμε την [[#Case2 | περίπτωση 2]].
Στο παραπάνω σχήμα φαίνεται ότι η ισορροπία του κόμβου @@Β@@ γίνεται -2 και του @@Α@@ γίνεται -1. Για την αποκατάσταση της ισορροπίας χρειάζεται μία [[#RR | απλή δεξιά περιστροφή]].
'''(γ) Αποκατάσταση της ισορροπίας'''
Ακολουθώντας τα βήματα έχουμε:
* Ο κόμβος @@Α@@ παίρνει τη θέση του κόμβου @@Β@@
* Το υποδέντρο @@2@@ γίνεται υποδέντρο του κόμβου @@Β@@ (από αριστερό του @@Α@@ γίνεται δεξί του @@Β@@)
* Ο κόμβος @@Β@@ γίνεται δεξί υποδέντρο του κόμβου @@Β@@
[[#Case2]]http://users.sch.gr/fergadis/images/RL.jpg
'''(α) Αρχική κατάσταση'''
Τα υποδέντρα @@1, 2@@ και @@3@@ έχουν ύψος h. Το υποδέντρο @@4@@ έχει ύψος 2h. Αυτό δίνει τιμή ισορροπίας στον κόμβο @@C@@ -1 και στον κόμβο @@Α@@ 1. Ο κόμβος @@Β@@ έχει τιμή 0.
>>center<<
Β(C)=H'_R_'+H'_L_'=2h-(1+2h) => B(C)=-1
B(A)=H'_R_'+H'_L_'=(1+h)-h => B(A)=1
>><<
'''(β) Εισαγωγή του κόμβου Χ'''
Η εισαγωγή του κόμβου Χ μπορεί να γίνει στο υποδέντρο @@2@@ ή @@3@@. Σε όποιο και να γίνει η διαδικασία είναι ίδια.
Οι τιμές στους κόμβους γίνονται:
>>center<<
B(C)=2h-(1+2h+1) => B(C)=-2
B(A)=(1+h+1)-h => B(A)=2
B(B)=-1 (αν η εισαγωγή γίνει στο υποδέντρο 2) ή Β(Β)=1 (αν γίνει στο 3)
>><<
'''(γ) Αποκατάσταση της ισορροπίας'''
Τα βήματα που αποκαταστούν την ισορροπία είναι αυτά της [[#RL | δεξιάς - αριστερής περιστροφής]]. Εδώ μπορούμε να συνοψίσουμε λίγο τα βήματα αυτά, οπότε έχουμε:
* Ο κόμβος @@Β@@ παίρνει τη θέση του κόμβου @@C@@
* Ο κόμβος @@C@@ γίνεται δεξί παιδί του κόμβου @@Β@@
* Το υποδέντρο @@2@@ γίνεται δεξί παιδί του κόμβου @@Α@@
* Το υποδέντρο @@3@@ γίνεται αριστερό παιδί του κόμβου @@C@@
!! Εισαγωγή Κόμβων
Η εισαγωγή του κόμβου γίνεται όπως και στην περίπτωση των δυαδικών δέντρων. Αφού γίνει η εισαγωγή του κόμβου, προχωρούμε προς τα πίσω στους κόμβους από τους οποίους περάσαμε και σε κάθε κόμβο υπολογίζουμε το βαθμό ισορροπία του. Αν έχει διαταραχθεί, κάνουμε τις κατάλληλες περιστροφές.
Η διαδικασία θα γίνει πιο κατανοητή με ένα παράδειγμα.
!! Παράδειγμα
Ας υποθέσουμε ότι έχουμε με τη σειρά τους αριθμούς: @@4, 5, 7, 2, 1, 3, 6@@
* Εισαγωγή @@4@@
>>center<<
http://users.sch.gr/fergadis/images/4.jpg
>><<
* Εισαγωγή @@5@@
>>center<<
http://users.sch.gr/fergadis/images/4-5.jpg
>><<
* Εισαγωγή @@7@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7.jpg
>><<
Εδώ βλέπουμε ότι ο κόμβος @@4@@ έχει τιμή @@2@@ και ο κόμβος @@5@@ 1. Κάνουμε, λοιπόν, μία [[#LL | απλή αριστερή περιστροφή]] για τους κόμβους @@4, 5, 7@@. Έχουμε:
* ο κόμβος @@5@@ γίνεται ρίζα στην θέση του @@4@@
* ο κόμβος @@4@@ γίνεται αριστερό παιδί του κόμβου @@5@@
Έτσι, το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-LL.jpg
>><<
* Εισαγωγή @@2@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2.jpg
>><<
* Εισαγωγή @@1@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1.jpg
>><<
Με αυτή την εισαγωγή, ο κόμβος @@4@@ έχει τιμή -2 και ο κόμβος @@2@@ -1. Κάνουμε, [[#RR | απλή δεξιά περιστροφή]] στους κόμβους @@4, 2, 1@@. Έχουμε:
* ο κόμβος @@2@@ παίρνει τη θέση του κόμβου @@4@@
* ο κόμβος @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-RR.jpg
>><<
* Εισαγωγή @@3@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3.jpg
>><<
Με την εισαγωγή του κόμβου @@3@@, ο κόμβος @@5@@ αποκτά τιμή -2 και ο @@2@@ τιμή 1. Για να αποκαταστήσουμε την ισορροπία πρέπει να κάνουμε μία [[#RL | δεξιά - αριστερή περιστροφή]] στους κόμβους @@5, 2, 4@@.
Πρώτα κάνουμε την αριστερή περιστροφή στους κόμβου @@2@@ και @@4@@.
* ο κόμβος @@4@@ γίνεται ρίζα στη θέση του @@2@@
* το αριστερό παιδί του κόμβου @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
* ο κόμβος @@2@@ γίνεται αριστερό παιδί του κόμβου @@4@@
Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-L.jpg
>><<
Τώρα κάνουμε την δεξιά περιστροφή:
* ο κόμβος @@4@@ γίνεται ρίζα, στη θέση του @@5@@
* ο κόμβος @@5@@ γίνεται δεξί παιδί στον κόμβο @@4@@
Τώρα το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-LR.jpg
>><<
* Εισαγωγή @@6@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6.jpg
>><<
Ο κόμβος @@5@@ έχει τιμή 2 και ο @@7@@ τιμή -1. Για την αποκατάσταση της ισορροπίας πρέπει να κάνουμε μία [[#LR | αριστερή - δεξιά περιστροφή]].
Πρώτα κάνουμε δεξιά περιστροφή στους κόμβους @@7@@ και @@6@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@7@@
* ο κόμβος @@7@@ γίνεται δεξί παιδί του κόμβου @@6@@
Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6-R.jpg
>><<
Τώρα κάνουμε αριστερή περιστροφή στους κόμβους @@5, 6@@ και @@7@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@5@@
* ο κόμβος @@5@@ γίνεται αριστερό παιδί του κόμβου @@6@@.
Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6-RL.jpg
>><<
!! Διαγραφή Κόμβων
Η διαγραφή κόμβων δεν είναι πιο δύσκολη από την εισαγωγή, εκτός από μία περίπτωση όπου απλά πρέπει να προσέξουμε ποιος κόμβος πρέπει να πάρει τη θέση εκείνου που διαγράφηκε. Σε κάθε διαγραφή κόμβου, πρέπει όπως και στην εισαγωγή, να διασχίσουμε το μονοπάτι από τον κόμβο που αντικαθιστά τον διαγραμμένο προς τη ρίζα και να υπολογίσουμε την ισορροπία των κόμβων. Αν βρούμε διαταραχές, τις αντιμετωπίζουμε με τις γνωστές περιστροφές.
Οι βασικές περιπτώσεις διαγραφής κόμβων είναι:
* Ο κόμβος που διαγράφεται είναι τερματικός (δεν έχει παιδιά)
->Σε αυτή την περίπτωση απλά διαγράφουμε τον κόμβο
>>center<<
http://users.sch.gr/fergadis/images/leaf-del.jpg
>><<
* Ο κόμβος έχει ένα παιδί
->Το παιδί παίρνει τη θέση του κόμβου που διαγράφεται
>>center<<
http://users.sch.gr/fergadis/images/parent-1child-del.jpg
>><<
* Ο κόμβος έχει δύο παιδιά
-> To αριστερό παιδί παίρνει τη θέση του κόμβου που διαγράφεται
>>center<<
http://users.sch.gr/fergadis/images/parent-2child-del.jpg
>><<
* Ο κόμβος έχει υποδέντρα
-> Ο πιο δεξιός κόμβος του αριστερού υποδέντρου παίρνει τη θέση του κόμβου που διαγράφεται
>>center<<
http://users.sch.gr/fergadis/images/parent-subtrees1-del.jpg
>><<
>>center<<
http://users.sch.gr/fergadis/images/parent-subtrees2-del.jpg
>><<
σε:
! Ορισμοί
! Ποσοτικά Στοιχεία
! Τύποι Δέντρων
* [[DataStructures.Binary-Tree-Theory | Δυαδικά Δέντρα]]
* [[DataStructures.AVL-Theory | AVL]]
* [[DataStructures.B-Tree-Theory | B - Δέντρα]]
27-02-2008 (22:06)
από Aris -
Αλλαγή σειρών 441-445 από:
http://users.sch.gr/fergadis/images/parent-subtrees-del.jpg
σε:
http://users.sch.gr/fergadis/images/parent-subtrees1-del.jpg
>><<
>>center<<
http://users.sch.gr/fergadis/images/parent-subtrees2-del.jpg
27-02-2008 (21:51)
από Aris -
Πρόσθεση σειρών 433-436:
>>center<<
http://users.sch.gr/fergadis/images/parent-2child-del.jpg
>><<
Αλλαγή σειρών 438-442 από:
-> Ο πιο δεξιός κόμβος του αριστερού υποδέντρου παίρνει τη θέση του κόμβου που διαγράφεται
σε:
-> Ο πιο δεξιός κόμβος του αριστερού υποδέντρου παίρνει τη θέση του κόμβου που διαγράφεται
>>center<<
http://users.sch.gr/fergadis/images/parent-subtrees-del.jpg
>><<
27-02-2008 (21:39)
από Aris -
Αλλαγή σειρών 20-21 από:
Η εισαγωγή/διαγραφή κόμβων γίνεται όπως στα δυαδικά δέντρα. Αν η ενέργεια διαταράξει την ισορροπία κόμβων πρέπει αυτή να αποκατασταθεί. Η αποκατάσταση γίνεται κάνοντας περιστροφή των κόμβων των οποίων η ισορροπία διαταράχθηκε. Πριν δούμε, λοιπόν, τις περιπτώσεις εισαγωγής κόμβου, θα δούμε πρώτα τις δυνατές περιστροφές.
σε:
Η εισαγωγή/διαγραφή κόμβων γίνεται όπως στα δυαδικά δέντρα. Αν η ενέργεια διαταράξει την ισορροπία κόμβων πρέπει αυτή να αποκατασταθεί. Η αποκατάσταση γίνεται κάνοντας περιστροφή των κόμβων των οποίων η ισορροπία διαταράχθηκε. Πριν δούμε, λοιπόν, την εισαγωγή και τη διαγραφή, θα δούμε πρώτα τις δυνατές περιστροφές.
Πρόσθεση σειρών 314-319:
!! Εισαγωγή Κόμβων
Η εισαγωγή του κόμβου γίνεται όπως και στην περίπτωση των δυαδικών δέντρων. Αφού γίνει η εισαγωγή του κόμβου, προχωρούμε προς τα πίσω στους κόμβους από τους οποίους περάσαμε και σε κάθε κόμβο υπολογίζουμε το βαθμό ισορροπία του. Αν έχει διαταραχθεί, κάνουμε τις κατάλληλες περιστροφές.
Η διαδικασία θα γίνει πιο κατανοητή με ένα παράδειγμα.
Διαγραφή σειρών 321-322:
Όλα τα παραπάνω θα γίνουν πιο κατανοητά με ένα παράδειγμα.
Αλλαγή σειρών 409-434 από:
σε:
>><<
!! Διαγραφή Κόμβων
Η διαγραφή κόμβων δεν είναι πιο δύσκολη από την εισαγωγή, εκτός από μία περίπτωση όπου απλά πρέπει να προσέξουμε ποιος κόμβος πρέπει να πάρει τη θέση εκείνου που διαγράφηκε. Σε κάθε διαγραφή κόμβου, πρέπει όπως και στην εισαγωγή, να διασχίσουμε το μονοπάτι από τον κόμβο που αντικαθιστά τον διαγραμμένο προς τη ρίζα και να υπολογίσουμε την ισορροπία των κόμβων. Αν βρούμε διαταραχές, τις αντιμετωπίζουμε με τις γνωστές περιστροφές.
Οι βασικές περιπτώσεις διαγραφής κόμβων είναι:
* Ο κόμβος που διαγράφεται είναι τερματικός (δεν έχει παιδιά)
->Σε αυτή την περίπτωση απλά διαγράφουμε τον κόμβο
>>center<<
http://users.sch.gr/fergadis/images/leaf-del.jpg
>><<
* Ο κόμβος έχει ένα παιδί
->Το παιδί παίρνει τη θέση του κόμβου που διαγράφεται
>>center<<
http://users.sch.gr/fergadis/images/parent-1child-del.jpg
>><<
* Ο κόμβος έχει δύο παιδιά
-> To αριστερό παιδί παίρνει τη θέση του κόμβου που διαγράφεται
* Ο κόμβος έχει υποδέντρα
-> Ο πιο δεξιός κόμβος του αριστερού υποδέντρου παίρνει τη θέση του κόμβου που διαγράφεται
22-02-2008 (19:21)
από Aris -
Διαγραφή σειράς 47:
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@b@@
Αλλαγή σειρών 50-51 από:
σε:
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@b@@
Διαγραφή σειράς 87:
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
Αλλαγή σειρών 90-91 από:
σε:
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
Πρόσθεση σειράς 128:
# Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@
Αλλαγή σειρών 130-131 από:
# Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@
σε:
Διαγραφή σειρών 165-167:
'''Σχόλιο:'''
Στην πραγματικότητα κάνουμε πρώτα μία δεξιά περιστροφή στο υποδέντρο και μία αριστερή στο δέντρο. Το γιατί ονομάζεται "Αριστερή-Δεξιά Περιστροφή" ή "Διπλή Αριστερή", για μένα παραμένει μυστήριο.
Πρόσθεση σειράς 190:
# Το δεξί παιδί του κόμβου @@a@@ γίνεται αριστερό παιδί του κόμβου @@c@@
Αλλαγή σειρών 192-193 από:
# Το δεξί παιδί του κόμβου @@a@@ γίνεται αριστερό παιδί του κόμβου @@c@@
σε:
Διαγραφή σειρών 227-229:
'''Σχόλιο:'''
Το ίδιο με την Αριστερή - Δεξιά Περιστροφή.
Πρόσθεση σειράς 243:
Αλλαγή σειρών 282-289 από:
!! Παράδειγμα
Όλα τα παραπάνω θα γίνουν πιο κατανοητά με ένα παράδειγμα.
Ας υποθέσουμε ότι έχουμε με τη σειρά τους αριθμούς: @@4, 5, 7, 2, 1, 3, 6@@
* Εισαγωγή @@4@@
σε:
'''(α) Αρχική κατάσταση'''
Τα υποδέντρα @@1, 2@@ και @@3@@ έχουν ύψος h. Το υποδέντρο @@4@@ έχει ύψος 2h. Αυτό δίνει τιμή ισορροπίας στον κόμβο @@C@@ -1 και στον κόμβο @@Α@@ 1. Ο κόμβος @@Β@@ έχει τιμή 0.
Αλλαγή σειρών 287-289 από:
http://users.sch.gr/fergadis/images/4.jpg
σε:
Β(C)=H'_R_'+H'_L_'=2h-(1+2h) => B(C)=-1
B(A)=H'_R_'+H'_L_'=(1+h)-h => B(A)=1
Αλλαγή σειρών 291-297 από:
σε:
'''(β) Εισαγωγή του κόμβου Χ'''
Η εισαγωγή του κόμβου Χ μπορεί να γίνει στο υποδέντρο @@2@@ ή @@3@@. Σε όποιο και να γίνει η διαδικασία είναι ίδια.
Οι τιμές στους κόμβους γίνονται:
Αλλαγή σειρών 299-303 από:
http://users.sch.gr/fergadis/images/4-5.jpg
σε:
B(C)=2h-(1+2h+1) => B(C)=-2
B(A)=(1+h+1)-h => B(A)=2
B(B)=-1 (αν η εισαγωγή γίνει στο υποδέντρο 2) ή Β(Β)=1 (αν γίνει στο 3)
Αλλαγή σειρών 305-321 από:
σε:
'''(γ) Αποκατάσταση της ισορροπίας'''
Τα βήματα που αποκαταστούν την ισορροπία είναι αυτά της [[#RL | δεξιάς - αριστερής περιστροφής]]. Εδώ μπορούμε να συνοψίσουμε λίγο τα βήματα αυτά, οπότε έχουμε:
* Ο κόμβος @@Β@@ παίρνει τη θέση του κόμβου @@C@@
* Ο κόμβος @@C@@ γίνεται δεξί παιδί του κόμβου @@Β@@
* Το υποδέντρο @@2@@ γίνεται δεξί παιδί του κόμβου @@Α@@
* Το υποδέντρο @@3@@ γίνεται αριστερό παιδί του κόμβου @@C@@
!! Παράδειγμα
Όλα τα παραπάνω θα γίνουν πιο κατανοητά με ένα παράδειγμα.
Ας υποθέσουμε ότι έχουμε με τη σειρά τους αριθμούς: @@4, 5, 7, 2, 1, 3, 6@@
* Εισαγωγή @@4@@
Αλλαγή σειράς 323 από:
http://users.sch.gr/fergadis/images/4-5-7.jpg
σε:
http://users.sch.gr/fergadis/images/4.jpg
Αλλαγή σειρών 325-329 από:
Εδώ βλέπουμε ότι ο κόμβος @@4@@ έχει τιμή @@2@@ και ο κόμβος @@5@@ 1. Κάνουμε, λοιπόν, μία [[#LL | απλή αριστερή περιστροφή]] για τους κόμβους @@4, 5, 7@@. Έχουμε:
* ο κόμβος @@5@@ γίνεται ρίζα στην θέση του @@4@@
* ο κόμβος @@4@@ γίνεται αριστερό παιδί του κόμβου @@5@@
Έτσι, το δέντρο γίνεται:
σε:
Αλλαγή σειράς 327 από:
http://users.sch.gr/fergadis/images/4-5-7-LL.jpg
σε:
http://users.sch.gr/fergadis/images/4-5.jpg
Αλλαγή σειράς 329 από:
σε:
Αλλαγή σειράς 331 από:
http://users.sch.gr/fergadis/images/4-5-7-2.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7.jpg
Αλλαγή σειρών 333-337 από:
σε:
Εδώ βλέπουμε ότι ο κόμβος @@4@@ έχει τιμή @@2@@ και ο κόμβος @@5@@ 1. Κάνουμε, λοιπόν, μία [[#LL | απλή αριστερή περιστροφή]] για τους κόμβους @@4, 5, 7@@. Έχουμε:
* ο κόμβος @@5@@ γίνεται ρίζα στην θέση του @@4@@
* ο κόμβος @@4@@ γίνεται αριστερό παιδί του κόμβου @@5@@
Έτσι, το δέντρο γίνεται:
Αλλαγή σειράς 339 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-LL.jpg
Αλλαγή σειρών 341-345 από:
Με αυτή την εισαγωγή, ο κόμβος @@4@@ έχει τιμή -2 και ο κόμβος @@2@@ -1. Κάνουμε, [[#RR | απλή δεξιά περιστροφή]] στους κόμβους @@4, 2, 1@@. Έχουμε:
* ο κόμβος @@2@@ παίρνει τη θέση του κόμβου @@4@@
* ο κόμβος @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
Το δέντρο γίνεται:
σε:
Αλλαγή σειράς 343 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-RR.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2.jpg
Αλλαγή σειράς 345 από:
σε:
Αλλαγή σειράς 347 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1.jpg
Αλλαγή σειρών 349-355 από:
Με την εισαγωγή του κόμβου @@3@@, ο κόμβος @@5@@ αποκτά τιμή -2 και ο @@2@@ τιμή 1. Για να αποκαταστήσουμε την ισορροπία πρέπει να κάνουμε μία [[#RL | δεξιά - αριστερή περιστροφή]] στους κόμβους @@5, 2, 4@@.
Πρώτα κάνουμε την αριστερή περιστροφή στους κόμβου @@2@@ και @@4@@.
* ο κόμβος @@4@@ γίνεται ρίζα στη θέση του @@2@@
* το αριστερό παιδί του κόμβου @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
* ο κόμβος @@2@@ γίνεται αριστερό παιδί του κόμβου @@4@@
σε:
Με αυτή την εισαγωγή, ο κόμβος @@4@@ έχει τιμή -2 και ο κόμβος @@2@@ -1. Κάνουμε, [[#RR | απλή δεξιά περιστροφή]] στους κόμβους @@4, 2, 1@@. Έχουμε:
* ο κόμβος @@2@@ παίρνει τη θέση του κόμβου @@4@@
* ο κόμβος @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
Αλλαγή σειράς 355 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-L.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1-RR.jpg
Αλλαγή σειρών 357-362 από:
Τώρα κάνουμε την δεξιά περιστροφή:
* ο κόμβος @@4@@ γίνεται ρίζα, στη θέση του @@5@@
* ο κόμβος @@5@@ γίνεται δεξί παιδί στον κόμβο @@4@@
Τώρα το δέντρο γίνεται:
σε:
Αλλαγή σειράς 359 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-LR.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3.jpg
Αλλαγή σειρών 361-362 από:
σε:
Με την εισαγωγή του κόμβου @@3@@, ο κόμβος @@5@@ αποκτά τιμή -2 και ο @@2@@ τιμή 1. Για να αποκαταστήσουμε την ισορροπία πρέπει να κάνουμε μία [[#RL | δεξιά - αριστερή περιστροφή]] στους κόμβους @@5, 2, 4@@.
Πρώτα κάνουμε την αριστερή περιστροφή στους κόμβου @@2@@ και @@4@@.
* ο κόμβος @@4@@ γίνεται ρίζα στη θέση του @@2@@
* το αριστερό παιδί του κόμβου @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
* ο κόμβος @@2@@ γίνεται αριστερό παιδί του κόμβου @@4@@
Το δέντρο γίνεται:
Αλλαγή σειράς 370 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-L.jpg
Αλλαγή σειρών 373-379 από:
Ο κόμβος @@5@@ έχει τιμή 2 και ο @@7@@ τιμή -1. Για την αποκατάσταση της ισορροπίας πρέπει να κάνουμε μία [[#LR | αριστερή - δεξιά περιστροφή]].
Πρώτα κάνουμε δεξιά περιστροφή στους κόμβους @@7@@ και @@6@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@7@@
* ο κόμβος @@7@@ γίνεται δεξί παιδί του κόμβου @@6@@
Το δέντρο γίνεται:
σε:
Τώρα κάνουμε την δεξιά περιστροφή:
* ο κόμβος @@4@@ γίνεται ρίζα, στη θέση του @@5@@
* ο κόμβος @@5@@ γίνεται δεξί παιδί στον κόμβο @@4@@
Τώρα το δέντρο γίνεται:
Αλλαγή σειράς 379 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6-R.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-LR.jpg
Αλλαγή σειρών 382-386 από:
Τώρα κάνουμε αριστερή περιστροφή στους κόμβους @@5, 6@@ και @@7@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@5@@
* ο κόμβος @@5@@ γίνεται αριστερό παιδί του κόμβου @@6@@.
Το δέντρο γίνεται:
σε:
Πρόσθεση σειρών 384-403:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6.jpg
>><<
Ο κόμβος @@5@@ έχει τιμή 2 και ο @@7@@ τιμή -1. Για την αποκατάσταση της ισορροπίας πρέπει να κάνουμε μία [[#LR | αριστερή - δεξιά περιστροφή]].
Πρώτα κάνουμε δεξιά περιστροφή στους κόμβους @@7@@ και @@6@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@7@@
* ο κόμβος @@7@@ γίνεται δεξί παιδί του κόμβου @@6@@
Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6-R.jpg
>><<
Τώρα κάνουμε αριστερή περιστροφή στους κόμβους @@5, 6@@ και @@7@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@5@@
* ο κόμβος @@5@@ γίνεται αριστερό παιδί του κόμβου @@6@@.
Το δέντρο γίνεται:
>>center<<
22-02-2008 (19:03)
από Aris -
Πρόσθεση σειρών 285-286:
[[#Case2]]http://users.sch.gr/fergadis/images/RL.jpg
22-02-2008 (19:01)
από Aris -
22-02-2008 (19:00)
από Aris -
22-02-2008 (18:23)
από Aris -
22-02-2008 (18:21)
από Aris -
Αλλαγή σειράς 249 από:
σε:
Αλλαγή σειράς 269 από:
'''Β(Β)=H'_R_'-H'_L'=h-(h+1) => B(B)=-1'''
σε:
'''Β(Β)=H'_R_'-H'_L_'=h-(h+1) => B(B)=-1'''
Αλλαγή σειρών 272-274 από:
Γίνεται εισαγωγή του κόμβου @@Χ@@.
σε:
'''(β) Γίνεται εισαγωγή του κόμβου @@Χ@@'''
Η εισαγωγή γίνεται ως παιδί του υποδέντρου @@1@@ του κόμβου @@Α@@. Αν γίνει εισαγωγή στο υποδέντρο @@2@@, τότε έχουμε την [[#Case2 | περίπτωση 2]].
Στο παραπάνω σχήμα φαίνεται ότι η ισορροπία του κόμβου @@Β@@ γίνεται -2 και του @@Α@@ γίνεται -1. Για την αποκατάσταση της ισορροπίας χρειάζεται μία [[#RR | απλή δεξιά περιστροφή]].
'''(γ) Αποκατάσταση της ισορροπίας'''
Ακολουθώντας τα βήματα έχουμε:
* Ο κόμβος @@Α@@ παίρνει τη θέση του κόμβου @@Β@@
* Το υποδέντρο @@2@@ γίνεται υποδέντρο του κόμβου @@Β@@ (από αριστερό του @@Α@@ γίνεται δεξί του @@Β@@)
* Ο κόμβος @@Β@@ γίνεται δεξί υποδέντρο του κόμβου @@Β@@
22-02-2008 (18:05)
από Aris -
Διαγραφή σειρών 10-13:
όπου x ο κόμβος (π.χ. a, b, c ή 5, 2, 7 κλπ)\\
H'_R_' το ύψος του δεξιού υποδέντρου του κόμβου, και\\
H'_L_' το ύψος του αριστερού υποδέντρου
Αλλαγή σειρών 12-19 από:
σε:
->όπου '''x''' ο κόμβος (π.χ. a, b, c ή 5, 2, 7 κλπ)\\
'''H'_R_'''' το ύψος του δεξιού υποδέντρου του κόμβου, και\\
'''H'_L_'''' το ύψος του αριστερού υποδέντρου
Η τιμή αυτή μπορεί να είναι -1, 0 ή 1. Τιμή -1 σημαίνει ότι το αριστερό υποδέντρο έχει μεγαλύτερο ύψος από το δεξί, η τιμή 0 ότι τα δύο υποδέντρα έχουν το ίδιο ύψος και η τιμή 1 ότι το δεξί υποδέντρο έχει μεγαλύτερο ύψος.
Αν η ισορροπία ενός κόμβου γίνει -2 ή 2, αυτό σημαίνει ότι ο κόμβος χρειάζεται εξισορρόπηση. Αυτό επιτυγχάνεται κάνοντας τις κατάλληλες [[#Rotations | περιστροφές]].
Αλλαγή σειρών 22-23 από:
σε:
!! [[#Rotations]]Περιστροφές
Αλλαγή σειρών 246-253 από:
!! Παράδειγμα
Όλα τα παραπάνω θα γίνουν πιο κατανοητά με ένα παράδειγμα.
Ας υποθέσουμε ότι έχουμε με τη σειρά τους αριθμούς: @@4, 5, 7, 2, 1, 3, 6@@
* Εισαγωγή @@4@@
σε:
Στην πραγματικότητα οι περιστροφές είναι δύο. Οι άλλες δύο είναι συμμετρικές αυτών. Αν πάρουμε για παράδειγμα τις δεξιές περιστροφές, τότε έχουμε
* απλή δεξιά με συμμετρική την απλή αριστερή
* δεξιά - αριστερή με συμμετρική την απλή αριστερή
http://users.sch.gr/fergadis/images/RR.jpg
'''(α) Αρχική κατάσταση σε ισορροπία'''
Τα υποδέντρα @@1@@ και @@2@@ του κόμβου @@Α@@ έχουν ύψος h. Το αριστερό υποδέντρο του κόμβου @@Β@@ έχει ύψος @@1+h@@. Το ένα προκύπτει από τον κόμβο @@Α@@. Έτσι, έχουμε:
Αλλαγή σειράς 257 από:
http://users.sch.gr/fergadis/images/4.jpg
σε:
Αλλαγή σειρών 259-261 από:
σε:
Το ύψος του δεξιού υποδέντρου του κόμβου @@Β@@ είναι h. Δηλαδή:
Αλλαγή σειράς 263 από:
http://users.sch.gr/fergadis/images/4-5.jpg
σε:
Αλλαγή σειρών 265-267 από:
σε:
Η ισορροπία του κόμβου @@Β@@ είναι:
Αλλαγή σειράς 269 από:
http://users.sch.gr/fergadis/images/4-5-7.jpg
σε:
'''Β(Β)=H'_R_'-H'_L'=h-(h+1) => B(B)=-1'''
Αλλαγή σειρών 271-275 από:
Εδώ βλέπουμε ότι ο κόμβος @@4@@ έχει τιμή @@2@@ και ο κόμβος @@5@@ 1. Κάνουμε, λοιπόν, μία [[#LL | απλή αριστερή περιστροφή]] για τους κόμβους @@4, 5, 7@@. Έχουμε:
* ο κόμβος @@5@@ γίνεται ρίζα στην θέση του @@4@@
* ο κόμβος @@4@@ γίνεται αριστερό παιδί του κόμβου @@5@@
Έτσι, το δέντρο γίνεται:
σε:
Γίνεται εισαγωγή του κόμβου @@Χ@@.
!! Παράδειγμα
Όλα τα παραπάνω θα γίνουν πιο κατανοητά με ένα παράδειγμα.
Ας υποθέσουμε ότι έχουμε με τη σειρά τους αριθμούς: @@4, 5, 7, 2, 1, 3, 6@@
* Εισαγωγή @@4@@
Αλλαγή σειράς 284 από:
http://users.sch.gr/fergadis/images/4-5-7-LL.jpg
σε:
http://users.sch.gr/fergadis/images/4.jpg
Αλλαγή σειράς 286 από:
σε:
Αλλαγή σειράς 288 από:
http://users.sch.gr/fergadis/images/4-5-7-2.jpg
σε:
http://users.sch.gr/fergadis/images/4-5.jpg
Αλλαγή σειράς 290 από:
σε:
Αλλαγή σειράς 292 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7.jpg
Αλλαγή σειρών 294-298 από:
Με αυτή την εισαγωγή, ο κόμβος @@4@@ έχει τιμή -2 και ο κόμβος @@2@@ -1. Κάνουμε, [[#RR | απλή δεξιά περιστροφή]] στους κόμβους @@4, 2, 1@@. Έχουμε:
* ο κόμβος @@2@@ παίρνει τη θέση του κόμβου @@4@@
* ο κόμβος @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
Το δέντρο γίνεται:
σε:
Εδώ βλέπουμε ότι ο κόμβος @@4@@ έχει τιμή @@2@@ και ο κόμβος @@5@@ 1. Κάνουμε, λοιπόν, μία [[#LL | απλή αριστερή περιστροφή]] για τους κόμβους @@4, 5, 7@@. Έχουμε:
* ο κόμβος @@5@@ γίνεται ρίζα στην θέση του @@4@@
* ο κόμβος @@4@@ γίνεται αριστερό παιδί του κόμβου @@5@@
Έτσι, το δέντρο γίνεται:
Αλλαγή σειράς 300 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-RR.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-LL.jpg
Αλλαγή σειράς 302 από:
σε:
Αλλαγή σειράς 304 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2.jpg
Αλλαγή σειρών 306-313 από:
Με την εισαγωγή του κόμβου @@3@@, ο κόμβος @@5@@ αποκτά τιμή -2 και ο @@2@@ τιμή 1. Για να αποκαταστήσουμε την ισορροπία πρέπει να κάνουμε μία [[#RL | δεξιά - αριστερή περιστροφή]] στους κόμβους @@5, 2, 4@@.
Πρώτα κάνουμε την αριστερή περιστροφή στους κόμβου @@2@@ και @@4@@.
* ο κόμβος @@4@@ γίνεται ρίζα στη θέση του @@2@@
* το αριστερό παιδί του κόμβου @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
* ο κόμβος @@2@@ γίνεται αριστερό παιδί του κόμβου @@4@@
Το δέντρο γίνεται:
σε:
Αλλαγή σειράς 308 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-L.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1.jpg
Αλλαγή σειρών 310-315 από:
Τώρα κάνουμε την δεξιά περιστροφή:
* ο κόμβος @@4@@ γίνεται ρίζα, στη θέση του @@5@@
* ο κόμβος @@5@@ γίνεται δεξί παιδί στον κόμβο @@4@@
Τώρα το δέντρο γίνεται:
σε:
Με αυτή την εισαγωγή, ο κόμβος @@4@@ έχει τιμή -2 και ο κόμβος @@2@@ -1. Κάνουμε, [[#RR | απλή δεξιά περιστροφή]] στους κόμβους @@4, 2, 1@@. Έχουμε:
* ο κόμβος @@2@@ παίρνει τη θέση του κόμβου @@4@@
* ο κόμβος @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
Το δέντρο γίνεται:
Αλλαγή σειράς 316 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-LR.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1-RR.jpg
Αλλαγή σειρών 318-319 από:
σε:
Αλλαγή σειράς 320 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3.jpg
Αλλαγή σειρών 322-328 από:
Ο κόμβος @@5@@ έχει τιμή 2 και ο @@7@@ τιμή -1. Για την αποκατάσταση της ισορροπίας πρέπει να κάνουμε μία [[#LR | αριστερή - δεξιά περιστροφή]].
Πρώτα κάνουμε δεξιά περιστροφή στους κόμβους @@7@@ και @@6@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@7@@
* ο κόμβος @@7@@ γίνεται δεξί παιδί του κόμβου @@6@@
σε:
Με την εισαγωγή του κόμβου @@3@@, ο κόμβος @@5@@ αποκτά τιμή -2 και ο @@2@@ τιμή 1. Για να αποκαταστήσουμε την ισορροπία πρέπει να κάνουμε μία [[#RL | δεξιά - αριστερή περιστροφή]] στους κόμβους @@5, 2, 4@@.
Πρώτα κάνουμε την αριστερή περιστροφή στους κόμβου @@2@@ και @@4@@.
* ο κόμβος @@4@@ γίνεται ρίζα στη θέση του @@2@@
* το αριστερό παιδί του κόμβου @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
* ο κόμβος @@2@@ γίνεται αριστερό παιδί του κόμβου @@4@@
Αλλαγή σειράς 331 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6-R.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-L.jpg
Αλλαγή σειρών 334-338 από:
Τώρα κάνουμε αριστερή περιστροφή στους κόμβους @@5, 6@@ και @@7@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@5@@
* ο κόμβος @@5@@ γίνεται αριστερό παιδί του κόμβου @@6@@.
Το δέντρο γίνεται:
σε:
Τώρα κάνουμε την δεξιά περιστροφή:
* ο κόμβος @@4@@ γίνεται ρίζα, στη θέση του @@5@@
* ο κόμβος @@5@@ γίνεται δεξί παιδί στον κόμβο @@4@@
Τώρα το δέντρο γίνεται:
Πρόσθεση σειρών 340-364:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-LR.jpg
>><<
* Εισαγωγή @@6@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6.jpg
>><<
Ο κόμβος @@5@@ έχει τιμή 2 και ο @@7@@ τιμή -1. Για την αποκατάσταση της ισορροπίας πρέπει να κάνουμε μία [[#LR | αριστερή - δεξιά περιστροφή]].
Πρώτα κάνουμε δεξιά περιστροφή στους κόμβους @@7@@ και @@6@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@7@@
* ο κόμβος @@7@@ γίνεται δεξί παιδί του κόμβου @@6@@
Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6-R.jpg
>><<
Τώρα κάνουμε αριστερή περιστροφή στους κόμβους @@5, 6@@ και @@7@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@5@@
* ο κόμβος @@5@@ γίνεται αριστερό παιδί του κόμβου @@6@@.
Το δέντρο γίνεται:
>>center<<
22-02-2008 (14:59)
από Aris -
Αλλαγή σειρών 4-5 από:
(:comment Ένα δέντρο AVL είναι ένας ειδικός τύπος δυαδικού δέντρου που είναι πάντα "μερικώς" ισορροπημένο. Το κριτήριο που χρησιμοποιείται για να καθορίσει το βαθμό ισορροπίας είναι η διαφορά μεταξύ των υψών των υποδέντρων και μιας ρίζας στο δέντρο. Το "ύψος" του δέντρου είναι ο "αριθμός επιπέδων" στο δέντρο. Ή για να είναι πιο σωστό, το ύψος ενός δέντρου καθορίζεται ως εξής: :)
σε:
Ένα δέντρο AVL είναι ένας ειδικός τύπος δυαδικού δέντρου που είναι πάντα "μερικώς" ισορροπημένο. Το κριτήριο που χρησιμοποιείται για να καθορίσει το βαθμό ισορροπίας είναι η διαφορά μεταξύ των υψών των υποδέντρων κάθε κόμβου. Το κριτήριο, λοιπόν, ισορροπίας είναι το ακόλουθο:
->Ένα δέντρο είναι ''ισορροπημένο'' αν και μόνο αν {+για κάθε+} κόμβο η διαφορά του ύψους των δύο υποδέντρων του διαφέρει το πολύ κατά 1 (απόλυτη τιμή).
Τη διαφορά αυτή, εδώ, τη συμβολίζουμε με:
>>center<<
B(x)=H'_R_'-H'_L_'
όπου x ο κόμβος (π.χ. a, b, c ή 5, 2, 7 κλπ)\\
H'_R_' το ύψος του δεξιού υποδέντρου του κόμβου, και\\
H'_L_' το ύψος του αριστερού υποδέντρου
>><<
21-02-2008 (22:25)
από Aris -
21-02-2008 (22:23)
από Aris -
Πρόσθεση σειρών 298-322:
>><<
* Εισαγωγή @@6@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6.jpg
>><<
Ο κόμβος @@5@@ έχει τιμή 2 και ο @@7@@ τιμή -1. Για την αποκατάσταση της ισορροπίας πρέπει να κάνουμε μία [[#LR | αριστερή - δεξιά περιστροφή]].
Πρώτα κάνουμε δεξιά περιστροφή στους κόμβους @@7@@ και @@6@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@7@@
* ο κόμβος @@7@@ γίνεται δεξί παιδί του κόμβου @@6@@
Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6-R.jpg
>><<
Τώρα κάνουμε αριστερή περιστροφή στους κόμβους @@5, 6@@ και @@7@@.
* ο κόμβος @@6@@ γίνεται ρίζα στη θέση του κόμβου @@5@@
* ο κόμβος @@5@@ γίνεται αριστερό παιδί του κόμβου @@6@@.
Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-6-RL.jpg
21-02-2008 (22:10)
από Aris -
21-02-2008 (22:06)
από Aris -
Αλλαγή σειρών 279-280 από:
Με την εισαγωγή του κόμβου @@3@@, ο κόμβος @@5@@ αποκτά τιμή -2 και ο @@2@@ τιμή 1. Για να αποκαταστήσουμε την ισορροπία πρέπει να κάνουμε μία [[#RL | δεξιά - αριστερή περιστροφή]] στους κόμβους @@5, 2, 4@@. Πρώτα κάνουμε την αριστερή περιστροφή στους κόμβου @@2@@ και @@4@@. Το δέντρο γίνεται:
σε:
Με την εισαγωγή του κόμβου @@3@@, ο κόμβος @@5@@ αποκτά τιμή -2 και ο @@2@@ τιμή 1. Για να αποκαταστήσουμε την ισορροπία πρέπει να κάνουμε μία [[#RL | δεξιά - αριστερή περιστροφή]] στους κόμβους @@5, 2, 4@@.
Πρώτα κάνουμε την αριστερή περιστροφή στους κόμβου @@2@@ και @@4@@.
* ο κόμβος @@4@@ γίνεται ρίζα στη θέση του @@2@@
* το αριστερό παιδί του κόμβου @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
* ο κόμβος @@2@@ γίνεται αριστερό παιδί του κόμβου @@4@@
Το δέντρο γίνεται:
Πρόσθεση σειρών 289-297:
>><<
Τώρα κάνουμε την δεξιά περιστροφή:
* ο κόμβος @@4@@ γίνεται ρίζα, στη θέση του @@5@@
* ο κόμβος @@5@@ γίνεται δεξί παιδί στον κόμβο @@4@@
Τώρα το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-LR.jpg
21-02-2008 (21:54)
από Aris -
Αλλαγή σειράς 282 από:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-R.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-L.jpg
21-02-2008 (21:27)
από Aris -
Αλλαγή σειράς 251 από:
Εδώ βλέπουμε ότι ο κόμβος @@4@@ έχει τιμή @@2@@ και ο κόμβος @@5@@ 1. Κάνουμε, λοιπόν, μία [[#LL | απλή αριστερή περιστροφή]]. Έχουμε:
σε:
Εδώ βλέπουμε ότι ο κόμβος @@4@@ έχει τιμή @@2@@ και ο κόμβος @@5@@ 1. Κάνουμε, λοιπόν, μία [[#LL | απλή αριστερή περιστροφή]] για τους κόμβους @@4, 5, 7@@. Έχουμε:
Πρόσθεση σειρών 258-282:
>><<
* Εισαγωγή @@2@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2.jpg
>><<
* Εισαγωγή @@1@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1.jpg
>><<
Με αυτή την εισαγωγή, ο κόμβος @@4@@ έχει τιμή -2 και ο κόμβος @@2@@ -1. Κάνουμε, [[#RR | απλή δεξιά περιστροφή]] στους κόμβους @@4, 2, 1@@. Έχουμε:
* ο κόμβος @@2@@ παίρνει τη θέση του κόμβου @@4@@
* ο κόμβος @@4@@ γίνεται δεξί παιδί του κόμβου @@2@@
Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-RR.jpg
>><<
* Εισαγωγή @@3@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3.jpg
>><<
Με την εισαγωγή του κόμβου @@3@@, ο κόμβος @@5@@ αποκτά τιμή -2 και ο @@2@@ τιμή 1. Για να αποκαταστήσουμε την ισορροπία πρέπει να κάνουμε μία [[#RL | δεξιά - αριστερή περιστροφή]] στους κόμβους @@5, 2, 4@@. Πρώτα κάνουμε την αριστερή περιστροφή στους κόμβου @@2@@ και @@4@@. Το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7-2-1-3-R.jpg
21-02-2008 (20:15)
από Aris -
Αλλαγή σειράς 257 από:
http://users.sch.gr/fergadis/images/4-5-7.jpg
σε:
http://users.sch.gr/fergadis/images/4-5-7-LL.jpg
21-02-2008 (19:23)
από Aris -
Αλλαγή σειρών 232-384 από:
!! Εισαγωγή Κόμβου
!!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
%frame%[@
d B(d)=2-1 => B(d)=-1
/ \
b j B(b)=0, B(j)=1-1 => B(j)=0
/ \
g m B(g)=0, B(m)=0
@]
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
%frame%[@
d B(d)=2-2 => B(d)=0
/ \
b j B(b)=0-1 => B(b)=-1, B(j)=1-1 => B(j)=0
/ / \
a g m B(a)=0, B(g)=0, B(m)=0
@]
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@. Επίσης, τα ίδια θα είχαμε αν το "κοντό" υποδέντρο βρίσκεται δεξιά της ρίζας @@c@@ και το "ψηλό" αριστερά.
!!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
[[#Figure5]]
%frame%[@
d B(d)=2-1 => B(d)=1
/ \
b j B(b)=0, B(j)=1-1 => B(j)=0
/ \
g m B(g)=0, B(m)=0
@]
Η εισαγωγή τώρα γίνεται στο "ψηλό" υποδέντρο, το οποίο σε αυτή την περίπτωση είναι το δεξί. Ο νέος κόμβος μπορεί να καταλήξει ως:
* δεξί παιδί του @@m@@
* αριστερό παιδί του @@m@@
* αριστερό παιδί του @@g@@
* δεξί παιδί του @@g@@
Κάθε μία από τις παραπάνω περιπτώσεις αντιμετωπίζεται με τις τέσσερις περιστροφές που έχουμε δει.
!!!! Εισαγωγή ως Δεξιού Παιδιού στο Δεξιότερο Κόμβο
Η εισαγωγή του κόμβου @@n@@ στο δέντρο του [[#Figure5 | σχήματος 5]], θα δημιουργήσει το παρακάτω δέντρο.
%frame%[@
d B(d)=3-1 => B(d)=2
/ \
b j B(b)=0, B(j)=2-1 => B(j)=1
/ \
g m B(d)=0, B(m)=1-0 => B(m)=1
\
n
@]
Μετά την εισαγωγή, ο "παππούς" του κόμβου @@m@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]] στους εμπλεκόμενους κόμβους @@d, j@@ και @@m@@. Ακολουθώντας τα βήματά της έχουμε:
# Ο κόμβος @@j@@ γίνεται ρίζα (στη θέση του @@d@@)
# Ο κόμβος @@d@@ γίνεται αριστερό παιδί του κόμβου @@j@@
# Το αριστερό παιδί του κόμβου @@j@@ γίνεται δεξί παιδί του κόμβου @@d@@
%frame%[@
j B(j)=2-2 => B(j)=0
/ \
d m B(d)=1-1 => B(d)=0, B(m)=1-0 => B(m)=1
/ \ \
b g n
@]
Βλέπουμε ότι η περιστροφή αποκατέστησε την ισορροπία.
!!!! Εισαγωγή ως Αριστερού Παιδιού στο Δεξιότερο Κόμβο
Η εισαγωγή του κόμβου @@l@@ στο δέντρο του [[#Figure5 | σχήματος 5]], θα δημιουργήσει το παρακάτω δέντρο.
%frame%[@
d B(d)=3-1 => B(d)=2
/ \
b j B(b)=0, B(j)=2-1 => B(j)=1
/ \
g m B(g)=0, B(m)=0-1 => B(f)=-1
/
l
@]
Βλέπουμε πάλι ότι ο "παππούς" του κόμβου @@m@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πάλι πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]] στους εμπλεκόμενους κόμβους @@d, j@@ και @@m@@. Ακολουθώντας τα βήματά της έχουμε:
# Ο κόμβος @@j@@ γίνεται ρίζα (στη θέση του @@d@@)
# Ο κόμβος @@d@@ γίνεται αριστερό παιδί του κόμβου @@j@@
# Το αριστερό παιδί του κόμβου @@j@@ γίνεται δεξί παιδί του κόμβου @@d@@
%frame%[@
j B(j)=2-2 => B(j)=0
/ \
/ \
d m B(d)=1-1 => B(d)=0, B(m)=0-1 => B(m)=-1
/ \ /
b g l
@]
!!! Εισαγωγή ως Αριστερού Παιδιού Του Αριστερότερου Κόμβου του Δεξιού Υποδέντρου
Στο γνωστό δέντρο (παρακάτω).
Η εισαγωγή του κόμβου @@f@@ στο δέντρο του [[#Figure5 | σχήματος 5]], θα δημιουργήσει το παρακάτω δέντρο.
%frame%[@
d B(d)=3-1 => B(d)=2
/ \
b j B(b)=0, B(j)=1-2 => B(j)=-1
/ \
g m B(g)=0-1 => B(g)=-1, B(m)=0
/
f
@]
Η εισαγωγή χαλάει την ισορροπία. Ο κόμβος @@d@@ έχει τιμή 2 και ο κόμβος @@j@@ -1. Αυτό σημαίνει ότι πρέπει να κάνουμε μία [[#LR | Αριστερή - Δεξιά Περιστροφή]] στους κόμβους @@d, j@@ και @@g@@.
Κάνουμε, λοιπόν, πρώτα τη δεξιά περιστροφή στους κόμβους @@j@@ και @@g@@.
# Ο κόμβος @@g@@ γίνεται ρίζα (στη θέση του @@j@@)
# Ο κόμβος @@j@@ γίνεται δεξί παιδί του @@g@@
%frame%[@
d B(d)=3-1 => B(d)=2
/ \
b g B(b)=0, B(g)=2-1 => B(g)=1
/ \
f j B(f)=0, B(j)=1-0 => B(j)=1
\
m
@]
Τώρα ο κόμβος @@d@@ έχει τιμή 2 και ο κόμβος @@g@@ 1. Άρα κάνουμε μία [[#LL | απλή αριστερή περιστροφή]] στους κόμβους @@d, g@@ και @@j@@.
# Ο κόμβος @@g@@ γίνεται ρίζα (στη θέση του @@d@@)
# Ο κόμβος @@d@@ γίνεται αριστερό παιδί του @@g@@
# Το αριστερό παιδί του @@g@@ γίνεται δεξί παιδί στον @@g@@
%frame%[@
g B(g)=2-2 => B(g)=0
/ \
d j B(d)=1-1 => B(d)=0, B(j)=1-0 => B(j)=1
/ \ \
b f m
@]
Η διαδικασία απεκατέστησε την ισορροπία.
σε:
!! Παράδειγμα
Όλα τα παραπάνω θα γίνουν πιο κατανοητά με ένα παράδειγμα.
Ας υποθέσουμε ότι έχουμε με τη σειρά τους αριθμούς: @@4, 5, 7, 2, 1, 3, 6@@
* Εισαγωγή @@4@@
>>center<<
http://users.sch.gr/fergadis/images/4.jpg
>><<
* Εισαγωγή @@5@@
>>center<<
http://users.sch.gr/fergadis/images/4-5.jpg
>><<
* Εισαγωγή @@7@@
>>center<<
http://users.sch.gr/fergadis/images/4-5-7.jpg
>><<
Εδώ βλέπουμε ότι ο κόμβος @@4@@ έχει τιμή @@2@@ και ο κόμβος @@5@@ 1. Κάνουμε, λοιπόν, μία [[#LL | απλή αριστερή περιστροφή]]. Έχουμε:
* ο κόμβος @@5@@ γίνεται ρίζα στην θέση του @@4@@
* ο κόμβος @@4@@ γίνεται αριστερό παιδί του κόμβου @@5@@
Έτσι, το δέντρο γίνεται:
>>center<<
http://users.sch.gr/fergadis/images/4-5-7.jpg
>><<
20-02-2008 (19:49)
από Aris -
20-02-2008 (19:42)
από Aris -
Αλλαγή σειράς 264 από:
σε:
Αλλαγή σειρών 336-384 από:
σε:
@]
!!! Εισαγωγή ως Αριστερού Παιδιού Του Αριστερότερου Κόμβου του Δεξιού Υποδέντρου
Στο γνωστό δέντρο (παρακάτω).
Η εισαγωγή του κόμβου @@f@@ στο δέντρο του [[#Figure5 | σχήματος 5]], θα δημιουργήσει το παρακάτω δέντρο.
%frame%[@
d B(d)=3-1 => B(d)=2
/ \
b j B(b)=0, B(j)=1-2 => B(j)=-1
/ \
g m B(g)=0-1 => B(g)=-1, B(m)=0
/
f
@]
Η εισαγωγή χαλάει την ισορροπία. Ο κόμβος @@d@@ έχει τιμή 2 και ο κόμβος @@j@@ -1. Αυτό σημαίνει ότι πρέπει να κάνουμε μία [[#LR | Αριστερή - Δεξιά Περιστροφή]] στους κόμβους @@d, j@@ και @@g@@.
Κάνουμε, λοιπόν, πρώτα τη δεξιά περιστροφή στους κόμβους @@j@@ και @@g@@.
# Ο κόμβος @@g@@ γίνεται ρίζα (στη θέση του @@j@@)
# Ο κόμβος @@j@@ γίνεται δεξί παιδί του @@g@@
%frame%[@
d B(d)=3-1 => B(d)=2
/ \
b g B(b)=0, B(g)=2-1 => B(g)=1
/ \
f j B(f)=0, B(j)=1-0 => B(j)=1
\
m
@]
Τώρα ο κόμβος @@d@@ έχει τιμή 2 και ο κόμβος @@g@@ 1. Άρα κάνουμε μία [[#LL | απλή αριστερή περιστροφή]] στους κόμβους @@d, g@@ και @@j@@.
# Ο κόμβος @@g@@ γίνεται ρίζα (στη θέση του @@d@@)
# Ο κόμβος @@d@@ γίνεται αριστερό παιδί του @@g@@
# Το αριστερό παιδί του @@g@@ γίνεται δεξί παιδί στον @@g@@
%frame%[@
g B(g)=2-2 => B(g)=0
/ \
d j B(d)=1-1 => B(d)=0, B(j)=1-0 => B(j)=1
/ \ \
b f m
@]
Η διαδικασία απεκατέστησε την ισορροπία.
20-02-2008 (16:03)
από Aris -
20-02-2008 (15:44)
από Aris -
Αλλαγή σειρών 293-294 από:
Μετά την εισαγωγή, ο "παππούς" του κόμβου @@m@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]]. Ακολουθώντας τα βήματά της έχουμε:
σε:
Μετά την εισαγωγή, ο "παππούς" του κόμβου @@m@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]] στους εμπλεκόμενους κόμβους @@d, j@@ και @@m@@. Ακολουθώντας τα βήματά της έχουμε:
Αλλαγή σειρών 297-298 από:
# Το αριστερό παιδί του κόμβου @@g@@ γίνεται δεξί παιδί του κόμβου @@d@@
σε:
# Το αριστερό παιδί του κόμβου @@j@@ γίνεται δεξί παιδί του κόμβου @@d@@
Αλλαγή σειρών 307-336 από:
Βλέπουμε ότι η περιστροφή αποκατέστησε την ισορροπία.
σε:
Βλέπουμε ότι η περιστροφή αποκατέστησε την ισορροπία.
!!!! Εισαγωγή ως Αριστερού Παιδιού στο Δεξιότερο Κόμβο
Η εισαγωγή του κόμβου @@l@@ στο δέντρο του [[#Figure5 | σχήματος 5]], θα δημιουργήσει το παρακάτω δέντρο.
%frame%[@
d B(d)=3-1 => B(d)=2
/ \
b j B(b)=0, B(j)=2-1 => B(j)=1
/ \
g m B(g)=0, B(m)=0-1 => B(f)=-1
/
l
@]
Βλέπουμε πάλι ότι ο "παππούς" του κόμβου @@m@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πάλι πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]] στους εμπλεκόμενους κόμβους @@d, j@@ και @@m@@. Ακολουθώντας τα βήματά της έχουμε:
# Ο κόμβος @@j@@ γίνεται ρίζα (στη θέση του @@d@@)
# Ο κόμβος @@d@@ γίνεται αριστερό παιδί του κόμβου @@j@@
# Το αριστερό παιδί του κόμβου @@j@@ γίνεται δεξί παιδί του κόμβου @@d@@
%frame%[@
j B(j)=2-2 => B(j)=0
/ \
/ \
d m B(d)=1-1 => B(d)=0, B(m)=0-1 => B(m)=-1
/ \ /
b g l
@]
20-02-2008 (15:36)
από Aris -
Αλλαγή σειράς 286 από:
b j B(b)=0, B(e)=2-1 => B(e)=1
σε:
b j B(b)=0, B(j)=2-1 => B(j)=1
Αλλαγή σειράς 288 από:
g m B(d)=0, B(f)=1-0 => B(f)=1
σε:
g m B(d)=0, B(m)=1-0 => B(m)=1
Αλλαγή σειρών 293-294 από:
Ο "παππούς" του κόμβου @@m@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]]. Ακολουθώντας τα βήματά της έχουμε:
σε:
Μετά την εισαγωγή, ο "παππούς" του κόμβου @@m@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]]. Ακολουθώντας τα βήματά της έχουμε:
Αλλαγή σειρών 300-305 από:
j B(j)=2-2 => B(j)=0
/ \
/ \
d m B(d)=1-1 => B(d)=0, B(m)=0-1 => B(m)=-1
/ \ /
b g l
σε:
j B(j)=2-2 => B(j)=0
/ \
d m B(d)=1-1 => B(d)=0, B(m)=1-0 => B(m)=1
/ \ \
b g n
Αλλαγή σειράς 307 από:
Βλέπουμε ότι η ''ίδια'' περιστροφή αποκατέστησε την ισορροπία.
σε:
Βλέπουμε ότι η περιστροφή αποκατέστησε την ισορροπία.
20-02-2008 (15:10)
από Aris -
Αλλαγή σειρών 300-304 από:
j B(j)=2-2 => B(j)=0
/ \
d m B(d)=1-1 => B(d)=0, B(m)=1-0 => B(m)=1
/ \ \
b g n
σε:
j B(j)=2-2 => B(j)=0
/ \
/ \
d m B(d)=1-1 => B(d)=0, B(m)=0-1 => B(m)=-1
/ \ /
b g l
Αλλαγή σειράς 308 από:
Βλέπουμε ότι η περιστροφή αποκατέστησε την ισορροπία.
σε:
Βλέπουμε ότι η ''ίδια'' περιστροφή αποκατέστησε την ισορροπία.
20-02-2008 (14:01)
από Aris -
Αλλαγή σειράς 239 από:
σε:
Αλλαγή σειράς 241 από:
b e B(b)=0, B(e)=1-1 => B(e)=0
σε:
b j B(b)=0, B(j)=1-1 => B(j)=0
Αλλαγή σειράς 243 από:
σε:
Αλλαγή σειράς 249 από:
σε:
Αλλαγή σειράς 251 από:
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
σε:
b j B(b)=0-1 => B(b)=-1, B(j)=1-1 => B(j)=0
Αλλαγή σειράς 253 από:
a d f B(a)=0, B(d)=0, B(f)=0
σε:
a g m B(a)=0, B(g)=0, B(m)=0
Αλλαγή σειράς 264 από:
σε:
Αλλαγή σειράς 266 από:
b e B(b)=0, B(e)=1-1 => B(e)=0
σε:
b j B(b)=0, B(j)=1-1 => B(j)=0
Αλλαγή σειράς 268 από:
σε:
Αλλαγή σειρών 272-276 από:
* δεξί παιδί του @@f@@
* αριστερό παιδί του @@f@@
* αριστερό παιδί του @@d@@
* δεξί παιδί του @@d@@
σε:
* δεξί παιδί του @@m@@
* αριστερό παιδί του @@m@@
* αριστερό παιδί του @@g@@
* δεξί παιδί του @@g@@
Αλλαγή σειρών 281-282 από:
Η εισαγωγή του κόμβου @@g@@ στο δέντρο του [[#Figure5 | σχήματος 5]], θα δημιουργήσει το παρακάτω δέντρο.
σε:
Η εισαγωγή του κόμβου @@n@@ στο δέντρο του [[#Figure5 | σχήματος 5]], θα δημιουργήσει το παρακάτω δέντρο.
Αλλαγή σειράς 284 από:
σε:
Αλλαγή σειράς 286 από:
b e B(b)=0, B(e)=2-1 => B(e)=1
σε:
b j B(b)=0, B(e)=2-1 => B(e)=1
Αλλαγή σειράς 288 από:
d f B(d)=0, B(f)=1-0 => B(f)=1
σε:
g m B(d)=0, B(f)=1-0 => B(f)=1
Αλλαγή σειράς 290 από:
σε:
Αλλαγή σειρών 293-298 από:
Ο "παππούς" του κόμβου @@f@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]]. Ακολουθώντας τα βήματά της έχουμε:
# Ο κόμβος @@e@@ γίνεται ρίζα (στη θέση του @@c@@)
# Ο κόμβος @@c@@ γίνεται αριστερό παιδί του κόμβου @@c@@
# Το αριστερό παιδί του κόμβου @@e@@ γίνεται δεξί παιδί του κόμβου @@c@@
σε:
Ο "παππούς" του κόμβου @@m@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]]. Ακολουθώντας τα βήματά της έχουμε:
# Ο κόμβος @@j@@ γίνεται ρίζα (στη θέση του @@d@@)
# Ο κόμβος @@d@@ γίνεται αριστερό παιδί του κόμβου @@j@@
# Το αριστερό παιδί του κόμβου @@g@@ γίνεται δεξί παιδί του κόμβου @@d@@
Αλλαγή σειράς 300 από:
σε:
Αλλαγή σειράς 302 από:
c f B(c)=1-1 => B(c)=0, B(f)=1-0 => B(f)=1
σε:
d m B(d)=1-1 => B(d)=0, B(m)=1-0 => B(m)=1
Αλλαγή σειράς 304 από:
σε:
20-02-2008 (13:24)
από Aris -
Πρόσθεση σειράς 262:
Πρόσθεση σειρών 272-273:
* δεξί παιδί του @@f@@
* αριστερό παιδί του @@f@@
Αλλαγή σειρών 276-278 από:
* αριστερό παιδί του @@f@@
* δεξί παιδί του @@f@@
σε:
Αλλαγή σειρών 279-282 από:
# Η εισαγωγή γίνεται ως δεξί παιδί του κόμβου f
σε:
!!!! Εισαγωγή ως Δεξιού Παιδιού στο Δεξιότερο Κόμβο
Η εισαγωγή του κόμβου @@g@@ στο δέντρο του [[#Figure5 | σχήματος 5]], θα δημιουργήσει το παρακάτω δέντρο.
%frame%[@
c B(c)=3-1 => B(c)=2
/ \
b e B(b)=0, B(e)=2-1 => B(e)=1
/ \
d f B(d)=0, B(f)=1-0 => B(f)=1
\
g
@]
Ο "παππούς" του κόμβου @@f@@ έχει τιμή 2 και ο "πατέρας" του 1. Άρα πρέπει να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]]. Ακολουθώντας τα βήματά της έχουμε:
# Ο κόμβος @@e@@ γίνεται ρίζα (στη θέση του @@c@@)
# Ο κόμβος @@c@@ γίνεται αριστερό παιδί του κόμβου @@c@@
# Το αριστερό παιδί του κόμβου @@e@@ γίνεται δεξί παιδί του κόμβου @@c@@
%frame%[@
e B(e)=2-2 => B(e)=0
/ \
c f B(c)=1-1 => B(c)=0, B(f)=1-0 => B(f)=1
/ \ \
b d g
@]
Βλέπουμε ότι η περιστροφή αποκατέστησε την ισορροπία.
20-02-2008 (13:07)
από Aris -
Αλλαγή σειρών 167-168 από:
Το δέντρο είναι ισορροπημένο. Η εισαγωγή ενός κόμβου ως αριστρερού παιδιού του κόμβου @@a@@ οδηγεί στην περίπτωση της [[#RR | απλής δεξιάς περιστροφής]]. Με την εισαγωγή ενός κόμβου που θα γίνει δεξί παιδί του @@a@, έχουμε το παρακάτω σχήμα.
σε:
Το δέντρο είναι ισορροπημένο. Η εισαγωγή ενός κόμβου ως αριστρερού παιδιού του κόμβου @@a@@ οδηγεί στην περίπτωση της [[#RR | απλής δεξιάς περιστροφής]]. Με την εισαγωγή ενός κόμβου που θα γίνει δεξί παιδί του @@a@@, έχουμε το παρακάτω σχήμα.
Αλλαγή σειρών 220-221 από:
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
σε:
!!! Ανακεφαλαίωση
Συγκεντρώνοντας τις παραπάνω παρατηρήσεις, δημιουργούμε τον παρακάτω πίνακα αποφάσεων.
||border=1
||! Ισορροπία ||||! Περιστροφή
||! Παππού ||! Πατέρα || ||
|| 2 || 1 || [[#LL | Απλή Αριστερή]] ||
|| 2 || -1 || [[#LR | Αριστερή - Δεξιά]] ||
|| -2 || -1 || [[#RR | Απλή Δεξιά]] ||
|| -2 || 1 || [[#RL | Δεξιά - Αριστερή]] ||
!! Εισαγωγή Κόμβου
!!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Αλλαγή σειρών 256-259 από:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
σε:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@. Επίσης, τα ίδια θα είχαμε αν το "κοντό" υποδέντρο βρίσκεται δεξιά της ρίζας @@c@@ και το "ψηλό" αριστερά.
!!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Αλλαγή σειρών 270-271 από:
Η εισαγωγή τώρα γίνεται στο "ψηλό" υποδέντρο, το οποίο σε αυτή την περίπτωση είναι το δεξί. Διακρίνουμε δύο περιπτώσεις:
σε:
Η εισαγωγή τώρα γίνεται στο "ψηλό" υποδέντρο, το οποίο σε αυτή την περίπτωση είναι το δεξί. Ο νέος κόμβος μπορεί να καταλήξει ως:
* αριστερό παιδί του @@d@@
* δεξί παιδί του @@d@@
* αριστερό παιδί του @@f@@
* δεξί παιδί του @@f@@
Κάθε μία από τις παραπάνω περιπτώσεις αντιμετωπίζεται με τις τέσσερις περιστροφές που έχουμε δει.
20-02-2008 (12:44)
από Aris -
Πρόσθεση σειράς 13:
Αλλαγή σειράς 32 από:
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@a@@ η οποία λύνεται με τα παρακάτω βήματα
σε:
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@a@@ η οποία λύνεται με τα παρακάτω βήματα:
Πρόσθεση σειράς 39:
Πρόσθεση σειράς 53:
Πρόσθεση σειράς 79:
Αλλαγή σειράς 112 από:
Αυτό το δέντρο δεν είναι ισορροπημένο. Για να αποκατασταθεί η ισορροπία του πρέπει να μειωθεί το ύψος του κόμβου @@c@@. Αν δοκιμάσουμε να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]], ακολουθούμε τα γνωστά βήματα:
σε:
Αυτό το δέντρο δεν είναι ισορροπημένο. Η ισορροπία του @@a@@ ("παππού" του @@b@@) είναι θετική και ίση με 2. Αν δοκιμάσουμε να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]], ακολουθούμε τα γνωστά βήματα και:
Αλλαγή σειρών 127-128 από:
Βλέπουμε ότι η περιστροφή δεν έλυσε το πρόβλημα. Μία προσπάθεια [[#RR | απλής δεξιάς περιστροφής]] δε θα λύσει πάλι το πρόβλημα. Θα φτάσουμε στην προηγούμενη κατάσταση.
σε:
Βλέπουμε ότι η περιστροφή δεν έλυσε το πρόβλημα. Μία προσπάθεια [[#RR | απλής δεξιάς περιστροφής]] (ισορροπία "παππού" -2) δε θα λύσει πάλι το πρόβλημα. Θα φτάσουμε στην προηγούμενη κατάσταση.
Αλλαγή σειρών 153-160 από:
Στην πραγματικότητα κάνουμε πρώτα μία δεξιά περιστροφή στο υποδέντρο και μία αριστερή στο δέντρο. Το γιατί ονομάζεται "Αριστερή-Δεξιά Περιστροφή" ή "Διπλή Αριστερά", για μένα παραμένει μυστήριο.
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
σε:
Στην πραγματικότητα κάνουμε πρώτα μία δεξιά περιστροφή στο υποδέντρο και μία αριστερή στο δέντρο. Το γιατί ονομάζεται "Αριστερή-Δεξιά Περιστροφή" ή "Διπλή Αριστερή", για μένα παραμένει μυστήριο.
!!! [[#RL]]Δεξιά - Αριστερή Περιστροφή (ή "Διπλή Δεξιά")
Αυτή η περίπτωση είναι όμοια με την [[#LR | Αριστερή - Δεξιά Περιστροφή]] με την έννοια ότι είναι συμμετρική της. Ας δούμε την παρακάτω περίπτωση.
[[#Figure4]]
Αλλαγή σειρών 161-165 από:
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
σε:
c Β(c)=0-1 => B(c)=-1
/
a B(a)=0
Αλλαγή σειρών 165-167 από:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
σε:
Σχήμα 4
Το δέντρο είναι ισορροπημένο. Η εισαγωγή ενός κόμβου ως αριστρερού παιδιού του κόμβου @@a@@ οδηγεί στην περίπτωση της [[#RR | απλής δεξιάς περιστροφής]]. Με την εισαγωγή ενός κόμβου που θα γίνει δεξί παιδί του @@a@, έχουμε το παρακάτω σχήμα.
Αλλαγή σειρών 170-174 από:
c B(c)=2-2 => B(c)=0
/ \
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
σε:
c B(c)=0-2 => B(c)=-2
/
a B(a)=1-0 => B(a)=1
\
b B(b)=0
Αλλαγή σειρών 177-182 από:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
σε:
Αυτό το δέντρο δεν είναι ισορροπημένο. Η ισορροπία του @@c@@ ("παππού" του @@b@@) είναι αρνητική και ίση με -2. Αν δοκιμάσουμε να κάνουμε μία [[#RR | απλή δεξιά περιστροφή]], ακολουθούμε τα γνωστά βήματα και:
# Ο κόμβος @@a@@ γίνεται η νέα ρίζα
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@
# Το δεξί παιδί του κόμβου @@a@@ γίνεται αριστερό παιδί του κόμβου @@c@@
Έτσι, το δέντρο γίνεται:
Αλλαγή σειρών 185-189 από:
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
σε:
a B(a)=2-0 => B(c)=2
\
c B(a)=0-1 => B(a)=-1
/
b B(b)=0
Πρόσθεση σειρών 192-255:
Βλέπουμε πάλι ότι η περιστροφή δεν έλυσε το πρόβλημα. Επίσης, μία προσπάθεια [[#LL | απλής αριστερής περιστροφής]] (ισορροπία "παππού" 2) δε θα λύσει πάλι το πρόβλημα. Θα φτάσουμε στην προηγούμενη κατάσταση.
Η διαδικασία που ακολουθούμε σε αυτή την περίπτωση είναι η εξής:
* Κάνουμε [[#LL | απλή αριστερή περιστροφή]] στο υποδέντρο με ρίζα τον κόμβο @@a@@
%frame%[@
c Β(c)=0-2 => B(a)=-2
/
b B(b)=0-1 => B(b)=-1
/
a B(a)=0
@]
Βλέπουμε ότι έχουμε @@B(c)=-2@@ και @@B(b)=-1@@, άρα, αυτό που έχουμε είναι να
* Κάνουμε [[#RR | απλή δεξιά περιστροφή]] στο δέντρο με ρίζα τον κόμβο @@c@@
%frame%[@
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(c)=0
@]
Βλέπουμε ότι αυτή η διαδικασία αποκαθιστά την ισορροπία. Γενικεύοντας την περίπτωση, αν η ισορροπία του "παππού" του νέου κόμβου είναι -2 και η ισορροπία του "πατέρα" είναι 1, τότε κάνουμε Δεξιά - Αριστερή Περιστροφή.
'''Σχόλιο:'''
Το ίδιο με την Αριστερή - Δεξιά Περιστροφή.
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
%frame%[@
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
@]
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
%frame%[@
c B(c)=2-2 => B(c)=0
/ \
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
@]
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
%frame%[@
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
@]
20-02-2008 (12:25)
από Aris -
Αλλαγή σειρών 34-35 από:
# Το αριστερό παιδί του κόμβου @@b@@ γίνεται δεξί παιδί του κόμβου @@a@@\\Σε αυτή την περίπτωση δεν υπάρχει αριστερό παιδί στον @@b@@
σε:
# Το αριστερό παιδί του κόμβου @@b@@ γίνεται δεξί παιδί του κόμβου @@a@@\\
Σε αυτή την περίπτωση δεν υπάρχει αριστερό παιδί στον @@b@@
Αλλαγή σειρών 72-73 από:
# Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@\\Σε αυτή την περίπτωση δεν έχουμε αριστερό παιδί του κόμβου @@b@@
σε:
# Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@\\
Σε αυτή την περίπτωση δεν έχουμε αριστερό παιδί του κόμβου @@b@@
Πρόσθεση σειράς 89:
Αλλαγή σειρών 138-139 από:
# Κάνουμε [[#LL | απλή αριστερή περιστροφή]] στο δέντρο με ρίζα τον κόμβο @@a@@
σε:
* Κάνουμε [[#LL | απλή αριστερή περιστροφή]] στο δέντρο με ρίζα τον κόμβο @@a@@
Πρόσθεση σειρών 146-152:
Βλέπουμε ότι αυτή η διαδικασία αποκαθιστά την ισορροπία. Γενικεύοντας την περίπτωση, αν η ισορροπία του "παππού" του νέου κόμβου είναι 2 και η ισορροπία του "πατέρα" είναι -1, τότε κάνουμε Αριστερή-Δεξιά Περιστροφή.
'''Σχόλιο:'''
Στην πραγματικότητα κάνουμε πρώτα μία δεξιά περιστροφή στο υποδέντρο και μία αριστερή στο δέντρο. Το γιατί ονομάζεται "Αριστερή-Δεξιά Περιστροφή" ή "Διπλή Αριστερά", για μένα παραμένει μυστήριο.
20-02-2008 (12:03)
από Aris -
Αλλαγή σειρών 124-131 από:
# Κάνουμε [[#LL | απλή αριστερή περιστροφή]] στο υποδέντρο με ρίζα τον κόμβο @@c@@
# Κάνουμε [[#RR | απλή δεξιά περιστροφή]] στο δέντρο με ρίζα τον κόμβο @@a@@
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
σε:
* Κάνουμε [[#RR | απλή δεξιά περιστροφή]] στο υποδέντρο με ρίζα τον κόμβο @@c@@
Αλλαγή σειρών 127-131 από:
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
σε:
a Β(a)=2-0 => B(a)=2
\
b B(c)=1-0 => B(c)=1
\
c B(c)=0
Αλλαγή σειρών 134-135 από:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
σε:
Βλέπουμε ότι έχουμε @@B(a)=2@@ και @@B(b)=1@@, άρα, αυτό που έχουμε είναι να
# Κάνουμε [[#LL | απλή αριστερή περιστροφή]] στο δέντρο με ρίζα τον κόμβο @@a@@
Αλλαγή σειρών 138-142 από:
c B(c)=2-2 => B(c)=0
/ \
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
σε:
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(c)=0
Αλλαγή σειρών 143-148 από:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
σε:
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
Πρόσθεση σειρών 155-178:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
%frame%[@
c B(c)=2-2 => B(c)=0
/ \
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
@]
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
%frame%[@
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
@]
20-02-2008 (11:58)
από Aris -
Αλλαγή σειρών 105-110 από:
Αυτό το δέντρο δεν είναι ισορροπημένο. Για να αποκατασταθεί η ισορροπία του πρέπει να μειωθεί το ύψος του κόμβου @@c@@.
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
σε:
Αυτό το δέντρο δεν είναι ισορροπημένο. Για να αποκατασταθεί η ισορροπία του πρέπει να μειωθεί το ύψος του κόμβου @@c@@. Αν δοκιμάσουμε να κάνουμε μία [[#LL | απλή αριστερή περιστροφή]], ακολουθούμε τα γνωστά βήματα:
# Ο κόμβος @@c@@ γίνεται η νέα ρίζα
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@c@@
# Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@
Έτσι, το δέντρο γίνεται:
Αλλαγή σειρών 113-117 από:
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
σε:
c B(c)=0-2 => B(c)=-2
/
a B(a)=1-0 => B(a)=1
\
b B(b)=0
Αλλαγή σειρών 120-121 από:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
σε:
Βλέπουμε ότι η περιστροφή δεν έλυσε το πρόβλημα. Μία προσπάθεια [[#RR | απλής δεξιάς περιστροφής]] δε θα λύσει πάλι το πρόβλημα. Θα φτάσουμε στην προηγούμενη κατάσταση.
Η διαδικασία που ακολουθούμε σε αυτή την περίπτωση είναι η εξής:
# Κάνουμε [[#LL | απλή αριστερή περιστροφή]] στο υποδέντρο με ρίζα τον κόμβο @@c@@
# Κάνουμε [[#RR | απλή δεξιά περιστροφή]] στο δέντρο με ρίζα τον κόμβο @@a@@
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
Αλλαγή σειράς 133 από:
σε:
Αλλαγή σειρών 135-137 από:
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
σε:
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
Αλλαγή σειρών 140-145 από:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
σε:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
Αλλαγή σειράς 143 από:
σε:
Αλλαγή σειρών 145-147 από:
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
σε:
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
Πρόσθεση σειρών 150-163:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
%frame%[@
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
@]
20-02-2008 (11:50)
από Aris -
Αλλαγή σειρών 34-35 από:
(:comment # Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@ :)
σε:
# Το αριστερό παιδί του κόμβου @@b@@ γίνεται δεξί παιδί του κόμβου @@a@@\\Σε αυτή την περίπτωση δεν υπάρχει αριστερό παιδί στον @@b@@
Πρόσθεση σειρών 43-44:
Γενικεύοντας την περίπτωση, μπορούμε να πούμε ότι [[#LL | απλή αριστερή περιστροφή]] έχουμε όταν η ισορροπία του "παππού" του νέου κόμβου (@@c@@ στο παράδειγμα), γίνει 2 και η ισορροπία του "πατέρα" του νέου κόμβου γίνει 1.
Αλλαγή σειρών 71-72 από:
(:comment # Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@ :)
σε:
# Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@\\Σε αυτή την περίπτωση δεν έχουμε αριστερό παιδί του κόμβου @@b@@
Πρόσθεση σειρών 80-81:
Γενικεύοντας και εδώ την περίπτωση, μπορούμε να πούμε ότι [[#RR | απλή δεξιά περιστροφή]] έχουμε όταν η ισορροπία του "παππού" του νέου κόμβου (@@c@@ στο παράδειγμα), γίνει -2 και η ισορροπία του "πατέρα" του νέου κόμβου γίνει -1.
Διαγραφή σειρών 96-101:
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
Αλλαγή σειρών 98-102 από:
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
σε:
a Β(a)=2-0 => B(a)=2
\
c B(c)=0-1 => B(c)=-1
/
b
Αλλαγή σειρών 105-106 από:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
σε:
Αυτό το δέντρο δεν είναι ισορροπημένο. Για να αποκατασταθεί η ισορροπία του πρέπει να μειωθεί το ύψος του κόμβου @@c@@.
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
Αλλαγή σειράς 112 από:
σε:
Αλλαγή σειρών 114-116 από:
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
σε:
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
Αλλαγή σειρών 119-124 από:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
σε:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
Αλλαγή σειράς 122 από:
σε:
Αλλαγή σειρών 124-126 από:
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
σε:
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
Πρόσθεση σειρών 129-142:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
%frame%[@
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
@]
20-02-2008 (11:38)
από Aris -
Αλλαγή σειρών 6-13 από:
!! Εισαγωγή Κόμβου
Η εισαγωγή γίνεται όπως στα δυαδικά δέντρα. Αν η εισαγωγή διαταράξει την ισορροπία κόμβων πρέπει αυτή να αποκατασταθεί. Η αποκατάσταση γίνεται κάνοντας περιστροφή των κόμβων των οποίων η ισορροπία διαταράχθηκε. Πριν δούμε, λοιπόν, τις περιπτώσεις εισαγωγής κόμβου, θα δούμε πρώτα τις δυνατές περιστροφές.
!!! Περιστροφές
!!!! [[#LL]]Απλή Αριστερή Περιστροφή (LL)
σε:
Η εισαγωγή/διαγραφή κόμβων γίνεται όπως στα δυαδικά δέντρα. Αν η ενέργεια διαταράξει την ισορροπία κόμβων πρέπει αυτή να αποκατασταθεί. Η αποκατάσταση γίνεται κάνοντας περιστροφή των κόμβων των οποίων η ισορροπία διαταράχθηκε. Πριν δούμε, λοιπόν, τις περιπτώσεις εισαγωγής κόμβου, θα δούμε πρώτα τις δυνατές περιστροφές.
!! Περιστροφές
!!! [[#LL]]Απλή Αριστερή Περιστροφή (LL)
Αλλαγή σειράς 13 από:
σε:
Αλλαγή σειρών 19-20 από:
σε:
Αλλαγή σειρών 43-46 από:
Σε περίπτωση που η εισαγωγή κόμβου στο [[#Figure1 | Σχήμα 1]] γίνει αριστερό παιδί του @@b@@, τότε έχουμε την περίπτωση της [[#LR | Αριστερής - Δεξιάς Περιστροφής]].
!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
σε:
Σε περίπτωση που η εισαγωγή κόμβου στο [[#Figure1 | σχήμα 1]] γίνει αριστερό παιδί του @@b@@, τότε έχουμε την περίπτωση της [[#LR | Αριστερής - Δεξιάς Περιστροφής]].
!!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
Αλλαγή σειράς 48 από:
σε:
Αλλαγή σειρών 54-55 από:
σε:
Αλλαγή σειρών 80-83 από:
!!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
σε:
!!! [[#LR]]Αριστερή - Δεξιά Περιστροφή (ή "Διπλή Αριστερή")
Μερικές φορές η [[#LL | απλή αριστερή περιστροφή]] δεν είναι αρκετή για να αποκαταστήσει την ισορροπία του δέντρου. Ας δούμε την παρακάτω περίπτωση.
[[#Figure3]]
Αλλαγή σειρών 85-89 από:
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
σε:
a Β(a)=1-0 => B(a)=1
\
c B(c)=0
Αλλαγή σειρών 89-91 από:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
σε:
Σχήμα 3
Το δέντρο είναι ισορροπημένο. Η εισαγωγή ενός κόμβου ως δεξί παιδιού του κόμβου @@c@@ οδηγεί στην περίπτωση της [[#LL | απλής αριστερής περιστροφής]]. Τι γίνεται όμως με εισαγωγή ενός κόμβου που θα γίνει αριστερό παιδί του @@c@@. Σ' αυτή την περίπτωση έχουμε το παρακάτω σχήμα.
!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
Αλλαγή σειράς 100 από:
σε:
Αλλαγή σειρών 102-104 από:
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
σε:
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
Αλλαγή σειρών 107-112 από:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
σε:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
Αλλαγή σειράς 110 από:
σε:
Αλλαγή σειρών 112-114 από:
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
σε:
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
Πρόσθεση σειρών 117-130:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
%frame%[@
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
@]
20-02-2008 (11:30)
από Aris -
Αλλαγή σειρών 21-24 από:
[[#Figure1| Σχήμα 1]]
Αν γίνει εισαγωγή κόμβου ως δεξί παιδί @@b@@, το δέντρο γίνεται:
σε:
[[#Figure1]]Σχήμα 1
Αν γίνει εισαγωγή κόμβου ως δεξί παιδί του @@b@@, το δέντρο γίνεται:
Αλλαγή σειρών 45-46 από:
Σε περίπτωση που η εισαγωγή στο
σε:
Σε περίπτωση που η εισαγωγή κόμβου στο [[#Figure1 | Σχήμα 1]] γίνει αριστερό παιδί του @@b@@, τότε έχουμε την περίπτωση της [[#LR | Αριστερής - Δεξιάς Περιστροφής]].
Αλλαγή σειρών 49-50 από:
Έχουμε το παρακάτω τμήμα ενός δέντρου:
σε:
Ας, υποθέσουμε ότι έχουμε το παρακάτω τμήμα ενός δέντρου.
Αλλαγή σειρών 56-58 από:
Γίνεται εισαγωγή του @@a@@. Το δέντρο γίνεται:
σε:
[[#Figure2]]Σχήμα 2
Αν γίνει εισαγωγή κόμβου ως αριστερό παιδί του κόμβου @@b@@, έχουμε το παρακάτω δέντρο.
Πρόσθεση σειρών 80-81:
Σε περίπτωση που η εισαγωγή κόμβου στο [[#Figure2 | σχήμα 2]] γίνει δεξί παιδί του @@b@@, τότε έχουμε την περίπτωση της [[#RL | Δεξιάς - Αριστερής Περιστροφής]].
20-02-2008 (11:14)
από Aris -
Πρόσθεση σειράς 1:
%define=frame block bgcolor=#ddddff border="1px dashed blue"%
Αλλαγή σειρών 8-19 από:
Η εισαγωγή γίνεται όπως στα δυαδικά δέντρα. Αν η εισαγωγή διαταράξει την ισορροπία κόμβων πρέπει αυτή να αποκατασταθεί.
!!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
[@
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f
σε:
Η εισαγωγή γίνεται όπως στα δυαδικά δέντρα. Αν η εισαγωγή διαταράξει την ισορροπία κόμβων πρέπει αυτή να αποκατασταθεί. Η αποκατάσταση γίνεται κάνοντας περιστροφή των κόμβων των οποίων η ισορροπία διαταράχθηκε. Πριν δούμε, λοιπόν, τις περιπτώσεις εισαγωγής κόμβου, θα δούμε πρώτα τις δυνατές περιστροφές.
!!! Περιστροφές
!!!! [[#LL]]Απλή Αριστερή Περιστροφή (LL)
Έχουμε το παρακάτω τμήμα ενός δέντρου.
%frame%[@
a B(a)=1-0 => B(a)=1
\
b B(b)=0
Αλλαγή σειρών 21-29 από:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
[@
c B(c)=2-2 => B(c)=0
/ \
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
σε:
[[#Figure1| Σχήμα 1]]
Αν γίνει εισαγωγή κόμβου ως δεξί παιδί @@b@@, το δέντρο γίνεται:
%frame%[@
a B(a)=2-0 => B(a)=2
\
b B(b)=1-0 => B(c)=1
\
c B(c)=0
Αλλαγή σειρών 33-43 από:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
Σε περίπτωση
!! [[#LL]]Απλή Αριστερή Περιστροφή (LL)
Έχουμε το παρακάτω τμήμα ενός δέντρου.
[@
a B(a)=1-0 => B(a)=1
\
b B(b)=0
σε:
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@a@@ η οποία λύνεται με τα παρακάτω βήματα
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@b@@
(:comment # Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@ :)
Έτσι, το δέντρο γίνεται:
%frame%[@
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(b)=0
Αλλαγή σειρών 45-52 από:
Γίνεται εισαγωγή του @@c@@. Το δέντρο γίνεται:
[@
a B(a)=2-0 => B(a)=2
\
b B(b)=1-0 => B(c)=1
\
c B(c)=0
σε:
Σε περίπτωση που η εισαγωγή στο
!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
Έχουμε το παρακάτω τμήμα ενός δέντρου:
%frame%[@
c B(c)=0-1 => B(c)=-1
/
b B(b)=0
Αλλαγή σειρών 56-66 από:
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@a@@ η οποία λύνεται με τα παρακάτω βήματα
σε:
Γίνεται εισαγωγή του @@a@@. Το δέντρο γίνεται:
%frame%[@
c B(c)=0-2 => B(c)=-2
/
b B(b)=0-1 => B(b)=-1
/
a B(a)=0
@]
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@c@@ η οποία λύνεται με τα παρακάτω βήματα
Αλλαγή σειρών 68-70 από:
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@b@@
(:comment # Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@ :)
σε:
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
(:comment # Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@ :)
Αλλαγή σειράς 72 από:
σε:
Αλλαγή σειράς 75 από:
σε:
Αλλαγή σειρών 78-85 από:
!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
Έχουμε το παρακάτω τμήμα ενός δέντρου:
[@
c B(c)=0-1 => B(c)=-1
/
b B(b)=0
σε:
!!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
%frame%[@
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
Αλλαγή σειρών 90-97 από:
Γίνεται εισαγωγή του @@a@@. Το δέντρο γίνεται:
[@
c B(c)=0-2 => B(c)=-2
/
b B(b)=0-1 => B(b)=-1
/
a B(a)=0
σε:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
%frame%[@
c B(c)=2-2 => B(c)=0
/ \
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
Αλλαγή σειρών 100-109 από:
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@c@@ η οποία λύνεται με τα παρακάτω βήματα
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
(:comment # Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@ :)
Έτσι, το δέντρο γίνεται:
[@
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(c)=0
σε:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
!! Εισαγωγή Κόμβου σε "Ψηλό" Υποδέντρο
Παίρνουμε πάλι το προηγούμενο δέντρο.
%frame%[@
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f B(d)=0, B(f)=0
Πρόσθεση σειρών 114-119:
Η εισαγωγή τώρα γίνεται στο "ψηλό" υποδέντρο, το οποίο σε αυτή την περίπτωση είναι το δεξί. Διακρίνουμε δύο περιπτώσεις:
# Η εισαγωγή γίνεται ως δεξί παιδί του κόμβου f
20-02-2008 (10:50)
από Aris -
Αλλαγή σειρών 5-8 από:
!! [[#LL]]Απλή Αριστερή Περιστροφή (LL)
Έχουμε το παρακάτω τμήμα ενός δέντρου.
σε:
!! Εισαγωγή Κόμβου
Η εισαγωγή γίνεται όπως στα δυαδικά δέντρα. Αν η εισαγωγή διαταράξει την ισορροπία κόμβων πρέπει αυτή να αποκατασταθεί.
!!! Εισαγωγή Κόμβου σε "Κοντό" Υποδέντρο
Ας πάρουμε παράδειγμα το παρακάτω δέντρο.
Αλλαγή σειρών 14-16 από:
a B(a)=1-0 => B(a)=1
\
b B(b)=0
σε:
c B(c)=2-1 => B(c)=-1
/ \
b e B(b)=0, B(e)=1-1 => B(e)=0
/ \
d f
Αλλαγή σειρών 21-22 από:
Γίνεται εισαγωγή του @@c@@. Το δέντρο γίνεται:
σε:
Το δέντρο είναι ισορροπημένο αφού κανένας κόμβος δεν βρίσκεται εκτός του εύρους [-1, 1]. Αν γίνει εισαγωγή κόμβου ο οποίος θα έχει "πατέρα" τον κόμβο @@b@@, τότε δεν υπάρχει ανάγκη αναδιοργάνωσης του δέντρου. Αν, για παράδειγμα, γίνει εισαγωγή του @@a@@, το δέντρο γίνεται:
Αλλαγή σειρών 24-28 από:
a B(a)=2-0 => B(a)=2
\
b B(b)=1-0 => B(c)=1
\
c B(c)=0
σε:
c B(c)=2-2 => B(c)=0
/ \
b e B(b)=0-1 => B(b)=-1, B(e)=1-1 => B(e)=0
/ / \
a d f B(a)=0, B(d)=0, B(f)=0
Αλλαγή σειρών 31-36 από:
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@a@@ η οποία λύνεται με τα παρακάτω βήματα
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@b@@
(:comment # Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@ :)
Έτσι, το δέντρο γίνεται:
σε:
Βλέπουμε ότι η ισορροπία δεν διαταράσσεται. Το ίδιο θα συνέβαινε αν η εισαγωγή γινόταν ως δεξί παιδί του κόμβου @@b@@.
Σε περίπτωση
!! [[#LL]]Απλή Αριστερή Περιστροφή (LL)
Έχουμε το παρακάτω τμήμα ενός δέντρου.
Αλλαγή σειρών 39-41 από:
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(b)=0
σε:
a B(a)=1-0 => B(a)=1
\
b B(b)=0
Αλλαγή σειρών 44-47 από:
!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
Έχουμε το παρακάτω τμήμα ενός δέντρου:
σε:
Γίνεται εισαγωγή του @@c@@. Το δέντρο γίνεται:
Αλλαγή σειρών 47-49 από:
c B(c)=0-1 => B(c)=-1
/
b B(b)=0
σε:
a B(a)=2-0 => B(a)=2
\
b B(b)=1-0 => B(c)=1
\
c B(c)=0
Αλλαγή σειρών 54-55 από:
Γίνεται εισαγωγή του @@a@@. Το δέντρο γίνεται:
σε:
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@a@@ η οποία λύνεται με τα παρακάτω βήματα
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@b@@
(:comment # Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@ :)
Έτσι, το δέντρο γίνεται:
Αλλαγή σειρών 61-65 από:
c B(c)=0-2 => B(c)=-2
/
b B(b)=0-1 => B(b)=-1
/
a B(a)=0
σε:
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(b)=0
Αλλαγή σειρών 66-71 από:
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@c@@ η οποία λύνεται με τα παρακάτω βήματα
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
(:comment # Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@ :)
Έτσι, το δέντρο γίνεται:
σε:
!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
Έχουμε το παρακάτω τμήμα ενός δέντρου:
Πρόσθεση σειρών 71-92:
c B(c)=0-1 => B(c)=-1
/
b B(b)=0
@]
Γίνεται εισαγωγή του @@a@@. Το δέντρο γίνεται:
[@
c B(c)=0-2 => B(c)=-2
/
b B(b)=0-1 => B(b)=-1
/
a B(a)=0
@]
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@c@@ η οποία λύνεται με τα παρακάτω βήματα
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
(:comment # Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@ :)
Έτσι, το δέντρο γίνεται:
[@
Αλλαγή σειρών 96-97 από:
σε:
20-02-2008 (10:08)
από Aris -
Αλλαγή σειρών 3-4 από:
Ένα δέντρο AVL είναι ένας ειδικός τύπος δυαδικού δέντρου που είναι πάντα "μερικώς" ισορροπημένο. Το κριτήριο που χρησιμοποιείται για να καθορίσει το βαθμό ισορροπίας είναι η διαφορά μεταξύ των υψών των υποδέντρων και μιας ρίζας στο δέντρο. Το "ύψος" του δέντρου είναι ο "αριθμός επιπέδων" στο δέντρο. Ή για να είναι πιο σωστό, το ύψος ενός δέντρου καθορίζεται ως εξής:
σε:
(:comment Ένα δέντρο AVL είναι ένας ειδικός τύπος δυαδικού δέντρου που είναι πάντα "μερικώς" ισορροπημένο. Το κριτήριο που χρησιμοποιείται για να καθορίσει το βαθμό ισορροπίας είναι η διαφορά μεταξύ των υψών των υποδέντρων και μιας ρίζας στο δέντρο. Το "ύψος" του δέντρου είναι ο "αριθμός επιπέδων" στο δέντρο. Ή για να είναι πιο σωστό, το ύψος ενός δέντρου καθορίζεται ως εξής: :)
Πρόσθεση σειρών 7-8:
Έχουμε το παρακάτω τμήμα ενός δέντρου.
Αλλαγή σειράς 10 από:
σε:
Αλλαγή σειρών 12-14 από:
c B(c)=1-1 => B(c)=0
/ \
b e
σε:
Αλλαγή σειρών 15-18 από:
# Ο κόμβος @@c@@ γίνεται η νέα ρίζα
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@c@@
# Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@
σε:
Γίνεται εισαγωγή του @@c@@. Το δέντρο γίνεται:
Αλλαγή σειρών 18-20 από:
c B(c)=1-2 => B(c)=-1
/ \
a e B(a)=1-0 => B(a)=1, B(e)=0
σε:
Αλλαγή σειρών 20-22 από:
σε:
b B(b)=1-0 => B(c)=1
\
c B(c)=0
Αλλαγή σειρών 25-26 από:
!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
σε:
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@a@@ η οποία λύνεται με τα παρακάτω βήματα
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@b@@
(:comment # Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@ :)
Έτσι, το δέντρο γίνεται:
Διαγραφή σειρών 31-32:
Αλλαγή σειράς 34 από:
σε:
Αλλαγή σειρών 37-40 από:
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
# Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@
σε:
!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
Έχουμε το παρακάτω τμήμα ενός δέντρου:
Αλλαγή σειρών 42-44 από:
b B(b)=2-1 => B(b)=1
/ \
a c B(a)=0, B(c)=0-1 => B(c)=-1
σε:
Αλλαγή σειρών 44-66 από:
σε:
b B(b)=0
@]
Γίνεται εισαγωγή του @@a@@. Το δέντρο γίνεται:
[@
c B(c)=0-2 => B(c)=-2
/
b B(b)=0-1 => B(b)=-1
/
a B(a)=0
@]
Έχουμε διαταραχή της ισορροπίας για τον κόμβο @@c@@ η οποία λύνεται με τα παρακάτω βήματα
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
(:comment # Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@ :)
Έτσι, το δέντρο γίνεται:
[@
b B(b)=1-1 => B(b)=0
/ \
a c B(a)=0, B(c)=0
19-02-2008 (20:50)
από Aris -
Αλλαγή σειρών 5-6 από:
!! [[#LL]]Απλή Αριστερή Περιστροφή
σε:
!! [[#LL]]Απλή Αριστερή Περιστροφή (LL)
Αλλαγή σειράς 20 από:
σε:
Αλλαγή σειράς 22 από:
σε:
a e B(a)=1-0 => B(a)=1, B(e)=0
Πρόσθεση σειρών 25-46:
@]
!! [[#RR]]Απλή Δεξιά Περιστροφή (RR)
[@
c B(c)=0-2 => B(c)=-2
/
b B(b)=1-1 => B(b)=0
/ \
a e
@]
# Ο κόμβος @@b@@ γίνεται η νέα ρίζα
# Ο κόμβος @@c@@ γίνεται δεξί παιδί του κόμβου @@b@@
# Το δεξί παιδί του κόμβου @@b@@ γίνεται αριστερό παιδί του κόμβου @@c@@
[@
b B(b)=2-1 => B(b)=1
/ \
a c B(a)=0, B(c)=0-1 => B(c)=-1
/
e
19-02-2008 (20:42)
από Aris -
Αλλαγή σειρών 3-25 από:
Ένα δέντρο AVL είναι ένας ειδικός τύπος δυαδικού δέντρου που είναι πάντα "μερικώς" ισορροπημένο. Το κριτήριο που χρησιμοποιείται για να καθορίσει το βαθμό ισορροπίας είναι η διαφορά μεταξύ των υψών των υποδέντρων και μιας ρίζας στο δέντρο. Το "ύψος" του δέντρου είναι ο "αριθμός επιπέδων" στο δέντρο. Ή για να είναι πιο σωστό, το ύψος ενός δέντρου καθορίζεται ως εξής:
σε:
Ένα δέντρο AVL είναι ένας ειδικός τύπος δυαδικού δέντρου που είναι πάντα "μερικώς" ισορροπημένο. Το κριτήριο που χρησιμοποιείται για να καθορίσει το βαθμό ισορροπίας είναι η διαφορά μεταξύ των υψών των υποδέντρων και μιας ρίζας στο δέντρο. Το "ύψος" του δέντρου είναι ο "αριθμός επιπέδων" στο δέντρο. Ή για να είναι πιο σωστό, το ύψος ενός δέντρου καθορίζεται ως εξής:
!! [[#LL]]Απλή Αριστερή Περιστροφή
[@
a B(a)=2-0 => B(a)=2
\
c B(c)=1-1 => B(c)=0
/ \
b e
@]
# Ο κόμβος @@c@@ γίνεται η νέα ρίζα
# Ο κόμβος @@a@@ γίνεται αριστερό παιδί του κόμβου @@c@@
# Το αριστερό παιδί του κόμβου @@c@@ γίνεται δεξί παιδί του κόμβου @@a@@
[@
c
/ \
a e
\
b
@]
19-02-2008 (19:55)
από Aris -
Αλλαγή σειρών 1-3 από:
http://users.sch.gr/fergadis/images/under_construction.jpg
σε:
! AVL Δέντρα (Ισορροπημένα)
Ένα δέντρο AVL είναι ένας ειδικός τύπος δυαδικού δέντρου που είναι πάντα "μερικώς" ισορροπημένο. Το κριτήριο που χρησιμοποιείται για να καθορίσει το βαθμό ισορροπίας είναι η διαφορά μεταξύ των υψών των υποδέντρων και μιας ρίζας στο δέντρο. Το "ύψος" του δέντρου είναι ο "αριθμός επιπέδων" στο δέντρο. Ή για να είναι πιο σωστό, το ύψος ενός δέντρου καθορίζεται ως εξής:
09-02-2008 (21:09)
από Aris -
Πρόσθεση σειράς 1:
http://users.sch.gr/fergadis/images/under_construction.jpg