平衡二叉树

平衡二叉树

在前面几节里，我们学会了怎样构建一棵非平衡二叉树。但不幸的是非平衡二叉树可能会变成一个列表，这样对树的插入和删除操作就是非随机的了。

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

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

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

lookup(Key, {nil,nil,0,nil,nil}) ->
    not_found;

lookup(Key, {Key,Value,_,_,_}) ->
    {found,Value};

lookup(Key, {Key1,_,_,Smaller,Bigger}) when Key < Key1 ->
    lookup(Key,Smaller);

lookup(Key, {Key1,_,_,Smaller,Bigger}) when Key > Key1 ->
    lookup(Key,Bigger).

lookup的代码和非平衡二叉树中的基本一样。插入操作这样实现：

insert(Key, Value, {nil,nil,0,nil,nil}) ->
    E = empty_tree(),
    {Key,Value,1,E,E};

insert(Key, Value, {K2,V2,H2,S2,B2}) when Key == K2 ->
    {Key,Value,H2,S2,B2};

insert(Key, Value, {K2,V2,_,S2,B2}) when Key < K2 ->
    {K4,V4,_,S4,B4} = insert(Key, Value, S2),
combine(S4, K4, V4, B4, K2, V2, B2);

insert(Key, Value, {K2,V2,_,S2,B2}) when Key > K2 ->
    {K4,V4,_,S4,B4} = insert(Key, Value, B2),
    combine(S2, K2, V2, S4, K4, V4, B4).

empty_tree() ->
    {nil,nil,0,nil,nil}.

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

combine({K1,V1,H1,S1,B1},AK,AV,
        {K2,V2,H2,S2,B2},BK,BV,
        {K3,V3,H3,S3,B3} ) when H2 > H1, H2 > H3 ->
            {K2,V2,H1 + 2,
             {AK,AV,H1 + 1,{K1,V1,H1,S1,B1},S2},
             {BK,BV,H3 + 1,B2,{K3,V3,H3,S3,B3}}
            };
combine({K1,V1,H1,S1,B1},AK,AV,
        {K2,V2,H2,S2,B2},BK,BV,
        {K3,V3,H3,S3,B3} ) when H1 >= H2, H1 >= H3 ->
            HB = max_add_1(H2,H3),
    HA = max_add_1(H1,HB),
    {AK,AV,HA,
            {K1,V1,H1,S1,B1},
            {BK,BV,HB,{K2,V2,H2,S2,B2},{K3,V3,H3,S3,B3}}
           };
combine({K1,V1,H1,S1,B1},AK,AV,
        {K2,V2,H2,S2,B2},BK,BV,
        {K3,V3,H3,S3,B3} ) when H3 >= H1, H3 >= H2 ->
            HA = max_add_1(H1,H2),
    HB = max_add_1(HA,H3),
    {BK,BV,HB ,
            {AK,AV,HA,{K1,V1,H1,S1,B1},{K2,V2,H2,S2,B2}},
            {K3,V3,H3,S3,B3}
           }.

max_add_1(X,Y) when X =< Y ->
    Y + 1;
max_add_1(X,Y) when X > Y ->
    X + 1.

打印一棵树也很简单:

write_tree(T) ->
    write_tree(0, T).

write_tree(D, {nil,nil,0,nil,nil}) ->
    io:tab(D),
    io:format('nil', []);

write_tree(D, {Key,Value,_,Smaller,Bigger}) ->
    D1 = D + 4,
    write_tree(D1, Bigger),
    io:format('~n', []),
    io:tab(D),
    io:format('~w ===> ~w~n', [Key,Value]),
    write_tree(D1, Smaller).

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

最后是AVL树中的删除操作：

delete(Key, {nil,nil,0,nil,nil}) ->
    {nil,nil,0,nil,nil};

delete(Key, {Key,_,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}}) ->
    {nil,nil,0,nil,nil};

delete(Key, {Key,_,_,Smaller,{nil,nil,0,nil,nil}}) ->
    Smaller;

delete(Key, {Key,_,_,{nil,nil,0,nil,nil},Bigger}) ->
    Bigger;

delete(Key, {Key1,_,_,Smaller,{K3,V3,_,S3,B3}}) when Key == Key1 ->
    {K2,V2,Smaller2} = deletesp(Smaller),
    combine(Smaller2, K2, V2, S3, K3, V3, B3);

delete(Key, {K1,V1,_,Smaller,{K3,V3,_,S3,B3}}) when Key < K1 ->
    Smaller2 = delete(Key, Smaller),
    combine(Smaller2, K1, V1, S3, K3, V3, B3);

delete(Key, {K1,V1,_,{K3,V3,_,S3,B3},Bigger}) when Key > K1 ->
    Bigger2 = delete(Key, Bigger),
    combine( S3, K3, V3, B3, K1, V1, Bigger2).

图4.3 一棵平衡二叉树

                    nil
                16 ===> a
                    nil
            15 ===> a
                nil
        14 ===> a
                nil
            13 ===> a
                nil
    12 ===> a
                nil
            11 ===> a
                nil
        10 ===> a
                nil
            9 ===> a
                nil
8 ===> a
                nil
            7 ===> a
                nil
        6 ===> a
                nil
            5 ===> a
                nil
    4 ===> a
                nil
            3 ===> a
                nil
        2 ===> a
                nil
            1 ===> a
                nil

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

deletesp({Key,Value,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}}) ->
    {Key,Value,{nil,nil,0,nil,nil}};
deletesp({Key,Value,_,Smaller,{nil,nil,0,nil,nil}}) ->
    {Key,Value,Smaller};
deletesp({K1,V1,2,{nil,nil,0,nil,nil},
         {K2,V2,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}}}) ->
            {K2,V2,
             {K1,V1,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}}
            };

deletesp({Key,Value,_,{K3,V3,_,S3,B3},Bigger}) ->
        {K2,V2,Bigger2} = deletesp(Bigger),
        {K2,V2,combine(S3, K3, V3, B3, Key, Value, Bigger2)}.

脚注