balanced binary tree
Peter H|gfeldt
peter@REDACTED
Sun Sep 23 20:05:54 CEST 2001
There are several problems with that code. In particular, the trees that
it produce, are not balanced!
I once (oh my -- it was almost ten years ago) rewrote the module, then
named avl (I attach avl.erl). Note that the code is (very) slow compared
to e.g.ets.
/Peter
-------------------------------------------------------------------------
Peter Högfeldt e-mail : peter@REDACTED
Open Telecom Platform
"Computers are machines that do exactly what you tell them,
but often surprise you in the result."
Richard Dawkins in The Blind Watchmaker
On Sun, 23 Sep 2001, Willem Broekema wrote:
> Is there a known error in the code for balanced binary trees in
> 'Concurrent programming in Erlang', pp. 62-66?
>
> I have carefully copied the code to balbintree.erl, but there's an error
> in it. Maybe someone else has copied code and can check if these
> statements work for him?
>
> 41> B = balbintree:empty_tree().
> {nil,nil,0,nil,nil}
> 42> B2 = balbintree:insert(key1,val1,B).
> {key1,val1,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}}
> 43> B3 = balbintree:insert(key2,val2,B2).
> {key1,val1,
> 2,
> {nil,nil,0,nil,nil},
> {key2,val2,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}}}
> 44> B4 = balbintree:delete(key2,B3).
>
> =ERROR REPORT==== 23-Sep-2001::17:01:06 ===
> Error in process <0.86.0> with exit value:
> {function_clause,[{balbintree,combine
> ,[nil,nil,nil,nil,key1,val1,{nil,nil,0,nil,nil}]},{erl_eval,expr,3},{...
> ** exited: {function_clause,[{balbintree,
> combine,
> [nil,
> nil,
> nil,
> nil,
> key1,
> val1,
> {nil,nil,0,nil,nil}]},
> {erl_eval,expr,3},
> {erl_eval,exprs,4},
> {shell,eval_loop,2}]} **
>
> - Willem
>
-------------- next part --------------
%% Copyright (C) 1993, Ellemtel Telecommunications Systems Laboratories
%% File : avl.erl
%% Version : 1.0
%% Date : 06NOV1991
%% Author : Peter Hogfeldt <ebcplh@REDACTED>
%% Purpose : Operations on AVL trees (a tree is an AVL tree
%% if for each subtree, the heights of its left
%% and right branch differ by at most one).
%%
%% EXPORTS
%%
%% empty_tree() = void
%%
%% lookup(Key,Tree) = not_found, {found,Value}
%%
%% lookup_first(Tree) = not_found, {found,Value,Key}
%%
%% lookup_next(Key,Tree) = not_found, {found,Value,not_found},
%% {found,Value,NextKey}. Value is the
%% value that corresponds to Key.
%%
%% insert(Key,Value,Tree) = NewTree
%%
%% delete(Key,Tree) = NewTree
-module(avl).
-revision('$Revision: 2.1 $').
-created('$CreationDate$').
-created_by('$Creator$').
-modified('$Date: 1995/09/12 16:41:06 $').
-modified_by('$Author: peter $').
-export([empty_tree/0,lookup/2,lookup_first/1,lookup_next/2,
insert/3,delete/2]).
empty_tree() -> void.
lookup(_,void) ->
not_found;
lookup(K,{_,{K,V},_,_}) ->
{found,V};
lookup(K,{L,{Km,_},_,_}) when K<Km ->
lookup(K,L);
lookup(K,{_,{Km,_},_,R}) when K>Km ->
lookup(K,R).
lookup_first(void) ->
not_found;
lookup_first({void,{K,V},_,_}) ->
{found,V,K};
lookup_first({L,_,_,_}) ->
lookup_first(L).
lookup_next(K,void) ->
not_found;
lookup_next(K,{_,{K,V},_,R}) ->
case lookup_first(R) of
{found,_,Ky} -> {found,V,Ky};
Other -> {found,V,Other}
end;
lookup_next(K,{L,{Km,_},_,_}) when K<Km ->
case lookup_next(K,L) of
{F,Vm,not_found} -> {F,Vm,Km};
Other -> Other
end;
lookup_next(K,{_,{Km,_},_,R}) when K>Km ->
lookup_next(K,R).
insert(K,V,void) ->
{void,{K,V},1,void};
insert(K,V,{L,{K,_},H,R}) ->
{L,{K,V},H,R};
insert(K,V,{L,{Km,Vm},_,R}) when K<Km ->
join(insert(K,V,L),{Km,Vm},R);
insert(K,V,{L,{Km,Vm},_,R}) when K>Km ->
join(L,{Km,Vm},insert(K,V,R)).
delete(K,T) ->
case catch del(K,T) of
not_found ->
T;
Other ->
Other
end.
%% LOCALS
%%
%% A tree is a tuple {LeftTree,Item,Height,RightTree} or void. Item
%% is of the form {Key,Value} for lookup, insert, delete and del.
%%
%% del(Key,Tree) = NewTree, not_found
%%
%% join(LeftTree,Item,RightTree} = Tree
%%
%% merge(LeftTree,RightTree) = Tree
%%
%% detach_right(Tree) = {Item,NewTree}
%% - detaches the rightmost item from Tree, which must not be void.
%%
%% detach_left(Tree) = {Item,NewTree}
%% - detaches the leftmost item from Tree, which must not be void.
%%
%% max(x,y) = max(x,y)
%%
del(_,void) ->
throw(not_found);
del(K,{L,{K,_},_,R}) ->
merge(L,R);
del(K,{L,{Km,Vm},_,R}) when K<Km ->
join(del(K,L),{Km,Vm},R);
del(K,{L,{Km,Vm},_,R}) when K>Km ->
join(L,{Km,Vm},del(K,R)).
join(void,I,void) -> {void,I,1,void};
join(void,I,{void,Iy,_,void}) -> {void,I,2,{void,Iy,1,void}};
join(void,I,{Ly,Iy,Hy,Ry}) when Hy>1 ->
{Im,Tm}=detach_left({Ly,Iy,Iy,Ry}),
join({void,I,1,void},Im,Tm);
join({void,Ix,_,void},I,void) -> {{void,Ix,1,void},I,2,void};
join({Lx,Ix,Hx,Rx},I,void) when Hx>1 ->
{Im,Tm}=detach_right({Lx,Ix,Hx,Rx}),
join(Tm,Im,{void,I,1,void});
join({Lx,Ix,Hx,Rx},I,{Ly,Iy,Hy,Ry}) when Hx=<Hy+1, Hy=<Hx+1 ->
{{Lx,Ix,Hx,Rx},I,max(Hx,Hy)+1,{Ly,Iy,Hy,Ry}};
join({Lx,Ix,Hx,Rx},I,{Ly,Iy,Hy,Ry}) when Hx>Hy+1 ->
{Im,Tm}=detach_right({Lx,Ix,Hx,Rx}),
join(Tm,Im,join(void,I,{Ly,Iy,Hy,Ry}));
join({Lx,Ix,Hx,Rx},I,{Ly,Iy,Hy,Ry}) when Hy>Hx+1 ->
{Im,Tm}=detach_left({Ly,Iy,Hy,Ry}),
join(join({Lx,Ix,Hx,Rx},I,void),Im,Tm).
merge(void,void) -> void;
merge(void,R) -> R;
merge(L,void) -> L;
merge({Lx,Ix,Hx,Rx},{Ly,Iy,Hy,Ry}) when Hx>Hy ->
{Im,Tm}=detach_right({Lx,Ix,Hx,Rx}),
join(Tm,Im,{Ly,Iy,Hy,Ry});
merge({Lx,Ix,Hx,Rx},{Ly,Iy,Hy,Ry}) when Hx=<Hy ->
{Im,Tm}=detach_left({Ly,Iy,Hy,Ry}),
join({Lx,Ix,Hx,Rx},Im,Tm).
detach_right({L,I,_,void}) ->
{I,L};
detach_right({L,I,_,R}) ->
{Im,Rm} = detach_right(R),
{Im,join(L,I,Rm)}.
detach_left({void,I,_,R}) ->
{I,R};
detach_left({L,I,_,R}) ->
{Im,Lm} = detach_left(L),
{Im,join(Lm,I,R)}.
max(X,Y) when X =< Y -> Y;
max(X,Y) -> X.
More information about the erlang-questions
mailing list