Mound - online παζλ

Mound (επίσης γνωστό ως σωρός ή σωρός) - μια δομή δεδομένων που βασίζεται σε δέντρο στην οποία οι τιμές των απογόνων του κόμβου βρίσκονται σε συνεχή σχέση με την τιμή του γονέα (για παράδειγμα, η τιμή του γονέα δεν είναι μικρότερη από την τιμή του απογόνου του).

Πλήρης ανάχωμα

Εάν το ανάχωμα πρόκειται να είναι πλήρες ανάχωμα, τότε πρέπει να πληρούνται οι ακόλουθες προϋποθέσεις:

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

Τα φύλλα στο τελευταίο επίπεδο τακτοποιούνται με συνέπεια από αριστερά προς τα δεξιά.

Ιδιότητες των αναχωμάτων

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

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

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

Εάν το παιδί έχει αριθμό

        n

        .

    {\ displaystyle n,}

   αυτός ο πατέρας έχει

        n

          /

        2

    {\ displaystyle n / 2}

   (π.χ. για 7, ο πατέρας έχει τον αριθμό 3). Χρησιμοποιούμε τη λειτουργία ολικής διαίρεσης.

Εάν ο πατέρας έχει αριθμό

        n

        .

    {\ displaystyle n,}

   τότε το αριστερό παιδί έχει έναν αριθμό

        2

        n

        .

    {\ displaystyle 2n,}

   και σωστά

        2

        n

        +

        1.