Array based AVL Tree

[karthikbalaguru]

Hi,

Can anyone let me know an opensource
implemenation of 'Array Based AVL Tree' ?

Thx in advans,
Karthik Balaguru

 

[user923005]

Hi,

Can anyone let me know an opensource
implemenation of  'Array Based AVL Tree' ?

One showed up as the second link of my google search.
What showed up on yours?

 

[karthikbalaguru]

One showed up as the second link of my google search.
What showed up on yours?

I did not find it on the first page. But after
digging through the pages listed down by google,
and also based on my earlier discussions related
to malloc free AVL tree , i do find the below links -

1. http://src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/common/avl/avl.c
2. http://darrencubitt.googlepages.com/avltreelink.zip
3. http://pastebin.com/f71ae5385 -> A region allocator that is
Independent of malloc calls.
4. http://users.cis.fiu.edu/~weiss/dsaa_c2e/files.html - Has a list of
algos . Few are
based on both static and dynamic allocation.

Thx,
Karthik Balaguru

 

[Chris M. Thomasson]

I did not find it on the first page. But after
digging through the pages listed down by google,
and also based on my earlier discussions related
to malloc free AVL tree , i do find the below links -

1.
http://src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/common/avl/avl.c
2. http://darrencubitt.googlepages.com/avltreelink.zip
3. http://pastebin.com/f71ae5385 -> A region allocator that is
Independent of malloc calls.

FWIW, here is a "better" version of the static region allocator:

http://pastebin.com/f207f6232

I say better because it allows one to allocate arrays of objects, and it has
a "condensed" API. BTW, here is the original discussion in this group:

http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978a0f20195


Enjoy! ;^)

 

[Franken Sense]

In Dread Ink, the Grave Hand of user923005 Did Inscribe:

One showed up as the second link of my google search.
What showed up on yours?

Google searches are good for people who already know the answer.

Would Ben's avl tree on the disc of Unleashed qualify?
--
Frank

In many ways I'm still a Hubert Humphrey Democrat -- someone who believes
in afflicting the comfortable and comforting the afflicted. A society is
judged by how it treats the elderly, the sick, the impoverished. To me it's
a matter of ethics and compassion.
~~ Al Franken, Playboy interview

 

[Keith Thompson]

In Dread Ink, the Grave Hand of user923005 Did Inscribe:


Google searches are good for people who already know the answer.

All that's needed in this case is the phrase "Array based AVL Tree",
which the OP already knew well enough to put it in the subject header.
(A number of the top hits are now links to this thread.)

 

[Franken Sense]

In Dread Ink, the Grave Hand of Keith Thompson Did Inscribe:

All that's needed in this case is the phrase "Array based AVL Tree",
which the OP already knew well enough to put it in the subject header.
(A number of the top hits are now links to this thread.)

I've done a lot of googling for tree-related stuff in C, lately, and found
a lot of parts I needed, but never a closed-form source listing that was
going to survive being fed to a compiler.

The several links posted for this were an entirely different matter,
including a place where you can do a one-click download, which is nive for
the 400 lines that these programs get to be.

What makes these "array-based" avl trees? The "a" in avl is for Adelson.

Are there clues in these comments here:

0 * Small arrays to translate between balance (or diff) values and child
indeces.
101 *
102 * Code that deals with binary tree data structures will randomly
use
103 * left and right children when examining a tree. C "if()"
statements
104 * which evaluate randomly suffer from very poor hardware branch
prediction.
105 * In this code we avoid some of the branch mispredictions by using
the
106 * following translation arrays. They replace random branches with
an
107 * additional memory reference. Since the translation arrays are
both very
108 * small the data should remain efficiently in cache.
--
Frank

There's no liberal echo chamber in this country. There's a right-wing echo
chamber. I want to create a countervailing echo chamber.
~~ Al Franken, Chicago Tribune interview, on

 

[karthikbalaguru]

FWIW, here is a "better" version of the static region allocator:

http://pastebin.com/f207f6232

I say better because it allows one to allocate arrays of objects, and it has
a "condensed" API. BTW, here is the original discussion in this group:

http://groups.google.com/group/comp.lang.c/browse_frm/thread/97a1c978...

Enjoy! ;^)

Gr8 ! Nice one.
Thx for that.

Karthik Balaguru