Home > Archive > Prolog > December 2004 > Balanced Binary Tree
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
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
| |
| Markus Triska 2004-11-29, 8:57 pm |
| 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.
| |
| Alan Baljeu 2004-11-30, 4:01 pm |
|
"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.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?
>
> 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).
| |
| Markus Triska 2004-12-01, 8:57 pm |
|
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.
|
|
|
|
|