Algorith Theory Problem

[Επισκέπτης]

Διαβάζω ενα βιβλίο εδώ σε C algorithm analysis and data structures. 

Και είδα αυτό το προβληματάκι

An alternative way of performing a split at a node v in a (2,4) tree is to partition v into v′ and v″, with v' being a 2-node and v″ being a 3-node. Which of the keys k1, k2, k3, or k4 do we store at v’s parent in this case? Why?

Μπορεί να μου εξηγήσει κάποιος τι εννοεί ο ποιητής και πως θα μπορούσε να λυθεί ?

Σε οποιαδήποτε γλώσσα μιας και έχω βασικές γνώσεις στις ποιο πολλές.

[Lanike71]

Google έψαξες;

[Επισκέπτης]

Ναι εννοειτε δεν θα ανοιγα θεμα αλλιως !

[Lanike71]

Αυτό βοηθάει;

http://www.cse.unsw.edu.au/~cs9024/11s2/classes/24trees.pdf

[Επισκέπτης]

Δεν θα το ελεγα δεν καταλαβα καν τι ζηταει ακριβως.

[marios28]

3 ώρες πριν, Kugashira είπε

Δεν θα το ελεγα δεν καταλαβα καν τι ζηταει ακριβως.

Δεν έχω συναντήσει τέτοιου τύπου δέντρα. Από ό,τι βλέπω στo pdf του @Lanike71οι απαιτήσεις/ιδιότητες των (2,4) δέντρων είναι οι εξής:

1. Node-Size Property: every internal node has at most four children

2. Depth Property: all the external nodes have the same depth

Παράλληλα εξ' ορισμού ισχύουν:

1 Each internal node has at least two children and stores d -1 key-element items (ki, oi), where d is the number of children

2. For a node with children v1 v2 … vd storing keys k1 k2 … kd-1

         Κeys in the subtree of v1 are less than k1

         keys in the subtree of vi are between ki-1 and ki (i = 2, …, d - 1)

          keys in the subtree of vd are greater than kd-1

3. The leaves store no items and serve as placeholders

Δες τις διαφάνειες 7,8 (στο pdf) κατά την εισαγωγή (k, ο). Στην άσκηση (αυτό που ρωτάς) έχεις τα  k1,k2,k3,k4  (στη διαφάνεια είναι τα keys: 27, 30, 32, 35). Επειδή θα υπάρχει overflow (5-node) κατά την εισαγωγή του 30 (δεν θα ισχύει η 1η ιδιότητα/απαίτηση),  o κόμβος v χωρίζεται (splitting) στον v' (3-node) και v'' (2-node). Το κ3 (32), ανεβαίνει στον κόμβο u (στη διαφάνεια), οπότε δεν έχουμε overflow και παράλληλα διατηρούνται τα επίπεδα του δέντρου (depth) (2η ιδιότητα). Από ό,τι καταλαβαίνω στη δική σου άσκηση αναφέρει ο vi να είναι 2-node  (δηλαδή το 27 στο παράδειγμα) και ο vii 3-node (δηλαδή τα 32, 35), άρα (υποθέτω) θα ανέβει το k2 (δηλαδή το 30). Έτσι τα κατάλαβα εγώ, από τις διαφάνειες.

[Επισκέπτης]

@Lanike71 and @marios28 ευχαριστώ πολύ !! Βρήκα την λύση με την βοηθεια σας !