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
data structures
I'm having problems understanding keys
Programming links, info, and tutorials
Mod Projects lots of info
PHP VS ASP
Creating a new Operating System
Who hates PDFs?
[OFFICIAL] What are you currently reading?
Loving PHP
[PHP] Some beginner questions
New endeavour: C programming language
Python: Sequences
The best mobile Phone
Computer Science Education
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.