一个更好的方法是保持树在任何情况下都是平衡的。

    Adelsom-Velskii和Landis [?]（在[?]中描述）使用一个简单的标准来衡量平衡这个概念：如果一棵树的每个结点的两个子树高度之差不超过1，我们就说这棵树是平衡的。具有这种特性的树常常被称作AVL树。平衡二叉树能够在O(logN)的时间规模里完成查找、插入和删除操作，N是树中结点的个数。

    假设我们用元组{Key,Value,Height,Smaller,Bigger}表示一棵 AVL树，用{,,0,,}表示一棵空树。然后在树中的查找操作就很容易实现了：

    1. insert(Key, Value, {nil,nil,0,nil,nil}) ->
    2.     E = empty_tree(),
    3.     {Key,Value,1,E,E};
    4.  
    5. insert(Key, Value, {K2,V2,H2,S2,B2}) when Key == K2 ->
    6.     {Key,Value,H2,S2,B2};
    7.  
    8. insert(Key, Value, {K2,V2,_,S2,B2}) when Key < K2 ->
    9.     {K4,V4,_,S4,B4} = insert(Key, Value, S2),
    10. combine(S4, K4, V4, B4, K2, V2, B2);
    11.  
    12. insert(Key, Value, {K2,V2,_,S2,B2}) when Key > K2 ->
    13.     {K4,V4,_,S4,B4} = insert(Key, Value, B2),
    14.     combine(S2, K2, V2, S4, K4, V4, B4).
    15.  
    16. empty_tree() ->
    17.     {nil,nil,0,nil,nil}.

    思路是找到要插入的项将被插入到什么地方，如果插入使得树变得不平衡了，那么就平衡它。平衡一棵树的操作通过combine函数实现。

    打印一棵树也很简单:

    1. write_tree(T) ->
    2.     write_tree(0, T).
    3.  
    4.     io:tab(D),
    5.     io:format('nil', []);
    6.  
    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).

    现在让我们来看看我们的劳动成果。假设我们在一棵AVL树中插入键为1,2,3,…,16的16个数据。结果如图4.3，它是一棵平衡的树了（跟上一节那棵变形的树比较一下）。

    图4.3 一棵平衡二叉树

    1.                     nil
    2.                 16 ===> a
    3.                     nil
    4.             15 ===> a
    5.                 nil
    6.         14 ===> a
    7.                 nil
    8.             13 ===> a
    9.                 nil
    10.     12 ===> a
    11.             11 ===> a
    12.                 nil
    13.         10 ===> a
    14.                 nil
    15.             9 ===> a
    16.                 nil
    17. 8 ===> a
    18.                 nil
    19.             7 ===> a
    20.                 nil
    21.         6 ===> a
    22.                 nil
    23.             5 ===> a
    24.                 nil
    25.     4 ===> a
    26.                 nil
    27.             3 ===> a
    28.                 nil
    29.         2 ===> a
    30.                 nil
    31.                 nil

    deletisp函数删除并返回树中最大的元素。

    脚注