CODEWITHSUNDEEP
algorithmdata-structureslanguage-agnosticb-tree
user20614
user20614

Reputation: 19

How to insert duplicate keys into b trees

Please answer on b trees and not b+ trees. I have 2 questions.

  1. What happens when you insert duplicated keys to a b tree? For the following input how will the b tree with t=3 look like? 1,1,1,1,1,1,1,1,1,1,1,1,1,1

  2. Can a parent node in a b tree with t=3 look like this? 1,1,4,10? If so will the son between the key "1" and the second key" 1" contain only the value "1" ?

Upvotes: 1

Views: 3162

Answers (1)

perreal
perreal

Reputation: 97948

Just like hash tables, each node in the tree should store a link to a list of items associated with that key. You will store unique keys in the tree but the links will point to a list with possibly multiple items:

[node, key=1, ptr=l], l={1,1,1,1,1,1,1...}

Upvotes: 5

Related Questions