hit counter

Timeline

My development logbook

Ex 2.2

Exercise 2.2 (Andersson [And91D]) In the worst case, member performs approximately 2d comparisons, where d is the depth of the tree. Rewrite member to take no more than d + 1 comparisons by keeping track of a candidate element that might be equal to the query element (say, the last element for which < returned false or < returned true) and checking for equality only when you hit the bottom of the tree.)

Answer

To test the example code, run these commands:

erl -noshell -noinit -run ex2_2 test_insert -run init stop
erl -noshell -noinit -run ex2_2 test_member -run init stop

My erlang implementation actually does not have the same performance characteristic as stated in the question. The code in question is this:

1
2
3
4
5

fun member (x, E) = false
  | member (x, T (a, y, b)) =
        If Element.lt (x, y) then member (x, a)
        else if Element.lt (y, x) then member (x, b)
        else true

The if clause in the above function will cause the Element.lt to be executed twice per node visit in the worst case scenarios. Hence the 2 * d comparisons.

It does not really apply to my erlang version of code because pattern matching has shortcircuted the comparsion when there is a match. The comparsion is done by the guard. In a sense I cheated: I did not use a functor to compare the values. This enables me to use the pattern matching.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

-module(ex2_2).
-export([make_sample_tree/0, test_insert/0, test_traverse/0, test_member/0]).

-record(treenode, {key, value}).
-record(tree, {left, treenode=#treenode{}, right}).

make_node(K, V) ->
    TN = #treenode{key=K, value=V},
    T = #tree{treenode=TN},
    T.

make_node(K, V, LeftTree, RightTree) ->
    TN = #treenode{key=K, value=V},
    T = #tree{treenode=TN, left=LeftTree, right=RightTree},
    T.

insert_tree_node(undefined, K, V) ->
    make_node(K, V);
insert_tree_node(#tree{left=LT, treenode=#treenode{key=CurK, value=_CurV}, right=_RT}=T, K, V) when K < CurK  ->
    LT1=insert_tree_node(LT, K, V),
    T1=T#tree{left=LT1},
    T1;
insert_tree_node(#tree{left=_LT, treenode=#treenode{key=CurK, value=_CurV}, right=RT}=T, K, V) when K > CurK  ->
    RT1=insert_tree_node(RT, K, V),
    T1=T#tree{right=RT1},
    T1;
% when K == CurK
insert_tree_node(T, _K, V)  when is_record(T, tree) ->
    T#tree{treenode=#treenode{value=V}}.


traverse(F, Tree) when is_record(Tree, tree) and is_function(F) ->
    traverse(F, Tree, 0).
traverse(_F, undefined, _D) -> ok;
traverse(F, Tree, D) when is_record(Tree, tree) and is_function(F) -> % F is a function that work on K and V
    traverse(F, Tree#tree.left, D+1),
    F(Tree#tree.treenode#treenode.key, Tree#tree.treenode#treenode.value, D),
    traverse(F, Tree#tree.right, D+1).

member(K, #tree{treenode=#treenode{key=K}}=Tree) ->
    found;
member(K, #tree{treenode=#treenode{key=CurK}}=Tree) when K < CurK ->
    % io:format("Compared for ~p~n", [K]),
    member(K, Tree#tree.left);
member(K, #tree{treenode=#treenode{key=CurK}}=Tree) when K > CurK ->
    % io:format("Compared for ~p~n", [K]),
    member(K, Tree#tree.right);
member(K, undefined) ->
    not_found.


%% routines for testings
%% 
make_sample_tree() ->
    Left = make_node(1, 1),
    Right = make_node(5, 5),
    T = make_node(3, 3, Left, Right),
    T.

make_sample_tree2() ->
    T = make_node(5, 5),
    T1 = insert_tree_node(T, 1, 1),
    T2 = insert_tree_node(T1, 2, 2),
    T3 = insert_tree_node(T2, 7, 7),
    T4 = insert_tree_node(T3, 6, 6),
    T5 = insert_tree_node(T4, 10, 10),
    T6 = insert_tree_node(T5, 12, 12),
    T6.

test_insert() ->
    T = make_sample_tree(),
    T1 = insert_tree_node(T, 7, 7),
    io:format("old ~p~n", [T]),
    io:format("new ~p~n", [T1]).

test_traverse() ->
    F = fun (K, V, _D) -> io:format("key:~p val:~p~n", [K, V]) end,
    T = make_sample_tree(),
    traverse(F, T).

test_member() ->
    T = make_sample_tree2(),
    F = fun (K, V, Depth) ->
            Indent = string:chars($\s, Depth*4),
            io:format("~skey:~p val:~p~n", [Indent, K, V])
        end,
    traverse(F, T),
    R1 = member(12, T),
    R2 = member(-1, T),
    io:format("R1:~p R2:~p~n", [R1, R2]).