Πως να βρω το κατάλληλο μονοπάτι για τα φύλλα σε Δέντρο C

[pagratios]

Σε μία εργασία πρέπει να φτιάξουμε ένα hash tree στο οποίο δεσμεύουμε όλους τους κόμβους και τα φύλλα ξέροντας το height και το fanout, δηλαδή δεν το φτιάχνουμε δυναμικά σε κάθε εισαγωγή σελίδας επίσης είναι πλήρης δέντρο έχοντας σε κάθε επίπεδο όλους τους κόμβους.

 

Τώρα έχοντας το δέντρο δεσμευμένο δεν ξέρω πως θα βρω το κατάλληλο μονοπάτι για το φύλλο που θα αποθηκεύσω την σελίδα.

 

πχ. Σε ένα δέντρο ύψους 4(δλδ 0 1 2 3) με fanout 3 το οποίο έχει 3^3 φύλλα (δλδ id 0-26) πως θα βρω ότι το σωστό μονοπάτι για την σελίδα 16 είναι το 1 2 1?

 

φαντάζομαι κάποια διαίρεση με κατάλληλα νούμερα αλλά δεν μπορώ(πλην του πρώτου μονοπατιού) τα επόμενα.

[bird]

Για δοκίμασε αυτό:

...
	
	for ( i = 1; i <= height; i++ ){
		route = (page/(int)pow(fanout,(height-i))) ;
		page -= (route)*(int)pow(fanout, height-i);
		printf("%d ",route);
	}

...

Αν το i το ξεκινήσεις από το 0 τότε πρεπει να αλλάξει η δύναμη σε (height-i+1)

Το page είναι το id και τα height & fanout όπως τα δηλωσες παραπάνω...

 

Πιθανόν να υπάρχει και πιο σύντομος τρόπος, αλλά αυτό μου ήρθε τώρα...

[pagratios]

Ευχαριστώ για την βοήθεια. Θα το δοκιμάσω στην πρώτη ευκαιρία.

Edit: αν έχουμε ύψος 4 το δέντρο έχει τα επίπεδα 0 για την ρίζα μέχρι το 3 για τα φύλλα. Μήπως πρέπει να κάνω pow(fanout, height-2-i) αν ξεκινήσω την for με i=0

Επεξ/σία 23 Μαΐου 2013 από pagratios

[pagratios]

Το δοκίμασα και λειτουργεί.

 

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

[bird]

Ευχαριστώ για την βοήθεια. Θα το δοκιμάσω στην πρώτη ευκαιρία.

 

Edit: αν έχουμε ύψος 4 το δέντρο έχει τα επίπεδα 0 για την ρίζα μέχρι το 3 για τα φύλλα. Μήπως πρέπει να κάνω pow(fanout, height-2-i) αν ξεκινήσω την for με i=0

Παρακαλώ, δεν κάνει τίποτα

 

Αν δεν έχω κάνει κάποιο λάθος, δουλεύει γενικά για οποιαδήποτε τιμή του height & fanout...