我们认为最简单的树组织形式是非平衡二叉树。树内部的结点用{Key,Vlue,Smaller,Bigger}来表示。Value是被存储在树的一些结点中对象的值，它的键为Key。Smaller是一棵子树，它的所有结点的键值都小于Key，Bigger也是一棵子树，它的所有结点的键值都大于或等于Key。树的叶子用原子式nil表示。

    我们从lookup(Key,Tree)函数开始，这个函数搜索Tree以确定树中是否有与Key相关的项。

    函数insert(Key,Value,OldTree)将数据Key-Value添加到树OldTree中，并返回一棵新树。

    1. insert(Key, Value, nil) ->
    2.     {Key,Value,nil,nil};
    3.  
    4. insert(Key, Value, {Key,_,Smaller,Bigger}) ->
    5.     {Key,Value,Smaller,Bigger};
    6.  
    7. insert(Key, Value, {Key1,V,Smaller,Bigger}) when Key < Key1 ->
    8.     {Key1,V,insert(Key, Value, Smaller),Bigger};
    9.  
    10. insert(Key, Value, {Key1,V,Smaller,Bigger}) when Key > Key1 ->
    11.     {Key1,V,Smaller,insert(Key, Value, Bigger)}.

    第一个子句得到数据，并插入到一棵新树当中，第二个子句将复写已经存在的结点，第三个和第四个子句确定当Key的值小于、大于或等于树中当前结点的Key时，应该采取什么样的行为。

    1. write_tree(T) ->
    2.     write_tree(0, T).
    3.  
    4. write_tree(D, nil) ->
    5.     io:tab(D),
    6.     io:format('nil', []);
    7. write_tree(D, {Key,Value,Smaller,Bigger}) ->
    8.     D1 = D + 4,
    9.     write_tree(D1, Bigger),
    10.     io:format('~n', []),
    11.     io:tab(D),
    12.     io:format('~w ===> ~w~n', [Key,Value]),
    13.     write_tree(D1, Smaller).

    我们可以用一个测试函数将数据插入到树中，并把它打印出来：

    图4.1 一棵非平衡二叉树

    1.         nil
    2.     12 ===> fred
    3.             9 ===> susan
    4.                     nil
    5.                 8 ===> dan
    6.                     nil
    7.         7 ===> kalle
    8.                 nil
    9.             6 ===> thomas
    10.                     nil
    11.                 5 ===> rickard
    12.                     nil
    13. 4 ===> joe
    14.         nil
    15.     3 ===> jane
    16.             nil
    17.         2 ===> tobbe
    18.             nil

    注意这棵树并不是十分“平衡”。按照严格的顺序插入键的队列，比如像这样：

    1. T1 = nil,
    2. T2 = insert(1,a,T1),
    3. T3 = insert(2,a,T2),
    4. T4 = insert(3,a,T3),
    5. T5 = insert(4,a,T4),
    6. ...
    7. T9 = insert(8,a,T8).

    使这棵树看起来变成了一个列表（见图4.2）。

    图4.2 变化后的非平衡二叉树

    我们也需要能够删除二叉树内的元素：

    1. delete(Key, nil) ->
    2.     nil;
    3.  
    4.     nil;
    5.  
    6. delete(Key, {Key,_,Smaller,nil}) ->
    7.     Smaller;
    8.  
    9. delete(Key, {Key,_,nil,Bigger}) ->
    10.     Bigger;
    11.  
    12. delete(Key, {Key1,_,Smaller,Bigger}) when Key == Key1 ->
    13.     {K2,V2,Smaller2} = deletesp(Smaller),
    14.     {K2,V2,Smaller2,Bigger};
    15.  
    16. delete(Key, {Key1,V,Smaller,Bigger}) when Key < Key1 ->
    17.     {Key1,V,delete(Key, Smaller),Bigger};
    18.  
    19. delete(Key, {Key1,V,Smaller,Bigger}) when Key > Key1 ->
    20.     {Key1,V,Smaller,delete(Key, Bigger)}.

    当要删除的结点是树中的叶子，或者在这个结点下面只有一颗子树时，删除操作是很容易的（子句1到4）。子句6和7中，要删除的结点并没有被确定位置，而是继续在合适的子树中向前搜索。

    在子句5当中，要删除的结点被找到，但是它是树中的一个内部结点（例如结点同时有Smaller和Bigger子树）。这种情况下,Smaller子树中具有最大键的结点将被删除，并且整棵树在这个点重建。

    1. deletesp({Key,Value,nil,nil}) ->
    2.     {Key,Value,nil};
    3.  
    4. deletesp({Key,Value,Smaller,nil}) ->
    5.     {Key,Value,Smaller};
    6.  
    7. deletesp({Key,Value,Smaller,Bigger}) ->
    8.     {K2,V2,Bigger2} = deletesp(Bigger),
    9.     {K2,V2,{Key,Value,Smaller,Bigger2}}.