?
Solved

AVL Data structure?

Posted on 2000-02-09
19
Medium Priority
?
369 Views
Last Modified: 2010-04-02
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
0
Comment
Question by:ShoGun
  • 10
  • 9
19 Comments
 
LVL 7

Accepted Solution

by:
KangaRoo earned 400 total points
ID: 2503594
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
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2503600
Forgot, ternary serach trees can be used very well for pattern matching and 'near neigboor' searches.
0
 

Author Comment

by:ShoGun
ID: 2521651
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
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 

Author Comment

by:ShoGun
ID: 2521671
If u can help me please tell.
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2521749
With the skiplist you mean?
0
 

Author Comment

by:ShoGun
ID: 2521811
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
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2521838
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
 

Author Comment

by:ShoGun
ID: 2521944
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
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2522077
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
 

Author Comment

by:ShoGun
ID: 2522408
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
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2522656
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
 

Author Comment

by:ShoGun
ID: 2526705
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
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2526738
>> 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
 

Author Comment

by:ShoGun
ID: 2526811
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
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2527116
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
 

Author Comment

by:ShoGun
ID: 2530102
>>>>>>>>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
 

Author Comment

by:ShoGun
ID: 2530107
>>>>>>>>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
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2530210
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
 

Author Comment

by:ShoGun
ID: 2530270
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

Featured Post

Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

599 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question