By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
438,798 Members | 1,349 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 438,798 IT Pros & Developers. It's quick & easy.

Java data structure

P: 9
I. Description

You are to create a red-black tree which supports only the operations listed below. All operations should have time complexity O(log n) when there are n items in the tree, this is the guarantee that red-black trees give. The class should be derived from the TreeMap class in java.util.

The only operations which this class supports are:

public boolean is Empty()
public void makeEmpty()
public void insert(Comparable x) throws DuplicateItem
public void delete(Comparable x) throws ItemNotFound
public void deleteMin() throws ItemNotFound
public void deleteMax() throws ItemNotFound
public Object find(Comparable x) throws ItemNotFound
public Object findMin() throws ItemNotFound
public Object findMax() throws ItemNotFound

Your class should be named RBTree

II. Notes

In no particular order
• TreeMap expects Object and the requirement for RBTree is Comparable
• TreeMap doesn’t throw any reasonable checked exceptions. Your RBTree class does.
• TreeMap expects to perform a mapping of keys to data. RBTree doesn’t. You may find this to present a problem if you’re not careful in the way you implement some of the methods.
• The methods in the above list are the only methods that RBTree supports.
Dec 12 '06 #1
Share this Question
Share on Google+
2 Replies


sicarie
Expert Mod 2.5K+
P: 4,677
I. Description

You are to create a red-black tree which supports only the operations listed below. All operations should have time complexity O(log n) when there are n items in the tree, this is the guarantee that red-black trees give. The class should be derived from the TreeMap class in java.util.

The only operations which this class supports are:

public boolean is Empty()
public void makeEmpty()
public void insert(Comparable x) throws DuplicateItem
public void delete(Comparable x) throws ItemNotFound
public void deleteMin() throws ItemNotFound
public void deleteMax() throws ItemNotFound
public Object find(Comparable x) throws ItemNotFound
public Object findMin() throws ItemNotFound
public Object findMax() throws ItemNotFound

Your class should be named RBTree

II. Notes

In no particular order
• TreeMap expects Object and the requirement for RBTree is Comparable
• TreeMap doesn’t throw any reasonable checked exceptions. Your RBTree class does.
• TreeMap expects to perform a mapping of keys to data. RBTree doesn’t. You may find this to present a problem if you’re not careful in the way you implement some of the methods.
• The methods in the above list are the only methods that RBTree supports.
http://www.thescripts.com/forum/thread575495.html
http://www.thescripts.com/forum/thread575307.html
http://www.thescripts.com/forum/thread575002.html

All point to:

http://www.thescripts.com/forum/thread571397.html

Please make an attempt to do the problem, and post what you have tried, and the error messages you get, instead of just trying to get other people to do your work for you. (You will get much more help that way)
Dec 12 '06 #2

10K+
P: 13,264
I. Description

You are to create a red-black tree which supports only the operations listed below. All operations should have time complexity O(log n) when there are n items in the tree, this is the guarantee that red-black trees give. The class should be derived from the TreeMap class in java.util.

The only operations which this class supports are:

public boolean is Empty()
public void makeEmpty()
public void insert(Comparable x) throws DuplicateItem
public void delete(Comparable x) throws ItemNotFound
public void deleteMin() throws ItemNotFound
public void deleteMax() throws ItemNotFound
public Object find(Comparable x) throws ItemNotFound
public Object findMin() throws ItemNotFound
public Object findMax() throws ItemNotFound

Your class should be named RBTree

II. Notes

In no particular order
• TreeMap expects Object and the requirement for RBTree is Comparable
• TreeMap doesn’t throw any reasonable checked exceptions. Your RBTree class does.
• TreeMap expects to perform a mapping of keys to data. RBTree doesn’t. You may find this to present a problem if you’re not careful in the way you implement some of the methods.
• The methods in the above list are the only methods that RBTree supports.
And when you post what you'll have done, remember to use the code tags
Dec 13 '06 #3

Post your reply

Sign in to post your reply or Sign up for a free account.