Εξεταστικη σε Δομες δεδομενων.

[gon1332]

Μαλλον εννοει siblings, τους κομβους που ειναι στο ιδιο υψος (το "αδερφακι" και τα "ξαδερφια").

 

3)Αν καθε κομβος εχει ενα παιδι (ειναι σαν αλυσίδα) τοτε εχει min=h κομβους. 

Αν ειναι πληρες δεντρο τοτε εχει max= 1+2+4+8+...+2^h=2^h+1-1 κομβους

Με αυτήν την έννοια αρκεί να αποδείξεις με ένα αντιπαράδειγμα

ότι δεν ισχύει το ζητήμενο:

             (α)
        .----` `----.
      -`             `-
     (β)             (γ)
    -` `-            -`
  -`     `-        -`
 (δ)     (ε)      (ζ)

Ο δ έχει δύο θυγατρικούς (ε, ζ) και ο προκάτοχός του (β) έχει δεξιό θυγατρικό (γ).

 

WTF; Μήπως ήταν ερώτηση παγίδα;

[albNik]

Με αυτήν την έννοια αρκεί να αποδείξεις με ένα αντιπαράδειγμα

ότι δεν ισχύει το ζητήμενο:

             (α)
        .----` `----.
      -`             `-
     (β)             (γ)
    -` `-            -`
  -`     `-        -`
 (δ)     (ε)      (ζ)

Ο δ έχει δύο θυγατρικούς (ε, ζ) και ο προκάτοχός του (β) έχει δεξιό θυγατρικό (γ).

 

WTF; Μήπως ήταν ερώτηση παγίδα;

Μπορει να αναφερεται σε αυτό 

http://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree

[Alithinos]

 

Alithinos ναι...ξερω οτι γινεται.Αλλα ξερω επισης οτι γινεται να εχει και δεξιο.

Αν ξερεις να μου πεις εστω υπο ποια προυποθεση δεν βαζουμε δεξιο θυγατρικο στον προκατοχο του.Γιατι η ερωτηση ειναι αποδειξη και καλα.

 

Η απάντηση στο γιατί ο προκάτοχος δεν έχει δεξί child, είναι επειδή η αξία του 'προκατόχου' είναι η max value.

Γιατί στα δεξιά ενός κόμβου Χ βάζουμε πάντα κόμβο με αξία μεγαλύτερη ή ίση της αξίας που κρατά ο κόμβος Χ.

 

Το σκεπτικό του Binary Search Tree, είναι ότι με αυτό το τρόπο μπορείς να ψάξεις να βρεις κάτι που υπάρχει σε μια λίστα, χωρίς να πρέπει ο επεξεργαστής να ελέγξει το κάθε μέλος της λίστας ξεχωριστά.

Έτσι ξεκινά η αναζήτηση από έναν κόμβο, και στη μια μεριά του (αριστερή) βάζεις μια τιμή μικρότερη, ενώ στα δεξιά του μια μεγαλύτερη.

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

Έτσι η εύρεση της αναζήτησης θα επιτευχθεί πιο γρήγορα,μιας και ο επεξεργαστής δεν θα χρειαστεί να ακουμπήσει και να συγκρίνει κάποια μέλη της λίστας καν.

 

 

 

Στην άσκηση που σου έδωσαν, υπάρχουν τέσσερεις κόμβοι, τους οποίους ας τους ονομάσουμε Χ,Ψ,Ω,Ζ, και για αυτούς ξέρουμε ότι:

 

 

Ο κόμβος Ψ, είναι left child του Χ.

Ο κόμβος Ω, είναι left child του Ψ.

Ο κόμβος Ζ, είναι right child του Ψ.

 

 

Αφού ένα left child θα έχει πάντα αξία ίση ή μικρότερη του parent του, και ένα right child μεγαλύτερη ή ίση, ξέρουμε πως ισχύουν τα εξής:

 

Ψ <= Χ

Ω <=Ψ

Ζ >= Ψ

 

Χ >= Ψ

Χ >= Ω

Χ >= Ζ

 

Άρα Χ είναι το Max Value του δέντρου. Η έλλειψη δεξιού θυγατρικού στον Χ σημαίνει αυτόματα πως ο Χ έχει τη μεγαλύτερη αξία μεταξύ των Χ,Ψ,Ω,Ζ. Ο Χ δεν έχει δεξί παιδί, επειδή δεν υπάρχει αξία μεγαλύτερη απ' την αξία του Χ, στο σύνολο κόμβων που μας δίνεται.

 

Ένας κόμβος Χ δεν έχει δεξί θυγατρικό, εφόσων οι κόμβοι του κλαδιού (branch) που ξετυλίγεται κάτω απ τον Χ, έχουν αξίες μικρότερες του Χ.

 

 

 

 

 

υ.γ.

 

θυγατρικός = child

κόμβος = node

σχετικά με το μπέρδεμα binary tree / binary search tree:

 

A binary search tree is a special kind of binary tree designed to improve the efficiency of searching through the contents of a binary tree. Binary search trees exhibit the following property: for any node n, every descendant node's value in the left subtree of n is less than the value of n, and every descendant node's value in the right subtree is greater than the value of n.

Επεξ/σία 17 Ιανουαρίου 2015 από Alithinos

[Alithinos]

Εγώ πάντως αν ήμουν καθηγητής θα σας έβαζα διαφορετική άσκηση για αυτό το θέμα. 

 

Θα έλεγα:

 

"Το binary search tree της Εικόνας 1 είναι τελείως unoptimized. Σχεδιάστε ένα binary search tree με τις ίδιες αξίες κόμβων, ώστε ο αριθμός nodes που θα πρέπει να ελέγξει ο επεξεργαστής για να βρει κάποιον αριθμό, να είναι ο μικρότερος δυνατός!"

 

 

Εικόνα 1

 

 

 

Λύση:

 

[albNik]

Και ποιος σε εμποδίζει να προσθεσεις ενα right child στο Χ? Δλδ εναν αριθμο >Χ

[Alithinos]

Και ποιος σε εμποδίζει να προσθεσεις ενα right child στο Χ? Δλδ εναν αριθμο >Χ

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

 

Το ερώτημα του παιδιού ήταν υπό ποια προϋπόθεση δεν βάζουμε right child στον Χ, ε λοιπόν η προϋπόθεση για να μην βάλεις right child στο Χ, είναι να μην υπάρχει στο σύνολό σου κάτι με μεγαλύτερη αξία απ' του Χ.

 

---

 

Αν έχεις τους αριθμούς 1,2,3,4,5 και θέλεις αυτούς συγκεκριμένα να τους βάλεις σε BST,και βάλεις τον 5 ως Χ, ε δε θα μπορείς μετά να βάλεις right child στον X! 

[zisis13]

Μμμμ το καταλαβα.Ευχαριστω πολυ ολους σας που βοηθησατε και τον alithino που προσπαθησε να καταλαβει τι ζηταει ο καθηγητης μου...μιας που εγω δεν εβγαζα ακρη ετσι οπως ειναι η εκφωνηση.Φαντασου ποσο ποιο διαφορετικα εισαι την ωρα της εξετασης χωρις καθαρο μυαλο και ιντερνετ ευκαιρο.