Σχετικα με αλγοριθμο

[nik324]

Θα θελα να εχω στο μυαλο μου ενα αλγοριθμο ο οποιος κανε merge ενα δεντρο και μια ταξινομημενη λιστα σε μια νεα ταξινομημενη λιστα σε χρονο O(n+m) οπου m ειναι το πληθος των στοιχείων του δεντρου και n ειναι το πληθος των στοιχειων της λιστα.

 

Δεν προκυται για εργασια,  απλως θα θελα να το εχω στο μυαλο μου σαν διαδικασια.

 

Αυτο που εχω σκεφτει μεχρι στιγμης ειναι οτι θα πρεπει να υπαρχει καποια συναρτηση εισαγωγης με δεικτη tail ετσι ωστε να κανουμε την εισαγωγη στην νεα λιστα σε γραμμικο χρονο Ο(1)

 

Ακουω τις ιδεες σας

[albNik]

Δε νομίζω να μπορείς να εισάγεις σε ταξινομημένη λίστα σε Ο(1) διότι έχει αργή προσπέλαση.  Αν ειναι π.χ. στη θέση k και πρεπει να πας στην k+10 για να εισάγεις ενα στοιχείο κάνεις 10 βηματα (next->next->...).

[nik324]

Δε νομίζω να μπορείς να εισάγεις σε ταξινομημένη λίστα σε Ο(1) διότι έχει αργή προσπέλαση.  Αν ειναι π.χ. στη θέση k και πρεπει να πας στην k+10 για να εισάγεις ενα στοιχείο κάνεις 10 βηματα (next->next->...).

Επειδη καθος θα διασχιζουμε το δεντρο σε inorder θα περνουμε τα κλειδια του σε αυξουσα διαταξη.. Η λιστα και αυτη ειναι ταξινομημενη..Οποτε καθε φορα που θα εισαγουμε ενα στοιχειο στη νεα λιστα τοτε αυτο θα ειναι το μαγαλυτερο καθε φορά απο ολα οσα υπαρχουν ηδη στη λιστα...Αρα μπορουμε να το βαλουμε στο τελος της λιστα σε χρονο Ο(1) κανοντας χρηση του δεικτη tail.

 

Το θεμα ειναι πως θα γινει συγχρονος διασχιση της λιστας και του δεντρου μαζι... Εκει το χανω λιγο με τις αναδρομες

[albNik]

Επειδη καθος θα διασχιζουμε το δεντρο σε inorder θα περνουμε τα κλειδια του σε αυξουσα διαταξη.. 

 

Αυτο γενικά δεν ισχυει   Νομίζω υπήρχε ένα thread πιο πριν ποια δεντρα έχουν αυτή την ιδιότητα 

 

Δυο ταξινομιμένς λίστες εννοειται αννονονται σε Ο(n+m)

[nik324]

Αυτο δεν μας δινει τις τιμες του δεντρου σε αυξουσα διαταξη;

 

1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

 

 

Δεν εχω καταλαβει μαλλον τι εννοεις

[albNik]

Δεν έχουν όλα τα δυαδικα αυτη την ιδιότητα 

 

http://www.insomnia.gr/topic/467655-αλγοριθμική-ερώτηση/?p=52344213

 

 

Αυτό το δεντρο ειναι δυαδικο ιδιο στη δομή 

             2

           /   \

          /      \

         5       1

          \      /

           4   3

 

 με αυτό 

            3

           /   \

          /      \

        4       2

          \      /

           1   5

 

αλλα δινουν διαφορετικη λίστα όταν διασχίζονται (inorder, postorder...)

[nik324]

Ε ενταξ

 

Εστω οτι την εχει αυτη την ιδιοτητα.... Δυαδικο δεντρο με τα κλειδια ου σε αυξουσα διαταξη αν το διατρεχουμε σε Inorder

[albNik]

Ε τοτε δεντρο + λιστα  σε μια νέα λιστα όπως κανουμε 

Site: https://www.google.gr/search?q=merge+two+sorted+lists&oq=merge+two+sorted+list&aqs=chrome.1.57j0l3j62.14443j0&sourceid=chrome&ie=UTF-8">merge two sorted lists

[nilosgr]

Κραταμε εναν δεικτη στη λιστα κι εναν στο δεντρο, εστω Λ και Δ. Αυτοι οι δεικτες δειχνουν στο μικροτερο στοιχειο που δεν εχει μπει στη νεα λιστα. Και εστω Α η νεα λιστα:

while "Δ, Λ δεν ειναι null":
    Μ = min(Λ, Δ)
    Α.add(M)
    if M == Λ :
        "ανανεωσε το Λ"
    else :
        "ανανεωσε το Δ"

if "Λ ειναι null":
    Α.addAll(Δεντρο)
if "Δ ειναι null":
    Α.addAll(Λιστα)

[nik324]

Το προβλημα μου δεν ειναι γενικα ο τροπος και η γενικότερη λογική του αλγοριθμου αλλά το πως θα διατρεχω το δεντρο σε inorder ετσι ωστε να περνω τα κλειδια σε αυξουσα σειρά και αναλογα να πηγαινω στο επομενο στοιχειο της λιστας η στο επομενο στοιχειο του δεντρου...

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

 

Αν ειναι να κανω ενα παραγειγμα

 

Μαλλον που θα το σκεφτω με διασχηση του δεντρο με χρηση στοιβας

 

 

Συγκεκριμενα το "while" που εχεις βαλει παραπανω ειναι το προβλημα μου...Το καταλαβαινω πως το εννοεις εκει

αλλα δεν θελω αλγοριθμο σε τοσο "υψηλο επιπεδο"

[nilosgr]

Θα πρεπει τα παιδια, στο δεντρο, να εχουν δεικτη προς τον πατερα ή με στοιβα οπως ειπες

[nik324]

Θα πρεπει τα παιδια, στο δεντρο, να εχουν δεικτη προς τον πατερα ή με στοιβα οπως ειπες

Kαι αν δεν εχουμε parent pointer δεν μπορουμε στην αναδρομική κληση να περναμε παντα το προηγουμενο κομβο που ειναι παντα ο πατερας, δλδ καπως ετσι για την κληση :

funct (node->lc , node);
funct (node->rc , node);

[albNik]

Πέρνα στην func και ένα δεικτη της λιστας και της merged λιστας (ή να τις έχεις global).

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

[nilosgr]

Αν μιλάμε για C, τότε πρέπει να "προσομοιώσεις" της iterator methods της Python. (προφανώ αυτό, με "σπατάλη" μνήμης έχει κόστος Ο(1)). Μια καλή ιδέα είναι να έχεις στη συνάρτηση που θα επιστρέφει το Δ -βλέπε ψευδοκώδικα που έδωσα παραπάνω- να έχει 2 static μεταβλητές. Μια που θα είναι η στοίβα με τα αριστερά παιδιά και έναν int που θα λέει σε πόσο ύψος βρίσκεσαι.

 

Βέβαια αν το δούμε καθαρά θεωρητικά, η μετατροπή του δέντρου σε λίστα κοστίζει Ο(m) άρα το Ο(n+m) πάλι δεν το ξεπερνάς