AVL Data structure?

hello,
we using java but it's data structures hashtabel & vector(a growable array) are clumsy and memory hog after just 2000 insertions ,i said of using AVL trees for really fast searches to team,can we implemnt as replacement for vector? requirement of storing upot 500,000 recrods smoothly and only 1 tiem inserts mostly searches always as we think of storing values in it.

excellemt site for AVL
http://www.enteract.com/~bradapp/ftp/src/libs/C++/AvlTrees.html

we later remove recrusion as slows down,
and also what is a good replacement for hashtable ? itis useful for storing name-value pairs,so what good replacement for it?

please advice ,many people give many points.

Thanks you
ShoGun
ShoGunAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

KangaRooCommented:
Search trees are efficient when there are many searches and few mutations. They are totally unsuited for random (indexed) access and a bit inefficient for sequential access.
Binary search trees generally use more memory then hashtables and vectors.

An interesting alternative to (partially) balanced trees are skiplists:
http://www.csihq.com/CSI/pubs/skiplist.html
ftp://ftp.cs.umd.edu/pub/skipLists/
Main advantage over trees is their respect for memory (average overhead per node 1~2 pointers as opposed to 2 pointers + flags for serach trees) and the ease of coding (simpler coding, less buggs, easier to optimize).

Hashtables may be replaced with ternary search trees, which are just approx as fast in normal cases and slightly better when the search fails. They are memory hungry.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
KangaRooCommented:
Forgot, ternary serach trees can be used very well for pattern matching and 'near neigboor' searches.
0
ShoGunAuthor Commented:
sorry but i try to read and cant understand that much how to convert them to Java? I dont think that anybody can help me but will have to ask some colleagues for heping me out.

can you tell me ?
Thanks you
0
Introducing Cloud Class® training courses

Tech changes fast. You can learn faster. That’s why we’re bringing professional training courses to Experts Exchange. With a subscription, you can access all the Cloud Class® courses to expand your education, prep for certifications, and get top-notch instructions.

ShoGunAuthor Commented:
If u can help me please tell.
0
KangaRooCommented:
With the skiplist you mean?
0
ShoGunAuthor Commented:
Yes the statement
>>>>>>>implement a dictionary using
skip lists

is what interestd me ,dictionary is superclass of hashtable in java.
I am right now doing taht ,will post some code sometime this week.

basically i am modifying code
0
KangaRooCommented:
I could help you with the skiplist algorithms as such, but I'm not a Java programmer.
Anything concrete you are stuck with

Is in Java a Dictionary a Super class of Hashtable? That is very odd design. I suppose you could implement a concrete dictionary by using a hashtable, but that doesn't make a hashtable a dictionary?
0
ShoGunAuthor Commented:
I dont know why its odd but hashtable is concrete implementation of Dictionary which is abstract.

data structures in Java are lot difficult than C/C++
0
KangaRooCommented:
Mh, well, guess I should not pass judgement too lightly here.
You ask for help but it is not clear to me on what, the skiplist, its implementattion? the ternary search tree (hash table replacement). Do you need help in understanding how they work or in the implementation?
0
ShoGunAuthor Commented:
http://www.csihq.com/CSI/pubs/skiplist.html
The page cannot be found ?

but i got this
http://www.ddj.com/articles/1998/9804/9804a/9804a.htm

Ok I want your help on a fast Data Structure for name-value pairs whaterevr that maybe.
Thanks you
0
KangaRooCommented:
Indeed, it is off line. I'm sure I've tried it just before posting though!

It has been moved:
http://www.csihq.com/CSI/pub_Skip.html

Did you get access to the ftp link?

>> http://www.ddj.com/articles/1998/9804/9804a/9804a.htm
Yes those are the ternary serach trees.

AFAIK, name-value pair search structures are dictionaries ;)
Any way, you said you were using hashtables but you found they used to much memory. Ternary search trees are a possible replacement, were it not that they use even more memory.
I mentioned SkipLists becaue they use far less memory (1~2 links per node) then AVL binary trees (2 links + info per node). They are slightly less efficient then balanced (AVL) binary trees.

If you got to the ftp link working you should really take a look at the articles. If you have any questions, or can't find the articles let me know (I'll have to refresh my memory though)
0
ShoGunAuthor Commented:
Yes i got access to ftp link,Ok can i transform Skiplists as a hashtable whcih is a name value pairs struture?

can yu transform it to C++ as then I can ask one of my friedns to help me out then.

I have 170 points now,cod eis 200 lines. pplease tell yes/no

Thanks you
0
KangaRooCommented:
>> code is 200 lines
You already have code.
Well, i'm not so sure it is done in 200 lines, at least not how I would implement it: STL compatible.
A full implemetation would take a considerable amount of time, not before the weekend.
I suppose I could translate the basic algortihms in a few hours, so I'll look at it tonight, ok?
0
ShoGunAuthor Commented:
thanks my friend,

my friend will then do the STL convesion to java as it is good and then i understand.

but the key and value is int in code?? We should Object in java or any other object,what use if not Object? I tink some expert like you can only implent it,we wnat any object mostly String to store as key and vector/hastable/ANY object as value.

Thanks you,I wait and i then mail you ,my 2 friedns will discuss me and we give u java code too.

friend,why dont you learn java its the future ,going to overtake c++ ,much as i dont like.
0
KangaRooCommented:
I think it is just common practice in literature to use integers as key. In practice one can use any type whose objects can be 'ordered' in some way. A C++ implementation would typically be as a template. I suppose in Java all objects are from classes ultimately derived from Object? Then the skiplist would store Object's.

>> friend,why dont you learn java its the future ,going to
>> overtake c++ ,much as i dont like.
I doubt Java will overtake C++. It is a great language for Web applications, but has some disadvantages.
But whatever the future brings, Java seems so close to C++ in syntax and concepts that I am confident I can learn it without to much difficulty.
0
ShoGunAuthor Commented:
>>>>>>>>I suppose in Java all objects are from classes ultimately derived from Object?

yes object is parent of all object in java.

>>>>>>>>I doubt Java will overtake C++. It is a great language for Web applications, but has some disadvantages.

My friedns all leaving c++ and trying jump java,i started learning now but they tell taht javas progress much fast than c++ in last 4 year,i tink release in 1996 ? how time till advanced featuires come in c++ ?much time ,yes but java slow for real time ,but they come with real time java specificasion,search for ti ,sun going everywhere.

now get back to work ,sorry but i also dont like what is happend ,if you do STL ,can template be easiyl converted to java?If not pls can you do normal? BUt yes if exception presenr very good as java  is good in exceptin.

Thanks you
0
ShoGunAuthor Commented:
>>>>>>>>now get back to work ,sorry but i also dont like what is happend ,

sorry I mean to said that what happen is bad ,2 frineds are fired from job,very bad change this.
0
KangaRooCommented:
Sorry about that. I think the people who run the show often seem to follow every trend or hype in IT, without knowing anything at all.
I'll just write the algo's for search, insert and delete.
How does Java manage with 'pointers' and 'arrays'?
0
ShoGunAuthor Commented:
java has reference and arrays,

since no pinter i saw all source code,hashtable and vector have array implement.They resize array when grow occurs.where you working and how many years?what dis people tihink of not bother about experinced people?i fear that this come to me,sometime in past as my dad also fire two years ,no job stable in this and next come genratois.my friends they think of going US and earn money fast as can ,me too ,have got little knowledge but am a student,who will employ me ,none?i browse sometime ,now from part time work,so sorry for cry.i staring design pattern and EJb ,corba ,rmi ,learn what is happen in world,then when i pass out after 3 ,half years,do MS ? yes my english bad will imprpve fast ,but seen my source code?i think it's good ,my brother he login here at EE,he also knwos you ,he talked with and u helped himout too.he told me all people kind to beginner as all through stage once ,I even help my borther ,but what to do he got lead of 5 years over me.I take english lesson,but speech still hesitat ,u can send me mail at shogun@techie.com, i wish to remain anonmous and i liked book ShoGun by james clavell,yoshi toranaga is his name.

Yes you ask me anyhitng and i tell you what i know,dont hesitate.pastre text.

It's not how good you are
It's how bad you want it.

i want it bad.

Thanks you
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.