FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!


2, 3 Trees (data structures)





davidv
For the past 12 weeks I've been implementing data structures working my way up from simple circularly doubly linked lists to complicated trees like red-black, 2,4 and 2,3. Anyway so right now for an assignment I'm implementing a 2, 3 tree in Java.

So I have a quick question, for past data structures I've had to deal with duplicate keys such as skiplists and BSTs. Some data structures like treaps I didn't have to (randomized priorities). How do I deal with duplicate keys in 2,3 trees? My implementation implements the Dictionary interface and as such, I've read that dictionary, unlike some data structures has the ability to allow for duplicate keys. I'm not sure how I account for duplicate keys without having some kind of auxiliary data structure and still maintain O(logn) guaranteed running time.

EDIT: I take it no one knows much about data structures. So what I thought was to employ something similar to Python's update feature in their dictionaries. Replacing a value V when a duplicate key K is encountered. Since the tree is ordered based on K changing V doesn't effect the structure.
Related topics
[OFFICIAL] What are you currently reading?
Creating a new Operating System
Programming links, info, and tutorials
The best mobile Phone
Computer Science Education
Mod Projects lots of info
PHP VS ASP
Who hates PDFs?
Loving PHP
data structures
I'm having problems understanding keys
[PHP] Some beginner questions
New endeavour: C programming language
Python: Sequences
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.