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

Οδηγίες

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

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

Ας πούμε ότι έχουμε τον πίνακα [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.