hyderman

Greenhorn

Posts: 3

posted 13 years ago

hi

i am trying to write this program and i dont know how to start. i will try to post code later, but i need some thing to start with.

thanx

main purpose:

To learn how to develop and use linked data structures.

The Sorted Interface

The sorted interface has the following methods for a data set of ints.

public void clear ();

This method will delete all items in the data set.

public int delete (int value);

This method will attempt to delete the item in the data set with the given value. If the item exists, the method will return the number of items that it had to examine to find the given item. If the item does not exist, the method will return -1 * the number of items examined.

public int find (int value);

This method will attempt to find the item in the data set with the given value. If the item exists, the method will return the number of items that it had to examine to find the given item. If the item does not exist, the method will return -1 * the number of items examined.

public int insert (int value);

This method will insert a new item into the data set with the given value. The method will return the number of items that it had to examine to find the location at which the new item should be inserted. Note: you may assume that no duplicate values will ever be inserted into the data set.

public void printAll ();

This method will print all items in the data set in ascending order.

The classfile for the interface is given here.

The Basic Node

To implement the linked data structure, you must use the following Node. This class holds four fields -- one int value and three links.

Node.class

The Linked Data Structure

For this program, you must implement the Sorted interface for a "Doubly Linked BST". This structure combines a BST with an extra link that points to the parent of each node (null for the root). The following shows an example:

insert (5)

(5)

insert (3)

(5)

/

(3)

insert (4)

(5)

/

(3)

\

(4)

find (4)

- current now points to Node "4"

printAncestors ()

- print the current Node and all of its ancestors -- 4 3 5

insert (6)

(5)

/ \

(3) (6)

\

(4)

delete (5)

(4)

/ \

(3) (6)

Remember, when deleting a Node from a binary search tree, there are four cases:

The Node is a leaf -- just delete the Node, and have the parent point to null.

The Node has no left child -- delete the Node, and have the parent point to the right child of the deleted Node.

The Node has no right child -- delete the Node, and have the parent point to the left child of the deleted Node.

The Node has two children -- have the parent point to the largest value in the left sub-tree of the deleted Node -- i.e. this value will replace the deleted Node in the BST.

Note: for the doubly linked BST, you may also have to update the parent link.

there are other files already created

http://hyderman.topcities.com/sam/Sorted.class

http://hyderman.topcities.com/sam/Node.class

http://hyderman.topcities.com/sam/Program1Base.java

http://hyderman.topcities.com/sam/Program1Driver.java

http://hyderman.topcities.com/sam/prog1.doc

http://hyderman.topcities.com/sam/output1.txt

http://hyderman.topcities.com/sam/input1.txt

i am trying to write this program and i dont know how to start. i will try to post code later, but i need some thing to start with.

thanx

main purpose:

To learn how to develop and use linked data structures.

The Sorted Interface

The sorted interface has the following methods for a data set of ints.

public void clear ();

This method will delete all items in the data set.

public int delete (int value);

This method will attempt to delete the item in the data set with the given value. If the item exists, the method will return the number of items that it had to examine to find the given item. If the item does not exist, the method will return -1 * the number of items examined.

public int find (int value);

This method will attempt to find the item in the data set with the given value. If the item exists, the method will return the number of items that it had to examine to find the given item. If the item does not exist, the method will return -1 * the number of items examined.

public int insert (int value);

This method will insert a new item into the data set with the given value. The method will return the number of items that it had to examine to find the location at which the new item should be inserted. Note: you may assume that no duplicate values will ever be inserted into the data set.

public void printAll ();

This method will print all items in the data set in ascending order.

The classfile for the interface is given here.

The Basic Node

To implement the linked data structure, you must use the following Node. This class holds four fields -- one int value and three links.

Node.class

The Linked Data Structure

For this program, you must implement the Sorted interface for a "Doubly Linked BST". This structure combines a BST with an extra link that points to the parent of each node (null for the root). The following shows an example:

insert (5)

(5)

insert (3)

(5)

/

(3)

insert (4)

(5)

/

(3)

\

(4)

find (4)

- current now points to Node "4"

printAncestors ()

- print the current Node and all of its ancestors -- 4 3 5

insert (6)

(5)

/ \

(3) (6)

\

(4)

delete (5)

(4)

/ \

(3) (6)

Remember, when deleting a Node from a binary search tree, there are four cases:

The Node is a leaf -- just delete the Node, and have the parent point to null.

The Node has no left child -- delete the Node, and have the parent point to the right child of the deleted Node.

The Node has no right child -- delete the Node, and have the parent point to the left child of the deleted Node.

The Node has two children -- have the parent point to the largest value in the left sub-tree of the deleted Node -- i.e. this value will replace the deleted Node in the BST.

Note: for the doubly linked BST, you may also have to update the parent link.

there are other files already created

http://hyderman.topcities.com/sam/Sorted.class

http://hyderman.topcities.com/sam/Node.class

http://hyderman.topcities.com/sam/Program1Base.java

http://hyderman.topcities.com/sam/Program1Driver.java

http://hyderman.topcities.com/sam/prog1.doc

http://hyderman.topcities.com/sam/output1.txt

http://hyderman.topcities.com/sam/input1.txt

posted 13 years ago

Hello Mr. Hyderman,

Welcome to JavaRanch!

Two things you need to know about the Ranch: first, we don't like to give out answers to homework problems. We're very happy to help you with answers to specific questions, or by critiquing your code; but don't ask people here to do your work for you, please. Show us what you've got, tell us what you need to do next, and people will be glad to help.

Second, you may not have read our naming policy on your way in; you'd best go read it now. Your display name needs to include both a real-sounding first and last name. You can adjust your display name here. Thanks, pardner!

Welcome to JavaRanch!

Two things you need to know about the Ranch: first, we don't like to give out answers to homework problems. We're very happy to help you with answers to specific questions, or by critiquing your code; but don't ask people here to do your work for you, please. Show us what you've got, tell us what you need to do next, and people will be glad to help.

Second, you may not have read our naming policy on your way in; you'd best go read it now. Your display name needs to include both a real-sounding first and last name. You can adjust your display name here. Thanks, pardner!

hyderman

Greenhorn

Posts: 3

posted 13 years ago

hi

thanx for replying, i am trying to write amethod to insert in BST

THE method will insert a new item into the data set with the given value.

THEN The method will return the number of items that it had to examine to find the location at which the new item should be inserted.

Pre-codition: no duplicate values will ever be inserted into the data set.

CODE:

public int insert (int val)

{

if (root==null)

{

root = new Node(value);

return 0;

}

return insertcode (val), root,0);

}

private int insertcode(int value, Node t, , int counter)

{

while (root.getVlue()> value)

don't know what to do next

please help

thanx for replying, i am trying to write amethod to insert in BST

THE method will insert a new item into the data set with the given value.

THEN The method will return the number of items that it had to examine to find the location at which the new item should be inserted.

Pre-codition: no duplicate values will ever be inserted into the data set.

CODE:

public int insert (int val)

{

if (root==null)

{

root = new Node(value);

return 0;

}

return insertcode (val), root,0);

}

private int insertcode(int value, Node t, , int counter)

{

while (root.getVlue()> value)

don't know what to do next

please help

necati sekkeli

Greenhorn

Posts: 26

posted 13 years ago

if efficiency in a sorted list is important for you. You can use trees. In insert method you must find the place first and then place it. (it is done by creating a node and putting it to a leaf and rotating it up to its right place by comparing the values). Deletion will be the inverse of this.

Find is easier. You can traverse the tree basicly.

Find is easier. You can traverse the tree basicly.