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

Οδηγίες

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

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

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

Υλοποίηση

Η υλοποίηση μιας αποδοτικής και τροποποιήσιμης δομής δέντρου στη Cairo (ή σε οποιαδήποτε καθαρά συναρτησιακή γλώσσα με αμετάβλητη μνήμη) είναι δύσκολη, γιατί αυτές οι γλώσσες είναι σχεδιασμένες να αποφεύγουν την αλλαγή των δεδομένων αφού δημιουργηθούν. Αυτή η αμεταβλητότητα σημαίνει ότι, αντί να ενημερώνεις απευθείας έναν κόμβο του δέντρου, πρέπει να δημιουργείς μια νέα εκδοχή του δέντρου κάθε φορά που το τροποποιείς.

Για να δείξουμε γιατί συμβαίνει αυτό, φαντάσου μια απλή δομή δυαδικού δέντρου όπου κάθε κόμβος έχει ένα αριστερό και ένα δεξί παιδί. Ας πούμε ότι ξεκινάμε με ένα μικρό δέντρο σαν αυτό:

       1
      / \
     2   3

Τώρα, ας υποθέσουμε ότι θέλουμε να προσθέσουμε έναν νέο κόμβο 4 ως το αριστερό παιδί του κόμβου 2. Σε μια καθαρά συναρτησιακή γλώσσα (όπως στη Cairo ή στη Haskell), η μνήμη είναι αμετάβλητη, οπότε δεν μπορούμε απλώς να προσθέσουμε τον κόμβο 4 απευθείας στο 2. Αντ' αυτού, πρέπει να δημιουργήσουμε μια νέα εκδοχή κάθε κόμβου κατά μήκος της διαδρομής από τη ρίζα μέχρι τον τροποποιημένο κόμβο, γιατί κάθε κόμβος σε αυτή τη διαδρομή δείχνει πλέον σε ένα νέο ή τροποποιημένο υποδέντρο.

Να πώς θα έμοιαζε η διαδικασία:

1. Προσθήκη του κόμβου 4 στον κόμβο 2:

   • Δημιούργησε μια νέα εκδοχή του κόμβου 2, ο οποίος τώρα έχει το 4 ως αριστερό παιδί.

       2'
      / 
     4   
   

2. Ενημέρωση του κόμβου ρίζας:

   • Επειδή ο κόμβος 1 αρχικά έδειχνε στο παλιό 2, δημιουργούμε μια νέα εκδοχή του κόμβου ρίζας 1' που τώρα δείχνει στον ενημερωμένο κόμβο 2' στα αριστερά και κρατά τον κόμβο 3 στα δεξιά.

       1'
      / \
     2'  3
   

Έτσι, το δέντρο που προκύπτει γίνεται:

       1'
      / \
     2'  3
    /
   4

Αυτό το νέο δέντρο (1') εξακολουθεί να μοιάζει με το αρχικό, αλλά με μια ενημερωμένη διαδρομή. Το βασικό σημείο είναι ότι έπρεπε να δημιουργήσουμε ξανά κάθε κόμβο κατά μήκος της διαδρομής (1 έως 2) για να διατηρήσουμε την αμεταβλητότητα, αφού οι υπάρχοντες κόμβοι δεν μπορούν να τροποποιηθούν επί τόπου. Το αρχικό δέντρο εξακολουθεί να υπάρχει (για παράδειγμα, για όλες τις αναφορές στην αρχική του ρίζα 1), ενώ αυτό το νέο δέντρο αντιπροσωπεύει την τροποποιημένη κατάσταση.

Σε μεγάλα δέντρα, αυτή η προσέγγιση μπορεί να γίνει δαπανηρή, καθώς κάθε νέα τροποποίηση απαιτεί τη δημιουργία ξανά μιας διαδρομής κόμβων από τη ρίζα μέχρι τον ενημερωμένο κόμβο, ακόμα κι αν στην πραγματικότητα αλλάζει μόνο ένα μικρό μέρος του δέντρου.