Σε αυτό το σεμινάριο, θα μάθετε για τη δομή δεδομένων δέντρων. Επίσης, θα μάθετε για διαφορετικούς τύπους δέντρων και τις ορολογίες που χρησιμοποιούνται στο δέντρο.
Ένα δέντρο είναι μια μη γραμμική ιεραρχική δομή δεδομένων που αποτελείται από κόμβους συνδεδεμένους με άκρα.
Ενα δέντρο
Γιατί δομή δεδομένων δέντρου;
Άλλες δομές δεδομένων όπως πίνακες, συνδεδεμένη λίστα, στοίβα και ουρά είναι γραμμικές δομές δεδομένων που αποθηκεύουν δεδομένα διαδοχικά. Προκειμένου να εκτελεστεί οποιαδήποτε λειτουργία σε μια γραμμική δομή δεδομένων, η χρονική πολυπλοκότητα αυξάνεται με την αύξηση του μεγέθους των δεδομένων. Όμως, δεν είναι αποδεκτό στον σημερινό υπολογιστικό κόσμο.
Διαφορετικές δομές δεδομένων δέντρων επιτρέπουν ταχύτερη και ευκολότερη πρόσβαση στα δεδομένα, καθώς είναι μια μη γραμμική δομή δεδομένων.
Ορολογίες δέντρων
Κόμβος
Ένας κόμβος είναι μια οντότητα που περιέχει ένα κλειδί ή τιμή και δείχνει τους θυγατρικούς κόμβους της.
Οι τελευταίοι κόμβοι κάθε διαδρομής ονομάζονται κόμβοι φύλλων ή εξωτερικοί κόμβοι που δεν περιέχουν σύνδεσμο / δείκτη προς θυγατρικούς κόμβους.
Ο κόμβος που έχει τουλάχιστον έναν θυγατρικό κόμβο ονομάζεται εσωτερικός κόμβος .
Ακρη
Είναι ο σύνδεσμος μεταξύ των δύο κόμβων.
Κόμβοι και άκρα ενός δέντρου
Ρίζα
Είναι ο κορυφαίος κόμβος ενός δέντρου.
Ύψος κόμβου
Το ύψος ενός κόμβου είναι ο αριθμός των άκρων από τον κόμβο στο βαθύτερο φύλλο (δηλ. Η μεγαλύτερη διαδρομή από τον κόμβο προς έναν κόμβο φύλλων).
Βάθος κόμβου
Το βάθος ενός κόμβου είναι ο αριθμός των άκρων από τη ρίζα προς τον κόμβο.
Ύψος ενός δέντρου
Το ύψος ενός δέντρου είναι το ύψος του ριζικού κόμβου ή το βάθος του βαθύτερου κόμβου.
Ύψος και βάθος κάθε κόμβου σε ένα δέντρο
Βαθμός κόμβου
Ο βαθμός ενός κόμβου είναι ο συνολικός αριθμός κλάδων αυτού του κόμβου.
Δάσος
Μια συλλογή από διαχωρισμένα δέντρα ονομάζεται δάσος.
Δημιουργία δάσους από ένα δέντρο
Μπορείτε να δημιουργήσετε ένα δάσος κόβοντας τη ρίζα ενός δέντρου.
Τύποι δέντρων
- Δυαδικό δέντρο
- Δυαδικό δέντρο αναζήτησης
- Δέντρο AVL
- Β-δέντρο
Διασχίζοντας το δέντρο
Για να εκτελέσετε οποιαδήποτε λειτουργία σε ένα δέντρο, πρέπει να μεταβείτε στον συγκεκριμένο κόμβο. Ο αλγόριθμος διέλευσης δέντρων βοηθά στην επίσκεψη ενός απαιτούμενου κόμβου στο δέντρο.
Για να μάθετε περισσότερα, επισκεφθείτε τη διασταύρωση δέντρων.
Εφαρμογές δέντρων
- Τα δυαδικά δέντρα αναζήτησης (BST) χρησιμοποιούνται για να ελέγχουν γρήγορα εάν υπάρχει ένα στοιχείο σε ένα σύνολο ή όχι.
- Ο σωρός είναι ένα είδος δέντρου που χρησιμοποιείται για το είδος του σωρού.
- Μια τροποποιημένη έκδοση ενός δέντρου που ονομάζεται Tries χρησιμοποιείται στους σύγχρονους δρομολογητές για την αποθήκευση πληροφοριών δρομολόγησης.
- Οι πιο δημοφιλείς βάσεις δεδομένων χρησιμοποιούν B-Trees και T-Trees, που είναι παραλλαγές της δομής του δέντρου που μάθαμε παραπάνω για να αποθηκεύσουμε τα δεδομένα τους
- Οι μεταγλωττιστές χρησιμοποιούν ένα δέντρο σύνταξης για να επικυρώσουν τη σύνταξη κάθε προγράμματος που γράφετε.
