Μια μη γραμμική δομή δεδομένων αποτελείται από μια συλλογή των στοιχείων που κατανέμονται σε ένα επίπεδο, πράγμα που σημαίνει ότι δεν υπάρχει τέτοια αλληλουχία μεταξύ των στοιχείων όπως υπάρχει σε μια δομή γραμμικών δεδομένων.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | Δέντρο | Γραφική παράσταση |
|---|---|---|
| Μονοπάτι | Μόνο μία μεταξύ δύο κορυφών. | Επιτρέπονται περισσότερες από μία διαδρομές. |
| Κόμβος ρίζας | Έχει ακριβώς έναν κόμβο ρίζας. | Το γράφημα δεν έχει έναν root κόμβο. |
| Βρόχους | Δεν επιτρέπονται βρόχοι. | Το γράφημα μπορεί να έχει βρόχους. |
| Περίπλοκο | Λιγότερο σύνθετο | Πιο περίπλοκο συγκριτικά |
| Τεχνικές ταχυτήτων | Προ-παραγγελία, εντός παραγγελίας και μετά την παραγγελία. | Έρευνα για πρώτη αναζήτηση και αναζήτηση βάθους πρώτα. |
| Αριθμός ακμών | n-1 (όπου n είναι ο αριθμός κόμβων) | Μη καθορισμένο |
| Τύπος μοντέλου | Ιεραρχικός | Δίκτυο |
Ορισμός του δέντρου
Ένα δέντρο είναι μια πεπερασμένη συλλογή δεδομένων που συνήθως ονομάζονται κόμβοι. Όπως αναφέρθηκε παραπάνω, ένα δέντρο είναι μια μη γραμμική δομή δεδομένων που οργανώνει τα στοιχεία δεδομένων με ταξινομημένη σειρά. Χρησιμοποιείται για την εμφάνιση μιας ιεραρχικής δομής μεταξύ των διαφόρων στοιχείων δεδομένων και οργανώνει τα δεδομένα σε κλάδους που αφορούν τις πληροφορίες. Η προσθήκη μιας νέας άκρης σε ένα δέντρο οδηγεί σε σχηματισμό του βρόχου ή του κυκλώματος.
Υπάρχουν διάφοροι τύποι δέντρων όπως ένα δυαδικό δέντρο, δυαδικό δέντρο αναζήτησης, δέντρο AVL, δυαδικό δένδρο με σπειρώματα, δέντρο B, κλπ. Η συμπίεση δεδομένων, η αποθήκευση αρχείων, ο χειρισμός της αριθμητικής έκφρασης και τα δέντρα παιχνιδιών αποτελούν μέρος της εφαρμογής του δέντρου δομή δεδομένων.
Ιδιότητες του δέντρου:
- Υπάρχει καθορισμένος κόμβος στην κορυφή του δέντρου που είναι γνωστός ως ρίζα του δέντρου.
- Τα υπόλοιπα στοιχεία δεδομένων χωρίζονται σε υποσύνολα disjoint που αναφέρονται ως subtree.
- Το δέντρο επεκτείνεται σε ύψος προς τα κάτω.
- Ένα δέντρο πρέπει να συνδεθεί που σημαίνει ότι πρέπει να υπάρχει μια διαδρομή από τη μια ρίζα σε όλους τους άλλους κόμβους.
- Δεν περιέχει βρόχους.
- Ένα δέντρο έχει n-1 άκρες.
Υπάρχουν διάφοροι όροι που σχετίζονται με τα δέντρα όπως ο τερματικός κόμβος, η άκρη, το επίπεδο, ο βαθμός, το βάθος, το δάσος κλπ. Μεταξύ αυτών των όρων, μερικές από αυτές περιγράφονται παρακάτω.
- Edge - Μια γραμμή που συνδέει δύο κόμβους.
- Επίπεδο - Ένα δέντρο χωρίζεται σε επίπεδα τέτοια ώστε ο κόμβος ρίζας να βρίσκεται στο επίπεδο 0. Στη συνέχεια, τα άμεσα παιδιά του βρίσκονται στο επίπεδο 1 και τα άμεσα παιδιά του βρίσκονται στο επίπεδο 2 και ούτω καθεξής μέχρι τον τερματικό ή τον κόμβο των φύλλων.
- Βαθμός - Είναι ο αριθμός των υποστρωμάτων ενός κόμβου σε ένα δεδομένο δέντρο.
- Βάθος - Είναι το μέγιστο επίπεδο κάθε κόμβου σε ένα δεδομένο δέντρο και επίσης γνωστό ως ύψος .
- Τερματικός κόμβος - Ο κόμβος του υψηλότερου επιπέδου είναι τερματικός κόμβος ενώ άλλοι κόμβοι εκτός από τον τερματικό και τον κόμβο ρίζας είναι γνωστοί ως μη τερματικοί κόμβοι.
Ορισμός του γραφήματος
Ένα γράφημα είναι επίσης μια μαθηματική μη γραμμική δομή δεδομένων που μπορεί να αντιπροσωπεύει διάφορα είδη φυσικής δομής. Αποτελείται από μια ομάδα κορυφών (ή κόμβων) και σύνολο ακμών που συνδέουν τις δύο κορυφές. Οι κορυφές στο γράφημα αντιπροσωπεύονται ως σημείο ή κύκλοι και οι άκρες εμφανίζονται ως τόξα ή τμήματα γραμμής. Μια άκρη αντιπροσωπεύεται από το E (v, w) όπου v και w είναι τα ζεύγη κορυφών. Η αφαίρεση μιας άκρης από ένα κύκλωμα ή ένα συνδεδεμένο γράφημα δημιουργεί μια υπογράμμιση που είναι ένα δέντρο.
Τα γραφήματα ταξινομούνται σε διάφορες κατηγορίες, όπως κατευθυνόμενα, μη κατευθυνόμενα, συνδεδεμένα, μη συνδεδεμένα, απλά και πολλαπλά γραφήματα. Το δίκτυο υπολογιστών, το σύστημα μεταφοράς, το γράφημα του κοινωνικού δικτύου, τα ηλεκτρικά κυκλώματα και ο σχεδιασμός του έργου είναι μερικές από τις εφαρμογές της δομής δεδομένων των γραφημάτων. Χρησιμοποιείται επίσης στην τεχνική διαχείρισης με την ονομασία PERT (τεχνική αξιολόγησης προγράμματος και ανασκόπησης) και CPM (μέθοδος κρίσιμης διαδρομής) στην οποία αναλύεται η δομή του γραφήματος.
Ιδιότητες ενός γράφου:
- Μια κορυφή σε ένα γράφημα μπορεί να συνδεθεί σε οποιοδήποτε αριθμό άλλων κορυφών χρησιμοποιώντας ακμές.
- Μια άκρη μπορεί να προσανατολιστεί ή να κατευθυνθεί.
- Μια άκρη μπορεί να σταθμιστεί.
Στο γράφημα χρησιμοποιούμε επίσης διάφορους όρους όπως γειτονικές κορυφές, διαδρομή, κύκλο, βαθμό, συνδεδεμένο γράφημα, πλήρες γράφημα, σταθμισμένο γράφημα κλπ. Ας καταλάβουμε ορισμένους από αυτούς τους όρους.
- Οι γειτονικές κορυφές - Μια κορυφή a είναι δίπλα στην κορυφή b εάν υπάρχει μια άκρη (a, b) ή (b, a).
- Διαδρομή - Μια διαδρομή από τυχαία κορυφή w είναι μια παρακείμενη ακολουθία κορυφών.
- Κύκλος - Πρόκειται για ένα μονοπάτι όπου οι πρώτες και τελευταίες κορυφές είναι οι ίδιες.
- Βαθμός - Είναι ένας αριθμός ακμών που προσπίπτουν σε μια κορυφή.
- Συνδεδεμένο γράφημα - Εάν υπάρχει διαδρομή από τυχαία κορυφή σε οποιαδήποτε άλλη κορυφή, τότε αυτό το γράφημα είναι γνωστό ως συνδεδεμένο γράφημα.
Βασικές διαφορές μεταξύ δέντρου και γραφήματος
- Σε ένα δέντρο υπάρχει μόνο μία διαδρομή μεταξύ οποιωνδήποτε δύο κορυφών, ενώ ένα γράφημα μπορεί να έχει μονόδρομες και αμφίδρομες διαδρομές μεταξύ των κόμβων.
- Στο δέντρο υπάρχει ακριβώς ένας κόμβος ρίζας και κάθε παιδί μπορεί να έχει μόνο έναν γονέα. Αντιθέτως, σε ένα γράφημα, δεν υπάρχει έννοια του κόμβου ρίζας.
- Ένα δέντρο δεν μπορεί να έχει βρόχους και αυτο-βρόχους, ενώ το γράφημα μπορεί να έχει βρόχους και αυτο-βρόχους.
- Τα γράμματα είναι πιο περίπλοκα καθώς μπορεί να έχουν βρόχους και αυτο-βρόχους. Σε αντίθεση, τα δέντρα είναι απλά σε σύγκριση με το γράφημα.
- Το δέντρο μεταφέρεται χρησιμοποιώντας τεχνικές προπαραγγελίας, εντός παραγγελίας και μετά την παραγγελία. Από την άλλη πλευρά, για τη διασταύρωση γραφημάτων, χρησιμοποιούμε BFS (Breadth First Search) και DFS (Depth First Search).
- Ένα δέντρο μπορεί να έχει n-1 άκρες. Αντίθετα, στο γράφημα δεν υπάρχει προκαθορισμένος αριθμός ακμών και εξαρτάται από το γράφημα.
- Ένα δέντρο έχει μια ιεραρχική δομή ενώ το γράφημα έχει ένα μοντέλο δικτύου.
συμπέρασμα
Το γράφημα και το δέντρο είναι η μη γραμμική δομή δεδομένων που χρησιμοποιείται για την επίλυση διαφόρων σύνθετων προβλημάτων. Ένα γράφημα είναι μια ομάδα κορυφών και ακμών όπου μια άκρη συνδέει ένα ζεύγος κορυφών, ενώ ένα δέντρο θεωρείται ως ένα ελάχιστα συνδεδεμένο γράφημα το οποίο πρέπει να συνδεθεί και να μην έχει βρόχους.
