Balanced Binary Tree

Hi,

i have to write a program that use a cache to memorize integer numbers.
I want this cache to run fast, so i've used, in my C program, a bb-tree.
Now i must translate this program in prolog language, and i don't know
how to code a bb-tree predicate.
The C code is simple enough, but without pointers, i don't know how to do...
The length of the cache can be around 1.000.000 elements.
Some ideas, code, reference?

Thanks,
Lucas

lucas wrote:

> i have to write a program that use a cache to memorize integer numbers.
> I want this cache to run fast, so i've used, in my C program, a bb-tree.
> Now i must translate this program in prolog language, and i don't know
> how to code a bb-tree predicate.

How about using this structure:

is_bbtree([]).
is_bbtree(tr(Val,Left,Right)) :-
number(Val),
is_bbtree(Left),
is_bbtree(Right)


Best regards,
Markus.

"lucas" <kingpin@freemail.it> wrote in message
news:25977234.0411261138.2ce2404f@posting.google.com...
> Hi,
>
> i have to write a program that use a cache to memorize integer numbers.
> I want this cache to run fast, so i've used, in my C program, a bb-tree.
> Now i must translate this program in prolog language, and i don't know
> how to code a bb-tree predicate.
> The C code is simple enough, but without pointers, i don't know how to do.
.
> The length of the cache can be around 1.000.000 elements.
> Some ideas, code, reference?

Maybe look for a good implementation of association lists.  For example, SWI
-prolog
includes one that's implemented as a 2-3 tree, in assoc.pl.

kingpin@freemail.it (lucas) wrote in message news:<25977234.0411261138.2ce2404f@posting.goo
gle.com>...
> Hi,
>
> i have to write a program that use a cache to memorize integer numbers.
> I want this cache to run fast, so i've used, in my C program, a bb-tree.
> Now i must translate this program in prolog language, and i don't know
> how to code a bb-tree predicate.
> The C code is simple enough, but without pointers, i don't know how to do.
.
> The length of the cache can be around 1.000.000 elements.
> Some ideas, code, reference?
>
> Thanks,
> Lucas



I've translated a c source code that implemented simple bb-tress.
Here is the code...i have to write only the remove function (but i
don't need
it..).
Some comments (really slow, slow, normal, good...)?


% Right rotate
bbtree_rightrot(bbtree(K, bbtree(K1, Left1, Right1, Level1), Right,
Level), New) :- Level1 =:= Level,
New = bbtree(K1, Left1, bbtree(K, Right1,
Right, Level), Level1), !.
bbtree_rightrot(Tree, Tree):-!.

% Left rotate
bbtree_leftrot(bbtree(K, Left, bbtree(K1, Left1, bbtree(K2, Left2,
Right2, Level2), Level1), Level), New) :- Level2 =:= Level,
Level3 is Level1 + 1,
New = bbtree(K1, bbtree(K,Left, Left1,
Level1), bbtree(K2,Left2,Right2, Level2), Level3), !.
bbtree_leftrot(Tree,Tree):-!.





% Insert
bbtreeinsert(Key, bbtree(void), bbtree(Key, bbtree(void),
bbtree(void), 0)):-!.
bbtreeinsert(Key, bbtree(K, Left, Right, Level), New) :- Key < K,
bbtreeinsert(Key, Left, New1),!,
bbtree_rightrot(bbtree(K, New1, Right, Level), New2),
bbtree_leftrot(New2, New).
bbtreeinsert(Key, bbtree(K, Left, Right, Level), New) :- Key > K,
bbtreeinsert(Key, Right, New1),!,
bbtree_rightrot(bbtree(K, Left, New1, Level), New2),
bbtree_leftrot(New2, New).

% Find
bbtreefind(Key, bbtree(void), 0).
bbtreefind(Key, bbtree(Key, Left, Right), 1).
bbtreefind(Key, bbtree(K, Left, Right), Flag) :- Key < K, !,
bbtreefind(Key, Left, Flag).
bbtreefind(Key, bbtree(K, Left, Right), Flag) :- Key > K, !,
bbtreefind(Key, Right, Flag).

The indentation seems to be messed up. In bbtreefind/3, you could do
without the "Flag" argument:

bbtree_keythere(Key, bbtree(Key, _, _)).
bbtree_keythere(Key, bbtree(K, Left, _)) :-
Key < K,
!,
bbtree_keythere(Key, Left).
bbtree_keythere(Key, bbtree(K, _, Right)) :-
Key > K,
bbtree_keythere(Key, Right).

If the key is *not* there, the predicate will then fail - catch this
case with

...
\+ bbtree_keythere(Key,Tree)
....

if you need it.

Best regards,
Markus.