Δυαδικά δένδρα αναζήτησης

[gpapava]

Καλησπέρα παιδιά.

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

 

Έστω οτι έχουμε τα στοιχεία 10, 11, 20, 21, 22, 2, 3, 4, 14, 24 και θέλουμε να τα εισάγουμε σε ένα άδειο δυαδικό δένδρο αναζήτησης.

Παίζει ρόλο η σειρά καταρχήν; Και από που θα ξεκινήσω; Επειδή η σειρά είναι αύξουσα το δένδρο καταλήγει αρκετά προς τα κάτω.

 

Μπορείτε να μου δώσετε τα φώτα σας;;

Ευχαριστώ

[bnvdarklord]

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

[gpapava]

Ύψους 5 το βγάζω εγώ. Δηλαδή 5 επίπεδα. Κάνω κάτι λάθος;

 

Και κάτι ακόμα φίλε. Ξέρεις μήπως ποιο είναι το βασικό μειονέκτημα ενός δυαδικού δένδρου αναζήτησης; Έχω κάτι παλιά θέματα και δεν βρίσκω απάντηση με τπτ.

 

Ευχαριστώ πολύ για την βοήθεια.

[bnvdarklord]

Αν μετράς την ρίζα 0 τοτε 5 ύψος.

 

Λογικα το μειονέκτημα ειναι ότι δεν ειναι ισοζυγισμένα, και έτσι υπαρχουν περιπτώσεις(οπως η δικη σου) που θα γινονται περισσοτερες συγκρισεις από οτι το ιδανικό δεντρο αναζήτησης.

[Luffy-san]

http://en.wikipedia.org/wiki/Binary_search_tree

 

οριζεις ως αριστερο γιο στοιχειο με μικροτερο νουμερο και δεξι γιο με μεγαλυτερο.

η σειρα προφανως παιζει ρολο

 

αρχικα θα μπουν καπως ετσι:

 

10

2| |

11

|

20

|21

|22

 

Παρατηρησε οτι αν σου ερχεται συνεχεια στοιχειο μεγαλυτερο ( ή μικροτερο ) απο το προηγουμενο , τοτε εχεις στην ουσια λιστα....

Κοιτα και τα AVL ωστε να μην εχεις κατι τετοιο,δηλαδη να κρατας το υψος του δεντρου

http://en.wikipedia.org/wiki/AVL_tree

 

edit: shit....χαλια φαινεται....βαριεμαι να το κανω σωστα

[gpapava]

Σωστά το κάνω;;

Έφτιαξα ένα σχηματάκι στην ζωγραφική.

 

Για τα AVL βρήκα αυτό το λινκ με περιστροφές κτλ πολύ καλό.

Link

[bnvdarklord]

To 20 ειναι μεγαλυτερο απο το 11 αρα παει δεξια του.

[gpapava]

Φίλε μπορείς να κάνεις ένα πρόχειρο σχήμα αν μπορείς;;

[bnvdarklord]

Ορίστε.

 

.........10

....../..... \

.....2.......11

......\........\

.......3.........20

........\......./...\

.........4.....14....21

.........................\

.......................22

.........................\

.........................24

[gpapava]

Μόλις έκανα και εγώ το ίδιο ακριβώς.

Ευχαριστώ πολύ παιδιά.