balanced binary tree

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

balanced binary tree

Willem Broekema
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



Reply | Threaded
Open this post in threaded view
|

balanced binary tree

Peter H|gfeldt

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
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>
%% 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.