非平衡二叉树

字典适合保存少量的数据项，但是当项的数量不断增加，更好的方法是用通过使用键的序列关系来访问数据的树形结构来组织数据。这种结构的访问时间与它所包含的项的数量成对数关系–列表是线性的访问时间。

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

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

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

函数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).

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

  1. test1() ->
  2.     S1 = nil,
  3.     S2 = insert(4,joe,S1),
  4.     S3 = insert(12,fred,S2),
  5.     S4 = insert(3,jane,S3),
  6.     S5 = insert(7,kalle,S4),
  7.     S6 = insert(6,thomas,S5),
  8.     S7 = insert(5,rickard,S6),
  9.     S8 = insert(9,susan,S7),
  10.     S9 = insert(2,tobbe,S8),
  11.     S10 = insert(8,dan,S9),
  12.     write_tree(S10).

图4.1 一棵非平衡二叉树

  1.         nil
  2.     12 ===> fred
  3.                 nil
  4.             9 ===> susan
  5.                     nil
  6.                 8 ===> dan
  7.                     nil
  8.         7 ===> kalle
  9.                 nil
  10.             6 ===> thomas
  11.                     nil
  12.                 5 ===> rickard
  13.                     nil
  14. 4 ===> joe
  15.         nil
  16.     3 ===> jane
  17.             nil
  18.         2 ===> tobbe
  19.             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.                                     nil
  2.                             8 ===> a
  3.                                 nil
  4.                         7 ===> a
  5.                             nil
  6.                     6 ===> a
  7.                         nil
  8.                 5 ===> a
  9.                     nil
  10.             4 ===> a
  11.                 nil
  12.         3 ===> a
  13.             nil
  14.     2 ===> a
  15.         nil
  16. 1 ===> a
  17.     nil

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

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