Τι είναι το quadtree;

Ένα quadtree είναι μια δομή που μοιάζει με δέντρο που βασίζεται στη δύναμη των τεσσάρων και χρησιμοποιείται για την οργάνωση αρχείων σε μια βάση δεδομένων.Κάθε γονέας, ή εκκίνηση, ο κόμβος έχει τέσσερις παιδικούς κόμβους και κάθε παιδί κατέχει ένα ορισμένο ποσό δεδομένων.Όταν το όριο των δεδομένων διαρρέει πάνω από τα όρια του, τέσσερα παιδιά θα κατασκευαστούν από αυτόν τον κόμβο.Υπάρχουν δύο κύριες δομές quadtree: η περιοχή και το δέντρο σημείων, το καθένα ελαφρώς διαφορετικό στο σχεδιασμό.Ενώ ένα quadtree χρησιμοποιείται συχνότερα με βάσεις δεδομένων, μπορεί επίσης να χρησιμοποιηθεί για να βρει εικονοστοιχεία σε δισδιάστατες (2D) εικόνες, επειδή τα εικονοστοιχεία σε μια εικόνα 2D μπορούν πάντα να χωριστούν σε τέσσερα μέρη.φτιαγμένο με γονέα, κλάδο, κόμβους και παιδί, ή φύλλα, κόμβους.Ο γονέας είναι το σημείο εκκίνησης και περιέχει δεδομένα βασισμένα σε κατηγορία, ενώ το παιδί κατέχει αρχεία και έγγραφα.Σε ένα quadtree, κάθε γονέας πρέπει να έχει τέσσερα παιδιά.Ενώ πρέπει να υπάρχουν τέσσερα παιδιά, δεν πρέπει όλα τα παιδιά να περιέχουν δεδομένα.Όσοι δεν είναι γνωστοί ως μηδενικοί κόμβοι.Αυτοί οι μηδενικοί κόμβοι συχνά παραμένουν στάσιμοι και περιμένουν δεδομένα.

Κάθε παιδικός κόμβος σε ένα τετράγωνο έχει ένα όριο δεδομένων.Αυτό το όριο καθορίζεται συνήθως από το συνολικό μέγεθος της βάσης δεδομένων.Όταν υπάρχουν τόσα πολλά στοιχεία που ωθεί πέρα από το όριο, ο κόμβος του παιδιού γίνεται γονικός κόμβος με ουσιαστικά τη γέννηση mdash;Δημιουργία τεσσάρων παιδιών κόμβων που καταλαμβάνουν όλα τα επιπλέον δεδομένα.Συνήθως θα υπάρχουν ένας ή δύο μηδενικοί κόμβοι από αυτή τη δημιουργία, αλλά αυτό εξαρτάται εξ ολοκλήρου από το πόσα δεδομένα ήταν στον κόμβο.

Υπάρχουν δύο κύρια quadtrees: περιοχή και σημείο.Η περιοχή Quadtree χρησιμοποιείται για την αποσύνθεση μιας ολόκληρης περιοχής 2D σε τμήματα με βάση τη δύναμη των τεσσάρων mdash.όπως τέσσερα, οκτώ ή 16 μέρη mdash;και συχνά χρησιμοποιούνται για παραστάσεις.Αυτή η δομή είναι καλύτερη για εικόνες ή γραφήματα πεδίου δεδομένων.Η έκδοση σημείων είναι σαν ένα δυαδικό δέντρο και χρησιμοποιείται καλύτερα με παραγγελθέντα σημεία.Αυτή η παραλλαγή είναι επίσης ένα πραγματικό δέντρο, επειδή υπάρχει ένα κεντρικό σημείο από το οποίο όλοι οι κόμβοι άνοιξη, σε αντίθεση με την έκδοση της περιοχής στην οποία οι κόμβοι είναι διάσπαρτοι.

Η πιο συνηθισμένη χρήση του Quadtree είναι να διαχωρίσει και να οργανώσει μια βάση δεδομένων, αλλάΑυτή δεν είναι η μόνη χρήση του.Οι αλγόριθμοι που έγιναν για να βρουν ένα συγκεκριμένο εικονοστοιχείο σε μια εικόνα που συνήθως χρησιμοποιούν quadtrees, επειδή κάθε εικονοστοιχείο σε μια εικόνα μπορεί να διαχωριστεί σε τέσσερα ίσα μέρη.Αυτό κάνει τα quadtrees μοναδικά κατάλληλα για την αναζήτηση εικονοστοιχείων.