Δυαδικό Δέντρο Αναζήτησης

Οδηγίες

Εισήγαγε και αναζήτησε αριθμούς σε ένα δυαδικό δέντρο.

Όταν χρειάζεται να αναπαραστήσουμε ταξινομημένα δεδομένα, ο πίνακας δεν αποτελεί καλή δομή δεδομένων.

Ας πούμε ότι έχουμε τον πίνακα [1, 3, 4, 5] και προσθέτουμε το 2, οπότε γίνεται [1, 3, 4, 5, 2]. Τώρα πρέπει να ταξινομήσουμε ξανά ολόκληρο τον πίνακα! Μπορούμε να το βελτιώσουμε αν συνειδητοποιήσουμε ότι χρειάζεται μόνο να κάνουμε χώρο για το νέο στοιχείο [1, nil, 3, 4, 5] και μετά να προσθέσουμε το στοιχείο στον χώρο που δημιουργήσαμε. Αλλά και πάλι αυτό απαιτεί να μετατοπίσουμε πολλά στοιχεία κατά μία θέση.

Τα Δυαδικά Δέντρα Αναζήτησης, ωστόσο, μπορούν να λειτουργήσουν σε ταξινομημένα δεδομένα πολύ πιο αποδοτικά.

Ένα δυαδικό δέντρο αναζήτησης αποτελείται από μια σειρά συνδεδεμένων κόμβων. Κάθε κόμβος περιέχει ένα στοιχείο δεδομένων (π.χ. τον αριθμό 3), μια μεταβλητή με όνομα left και μια μεταβλητή με όνομα right. Οι μεταβλητές left και right δείχνουν στο nil ή σε άλλους κόμβους. Επειδή αυτοί οι άλλοι κόμβοι έχουν με τη σειρά τους άλλους κόμβους από κάτω τους, λέμε ότι οι μεταβλητές left και right δείχνουν σε υποδέντρα. Όλα τα δεδομένα στο αριστερό υποδέντρο είναι μικρότερα ή ίσα με τα δεδομένα του τρέχοντος κόμβου και όλα τα δεδομένα στο δεξί υποδέντρο είναι μεγαλύτερα από τα δεδομένα του τρέχοντος κόμβου.

Για παράδειγμα, αν είχαμε έναν κόμβο που περιέχει το δεδομένο 4 και προσθέταμε το δεδομένο 2, το δέντρο μας θα έμοιαζε κάπως έτσι:

      4
     /
    2

Αν μετά προσθέταμε το 6, θα έμοιαζε κάπως έτσι:

      4
     / \
    2   6

Αν μετά προσθέταμε το 3, θα έμοιαζε κάπως έτσι

       4
     /   \
    2     6
     \
      3

Και αν μετά προσθέταμε το 1, το 5 και το 7, θα έμοιαζε κάπως έτσι

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

Αναγνώριση

Οι εικόνες δημιουργήθηκαν από τον habere-et-dispertire χρησιμοποιώντας το PGF/TikZ του Till Tantau.