Important alert: (current site time 12/21/2014 12:04:24 AM EDT)
 

winzip icon

Balanced Binary AVL Trees Using Dynamic RAM Allocation

Email
Submitted on: 4/11/2005 11:00:28 AM
By: Herbert Glarner 
Level: Advanced
User Rating: By 8 Users
Compatibility: VB 6.0
Views: 7376
(About the author)
 
     ABSTRACT Provides any amount of requested memory (as long as there is available RAM) and associates that memory with a user-defined alphanumeric key. Features very fast retrieval in sorted order, even faster sequential access (in the chronological order the requests were made). DESCRIPTION The alphanumeric keys are associated with a certain quantity of bytes located at a designated position in RAM. That RAM is and remains exclusively reserved for that Key. Via the key the address can be returned, and also the reserved bytes at that address. Keys are internally managed with a balanced binary AVL tree. It is possible to iterate through the whole collection of keys in the order in which these keys were created (and the memory allocated), returning the Key, the Memory Address and the Size. It is also possible to access all the Keys in sorted order (ascending as well as descending). All operations are considerabily faster than VB's Collection object (as far as such functions are provided by the Collection).

 
winzip iconDownload code

Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. Afterdownloading it, you will need a program like Winzip to decompress it.Virus note:All files are scanned once-a-day by Planet Source Code for viruses, but new viruses come out every day, so no prevention program can catch 100% of them. For your own safety, please:
  1. Re-scan downloaded files using your personal virus checker before using it.
  2. NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.
  3. Scan the source code with Minnow's Project Scanner

If you don't have a virus scanner, you can get one at many places on the net including:McAfee.com

 
Terms of Agreement:   
By using this code, you agree to the following terms...   
  1. You may use this code in your own programs (and may compile it into a program and distribute it in compiled format for languages that allow it) freely and with no charge.
  2. You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.   
  3. You may link to this code from another website, but ONLY if it is not wrapped in a frame. 
  4. You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.


Other 3 submission(s) by this author

 


Report Bad Submission
Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

Your Vote

What do you think of this code (in the Advanced category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)
 

Other User Comments

4/11/2005 12:01:59 PMStavros Sirigos

Very usefull, nicely coded and commented! Pretty efficient also. 5 from me!

Btw, where did you get that "5 million elements= max. array size under VB" thing? :) Anyway, good work!
(If this comment was disrespectful, please report it.)

 
4/11/2005 1:06:46 PMHerbert Glarner

Thank you, Stavros :)

With 2 million elements, my VB 6 SP 5 under Win 2000 Pro says "Out of memory" (having 1.3 GB :p) - well, the DLL can handle 5 million entries easily (that's as far as I went when testing, although the key generation process becomes a nuysance then, due to repetitions in the Rnd() sequences: use a prime number as key length if you're going to try the same). However, it's just so that VB won't let me create a larger string array to store the generated keys in the test form's array.

(If this comment was disrespectful, please report it.)

 
4/11/2005 9:15:47 PMenmity

you have to tell us it IS much faster in compiled mode :)

btw, where is SatBNF.cls?

(If this comment was disrespectful, please report it.)

 
4/11/2005 9:17:27 PMenmity

one more thing, can it be used to store strings or even objects?
(If this comment was disrespectful, please report it.)

 
4/11/2005 11:22:57 PMHerbert Glarner

True, enmity: As is the case with all VB projects, it is much faster when compiled. When running the project in the IDE, the built-in (already "compiled") Collection object wins by lengths.

The reference to SatBNF refers to another DLL (Backus Naur Form lexer and parser, which I might upload as well in a few days after some more testing, possibly also within a tutorial describing parser building in VB). It merely escaped my attention to remove that reference from the file "SatStructures.vbp". For now, you can safely delete the line "Class=SatBNF;" in there.
(If this comment was disrespectful, please report it.)

 
4/11/2005 11:37:56 PMHerbert Glarner

What you do with the allocated address is completely up to you, although it is ideal for a usage with CopyMemory ("RtlMoveMemory").

However, keep in mind that this is advanced stuff: You really should know what you do with allocated RAM, especially when it comes to stealing object references circumventing the COM ;)

In short, to copy a string:

lSize = LenB(Text)
lBytes = lSize + 4&
lNodeAddr = YourObject.Add(YourKey, lBytes)
CopyMemory ByVal lNodeAddr, lSize, 4&
CopyMemory ByVal lNodeAddr + 4&, ByVal StrPtr(YourString), lSize

To retrieve a stored string:

lIndex = YourAVLObject.Item(YourKey)
lAddr = YourAVLObject.Address(lIndex)
CopyMemory lBytes, ByVal lAddr, 4&
YourString = Space$(lBytes \ 2)
CopyMemory ByVal StrPtr(YourString), ByVal lAddr + 4, lBytes

(If this comment was disrespectful, please report it.)

 
4/12/2005 7:01:54 AMJamsey Stevenson

This is what psc is all about. Nice one.
(If this comment was disrespectful, please report it.)

 
3/21/2012 3:36:06 AMRde


Hi Herbert

First I would like to thank you for your superb AVL class. It is very much appreciated.

VB's Collection object has a reputation for being surprisingly fast for insertion and key lookups so blowing it away with this AVL tree is impresssive.

I'm lead to believe the VB Collection object uses a hash table or a binary tree internally for its fast performance.

I selected your AVL class as my basis for a fast VB Collection substitute.

However, after creating a node removal algo I needed to test it. I set up to test the trees validity before and after a node delete operation - and it failed before!

A couple of slight changes to your double rotation routines fixed the subtle bugs that maintained a valid binary search tree but not a valid AVL balance on certain situations. The second (or third) last line in each routine was the culprit if I remember correctly. ... cont'd next comment ...
(If this comment was disrespectful, please report it.)

 
3/21/2012 3:37:08 AMRde

Private Sub BalanceLR(lC As Long)
...
'New weights
vBinTree(lA).RightHeight = vBinTree(lB).LeftHeight
vBinTree(lB).LeftHeight = vBinTree(lA).LeftHeight + 1
vBinTree(lC).LeftHeight = vBinTree(lB).RightHeight
vBinTree(lB).RightHeight = vBinTree(lC).RightHeight + 1
End Sub

Private Sub BalanceRL(lA As Long)
...
'New weights
vBinTree(lA).RightHeight = vBinTree(lB).LeftHeight
vBinTree(lB).LeftHeight = vBinTree(lA).LeftHeight + 1
vBinTree(lC).LeftHeight = vBinTree(lB).RightHeight
vBinTree(lB).RightHeight = vBinTree(lC).RightHeight + 1
End Sub

Thanks again Herbert

For more info, perhaps the validity test routine, or the node removal algo feel free to contact me.

Happy coding,
Rd :)

(If this comment was disrespectful, please report it.)

 
1/21/2014 2:36:17 PMCap. Picard

super, :)
(If this comment was disrespectful, please report it.)

 

Add Your Feedback
Your feedback will be posted below and an email sent to the author. Please remember that the author was kind enough to share this with you, so any criticisms must be stated politely, or they will be deleted. (For feedback not related to this particular code, please click here instead.)
 

To post feedback, first please login.