Ένα δέντρο K-D (ονομάζεται επίσης και ως K-Dimensional Tree) είναι ένα δυαδικό δέντρο αναζήτησης όπου τα δεδομένα σε κάθε κόμβο είναι ένα K- Σημείο διαστάσεων στο διάστημα … Σημεία προς τα αριστερά αυτού του χώρου αντιπροσωπεύονται από το αριστερό υποδέντρο αυτού του κόμβου και τα σημεία στα δεξιά του χώρου αντιπροσωπεύονται από το δεξί υποδέντρο.
Είναι το KD Tree ακριβές;
Τα σημεία δεδομένων χωρίζονται σε κάθε κόμβο σε δύο σύνολα. Όπως ο προηγούμενος αλγόριθμος, το KD Tree είναι επίσης ένας αλγόριθμος δυαδικού δέντρου που καταλήγει πάντα σε δύο το πολύ κόμβους… Στη δεξιά πλευρά της παρακάτω εικόνας, μπορείτε να δείτε την ακριβή θέση του σημεία δεδομένων, στην αριστερή πλευρά η χωρική τους θέση.
Πώς φτιάχνεις ένα δέντρο KD;
Building KD-Tree
- Το πρώτο σημείο που εισάγεται γίνεται ρίζα του δέντρου.
- Επιλέξτε άξονα με βάση το βάθος, έτσι ώστε ο άξονας να περνάει από όλες τις έγκυρες τιμές. …
- Ταξινομήστε τη λίστα σημείων ανά άξονα και επιλέξτε τη διάμεσο ως στοιχείο περιστροφής. …
- Διασχίστε το δέντρο μέχρι να αδειάσει ο κόμβος και, στη συνέχεια, εκχωρήστε σημείο σε κόμβο.
- Επαναλάβετε το βήμα 2-4 επαναλαμβανόμενα μέχρι να γίνει επεξεργασία όλων των σημείων.
Γιατί χρησιμοποιούμε το δέντρο kd;
Τα
KD-trees είναι μια συγκεκριμένη δομή δεδομένων για την αποτελεσματική αναπαράσταση των δεδομένων μας Ειδικότερα, τα KD-trees βοηθούν στην οργάνωση και την κατάτμηση των σημείων δεδομένων βάσει συγκεκριμένων συνθηκών. Τώρα, θα κάνουμε κάποιες τομές ευθυγραμμισμένες με τον άξονα και θα διατηρήσουμε λίστες σημείων που εμπίπτουν σε κάθε ένα από αυτά τα διαφορετικά δοχεία.
Είναι το octree ένα δέντρο kd;
Τα δεδομένα κάθε κόμβου φύλλου σε οκτάδες αποτελούν ένα τοπικό δέντρο KD. Στην οκτάδα, οι κόμβοι αποθηκεύουν μόνο τις πληροφορίες τους σχετικά με το πλαίσιο οριοθέτησης. Σε κάθε κόμβο φύλλου δίνεται μια τιμή δείκτη για τη διευκόλυνση της έρευνας.
