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

Οδηγίες

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

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

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