How to store in memory a tree like structure?
2 posts in topic
Flat View  Flat View
TOPIC ACTIONS:
 

Posted By:   francis_robitaille
Posted On:   Monday, July 7, 2003 12:01 PM

Hi, We're having some problems accomplishing the following: Objective: vertically read a tree like data structure and maintain the tree structure in memory. Example: let's say we have the following data stored in a RDBMS - table countries: field country, rows=USA - table states: field state, rows=NY,CA - table cities: field city, rows=Rochester,NYC,LA Naturally the DB structure allows us to link cities to states and states to countries. Now the goal is to read all the data from the DB from the "root" level i/e countries all the way down to the "child most" objects in order to vertically build a tree like   More>>

Hi,


We're having some problems accomplishing the following:



Objective: vertically read a tree like data structure and maintain the tree structure in memory.



Example: let's say we have the following data stored in a RDBMS

- table countries: field country, rows=USA

- table states: field state, rows=NY,CA

- table cities: field city, rows=Rochester,NYC,LA


Naturally the DB structure allows us to link cities to states and states to countries.



Now the goal is to read all the data from the DB from the "root" level i/e countries all the way down to the "child most" objects in order to vertically build a tree like structure as follow:

- level 0: country=USA, parent=null

- level 1: state=NY, parent=USA

- level 2: city=Rochester, parent=NY

- level 2: city=NYC, parent=NY

- level 1: state=CA, parent=USA

- level 2: city=LA, parent=CA



We will have to use a recursive pattern to read the data since in reality the number of level in the structure is unknown.



The problem is to decide on a structure to store the object relations in memory. We looked at TreeMap but from what I understand this collection implements a black/red tree which we can not apply to our data model.


Any hints will be greatly appreciated!

Many thanks!

   <<Less

Re: How to store in memory a tree like structure?

Posted By:   Nilanjan_Sengupta  
Posted On:   Monday, July 7, 2003 01:05 PM

You can use hashtables for your situation.

Define the following hashtables -- countryHash and stateHash. countryHash has the key set as "USA" or "CANADA" or "UK". The value is stateHash. stateHash has the key set as "CA" or "VA" or "DC". The value is city. You can define a Static List object to populate the hashtables from the database. You can store these hashtables in the session.

Hope this helps.

thanks
Nilanjan

Re: How to store in memory a tree like structure?

Posted By:   Stephen_McConnell  
Posted On:   Monday, July 7, 2003 12:47 PM

It appears you don't have the "academic" binary or red-black or multiway tree, but an actual TREE! AH HA!


The Java Collections aren't great at handling this kind of structure, BUT all is not lost. I have used the swing class java.swing.tree.DefaultTreeModel many times to represent this kind of tree structure.


It has a setRoot() method. Methods for insertNodeInto(...), removeNodeFromParent(...) etc...etc. You can also add listeners and methods for notification if child tree structures have changed.... It's an absolutely fabulous little class.


Look at all the java.swing.tree classes. And if you get a chance, look at the source code for them. They are very interesting and I learned a lot about Java and actions when I did.


Stephen McConnell

About | Sitemap | Contact