Φυλλοπροσανατολιζόμενο δυαδικό δέντρο αναζήτησης.

Ορισμός δέντρου.
Ένα φυλλοπροσανατολιζόμενο δυαδικό δέντρο αναζήτησης είναι ένα δέντρο στο οποίο ο κάθε εσωτερικός κόμβος έχει ένα ή δύο παιδιά. Τα στοιχεία της δομής S αποθηκεύονται στα φύλλα ενώ οι εσωτερικοί κόμβοι περιέχουν ενδιάμεσα στοιχεία τα οποία βοηθούν την αναζήτηση.
Πιο συγκεκριμένα:

Μια σημαντική ιδιότητα του δέντρου εύρεσης είναι ότι αν ένας εσωτερικός κόμβος v περιέχει μια  τιμή(v)=Κ, τότε  κάθε τιμή στο αριστερό υποδέντρο του v θα είναι μικρότερη του Κ ενώ κάθε τιμή στο δεξιό υποδέντρο θα είναι μεγαλύτερη του Κ. Κάτι τέτοιο μπορείτε να το παρατηρήσετε στην  εικόνα 1. 

Σε κάθε κόμβο v ορίζουμε το xrange(v) το οποίο είναι διάστημα τιμών [a,b]. To xrange(v) δείχνει το εύρος των στοιχείων που καλύπτουν το φύλλα του υποδέντρου με ρίζα v.  Με άλλα λόγια αποκλείεται κάποιο φύλλο u από το υποδέντρο αυτό να έχει τιμή(u) που να μην ανήκει στο xrange(v).

Τυπική εξήγηση για τιμή(v) και xrange(v)

Τιμή(v)

Η τιμή(v) κάθε κόμβου v υπολογίζεται ως η μέση τιμή των περιεχομένων των παιδιών του.
Έτσι τιμή(v)=( τιμή(αρ.παιδί(v))+τιμή(δεξ.παιδί(v)) )  .

 Η τιμή ενός κόμβου v εξαρτάται απο τις τιμές των παιδιών του. Έτσι μπορούμε να βρούμε σταδιακά ξεκινώντας από τα φύλλα την τιμή(v) κάθε κόμβου v.Στην εικόνα φαίνεται ότι η ρίζα έχει τιμή(ρίζας)=35 και ότι όλοι οι κόμβοι αριστερά της ρίζας έχουν τιμές μικρότερες του 35 ενώ δεξιά της ρίζας μεγαλύτερες του 35.

Εικόνα 1

 

Xrange(v)

Αντίθετα το xrange(v) κάθε κόμβου v υπολογίζεται άμα ξέρουμε το xrange και την τιμή(val()) του γονέα  του, όπως φαίνεται στον παρακάτω τύπο.

 
Δηλαδή το xrange(v) είναι ένα υποσύνολο του xrange(w) του γονέα, και το val(w) του γονέα είναι το δεξιό όριο στο xrange του αριστερού παιδιού. Για δεξί παιδί έχουμε το val(w) (τιμή(w))είναι αριστερό όριο στο xrange.

 Κομβοσύνολα P, C, Cmax.

Ορισμός : Δίνετε διάστημα ερώτησης Ι=[x0,y0]. Ορίζουμε τα σύνολα κόμβων P,C,Cmax σε σχέση με το I.

P

 P={v; xrange(v) Η [x0,y0]Ή0 και xrange(v)Λ[x0,y0]} 
Το P είναι ένα σύνολο κόμβων οι οποίοι έχουν την εξής ιδιότητα:
Το διάστημά τους τέμνει το I αλλά το xrange των κόμβων που ανήκουν στο P δέν περιέχεται στο I. Αντίθετα προσέξτε πως το I μπορεί να περιέχεται σε κάποιον κόμβο  v Ξ P.
Sorry, your browser doesn't support Java(tm). Δίπλα φαίνονται οι περιπτώσεις στις οποίες ένας κόμβος v ανήκει στο σύνολο P. Ή το x0 ή το y0 θα ανήκoυν στο xrange(v) ή τέλος και τα δύο, δηλαδή x0,y0 Ξ xrange(v).

 

Για το πλήθος των στοιχείων του συνόλου P ισχύει |P| £ 2h.
Δηλαδή το πλήθος του P είναι το πολύ ισο με το διπλάσιο του ύψους του δέντρου.

 

C

C={v; xrange(v) Ν I }
Το C είναι το σύνολο των κόμβων των οποίων το xrange είναι υποσύνολο του I.

Στη διπλανή εικόνα τα u1,u2,u3 ανήκουν στο C μια που τα xrange τους είνα υποσύνολα του I=[x0,y0].

 

 Για το πλήθος των στοιχείων του C ισχύει οτι αυτό είναι μικρότερο ή ισο με διπλάσιο του πλήθους των φύλλων των υποδέντρων που έχουν ρίζα κάποιο στοιχείο του Cmax.
|P| £ 2(# φύλλα v με xrange(v) Ν I )

Cmax

Cmax={v; vΞ C και πατέρας(v)Ο C}
 To Cmax είναι το σύνολο των κόμβων που ανήκουν στο C αλλά ο πατέρας τους δέν ανήκει στο C.
Αριστερά βλέπουμε πως το v ανήκει στο Cmax μια που το xrange του είναι υποσύνολο του [x0,y0]. Αντίθετα ο πατέρας του v δεν ανήκει στο C αλλά ανήκει στο P, επειδή τέμνει το I αλλά δεν περιέχεται σε αυτό.

 

 

ΛΗΜΜΑ.:Εστω Τ ένα δυικό δένδρο εύρεσης με ύψος h και έστω [x0,y0] ένα διάστημα ερώτησης. Τότε ισχύει:
a) |P|£2h
b)|Cmax| £2h
c)|C| £2(πλήθος φύλλων v με xrange(v)Ν I)

 

 

Κατανόηση συνόλων P,C,Cmax μέσω Applet.

Είναι σημαντικό κανείς να δεί την κατανομή των συνόλων P,C,Cmax σε ένα φυλλοπροσανατολιζόμενο δυικό δέντρο. Τα σύνολα αυτά φαίνονται πως κατανέμονται στο Search Tree Applet.