Erlang程式設計與問題解決/樹

計算機科學 > 編程 > Erlang程式設計與問題解決

樹結構是將幾個節點連通，使每一個節點對其他每一個節點的連通路徑各只有一條。樹符合下列性質。

1. 空集合是樹。
2. 以一個節點做為樹根，其下擁有若干子樹，這樣也是樹。

以下由一個二元樹的定義開始，介紹 Erlang 如何實作樹及演算法。

二元樹

樹的基本構成，有兩種情況：

nil                 % 空集合
{Root, Left, Right} % 有樹根、左子樹和右子樹

先有一個最簡單的樹生產式 create/1 ，產生 N 個節點並且大致平衡的樹。用 x 標示節點位置。

-module(binary_tree).
-compile(export_all).

create(0) ->
    nil;
create(N) ->
    Half = (N-1) div 2,
    {x, create(Half), create(N-1-Half)}.

> binary_tree:create(6).
{x,{x,nil,{x,nil,nil}},{x,{x,nil,nil},{x,nil,nil}}}

上述程式提供了雛型，讓我們可以由簡單的結果檢查程式是否運作良好。我們可以轉抄上述程式的框架，寫成資料妥善分配的版本。

create([]) ->
    nil;
create([X|Xs]) ->
    Half = (length(Xs)-1) div 2,
    {Left, Right} = split_at(Half, Xs),
    { X, create(Left), create(Right) }.

split_at(0, Xs) ->
    {[], Xs};
split_at(N, [X|Xs]) ->
    {Ys, Zs} = split_at(N-1, Xs),
    {[X|Ys], Zs}.

程式執行結果為：

> binary_tree:create([a,b,c,d]).
{a,{b,nil,nil},{c,nil,{d,nil,nil}}}

接着還可以寫一些函數檢查樹的一些屬性：例如， height/1 檢查樹高度， node_count/1 檢查節點數目， node_count_at/2 檢查某一層的節點數目。

height(nil) ->
    0;
height({_,L,R}) ->
    1 + erlang:max(height(L), height(R)).

node_count(nil) ->
    0;
node_count({_,L,R}) ->
    1 + node_count(L) + node_count(R).

node_count_at(_, nil) ->
    0;
node_count_at(1, {_,_,_}) ->
    1;
node_count_at(Level, {_,L,R}) ->
    node_count_at(Level-1, L) + node_count_at(Level-1, R).

接着，接到一個列表，產生全部可能的樹，程式如下：

all_trees([]) ->
    [nil];
all_trees([X|Xs]) ->
    [ {X, L, R}
      || {Ls, Rs} <- [ split_at(Half,Xs) 
		       || Half <- lists:seq(0,length(Xs))],
	 L <- all_trees(Ls),
	 R <- all_trees(Rs) ].

稍做修改，可以求全部可能的樹的高度：

all_trees_height([]) ->
    [0];
all_trees_height([_|Xs]) ->
    [ 1 + erlang:max(Ln,Rn)
      || {Ls, Rs} <- [ split_at(Half,Xs)
		       || Half <- lists:seq(0,length(Xs))],
	 Ln <- all_trees_height(Ls),
	 Rn <- all_trees_height(Rs) ].

平衡樹

平衡樹，又叫做自我平衡樹，有好幾種類別。其中一種稱為 AVL tree ，是指在樹的左子樹與右子樹的高度，最多不相差超過 1 。

AVL 樹

現在，要做的問題是，給一個列表，產生可能構成的 AVL 樹。我們已經有一個 all_tree/1 可以產生一個列表全部可能有的樹。對每一株樹，我們可以有 is_avl_tree/1 判斷是否為 AVL 樹。

is_avl_tree(nil) ->
    true;
is_avl_tree({_,L,R}) ->
    case height(L) - height(R) of
	0 ->
	    is_avl_tree(L) and is_avl_tree(R);
	1 ->
	    is_avl_tree(L) and is_avl_tree(R);
	-1 ->
	    is_avl_tree(L) and is_avl_tree(R);
	_ ->
	    false
    end.

於是，使用 lists 模組的 filter 函數，可以根據指定的準則，將符合的結果找出。我們可以找出全部的 AVL tree 。

avl_trees(Xs) ->
    lists:filter(
        fun(T) -> test:is_avl_tree(T) end,
        all_trees(Xs)
    ).

> binary_tree:avl_trees([a,b,c,d]).
[{a,{b,nil,nil},{c,nil,{d,nil,nil}}},
 {a,{b,nil,nil},{c,{d,nil,nil},nil}},
 {a,{b,nil,{c,nil,nil}},{d,nil,nil}},
 {a,{b,{c,nil,nil},nil},{d,nil,nil}}]

完整樹

接下來討論另一種平衡樹：完整樹 ( complete tree ) 。完整樹是在它最高高度以下的任何一層中，能夠補滿節點的位置都補滿了。而在樹的最高一層，所有的節點全部向左靠齊，留下右邊全都是 nil 。或者，最高的一層也全部補滿。

從上述建構樹的程式的思路走來，我們發現，上述的樹建構都思考子樹本身的局部情況。然而，來處理完整樹時，你必須思考自己子樹和其他子樹的一些節點的情況。所以，在此要寫一些新的函數。

level_at/2 是從樹中取出指定層次的一列節點；要注意的是，把一層裏沒有節點的位置填上 nil ：

level_at(1, nil) ->
    [nil];
level_at(1, {Rt,_,_}) ->
    [Rt];
level_at(N, nil) when N > 1 ->
    level_at(N-1, nil) ++ level_at(N-1, nil);
level_at(N, {_,L,R}) when N > 1 ->
    level_at(N-1, L) ++ level_at(N-1, R).

對最高高度以下的任何一層，用 check_level_full/1 檢查列表中全部填滿節點，也就是沒有 nil ：

check_level_full([]) ->
    true;
check_level_full([nil|_]) ->
    false;
check_level_full([_|Ns]) ->
    check_level_full(Ns).

對最高高度一層，用 check_level_complete/1 檢查列表中的節點全部向左靠齊：

check_level_complete([]) ->
    true;
check_level_complete([_]) ->
    true;
check_level_complete([nil,Node|_]) when Node /= nil ->
    false;
check_level_complete([_|Ns]) ->
    check_level_complete(Ns).

於是，檢查一株樹是不是完整樹，作法是先取樹高，接着求低於樹高的每一層都是填滿節點，最後求最高層節點都向左靠齊：

check_complete_tree(nil) ->
    true;
check_complete_tree(T) ->
    Height = height(T),
    check_full_level_at([ level_at(H,T) || H <- lists:seq(1,Height-1) ])
	andalso check_complete_level_at(Height, T).

check_complete_level_at(H, T) ->
    check_level_complete(level_at(H, T)).

check_full_level_at([]) ->
    true;
check_full_level_at([Level|Ls]) ->
    check_level_full(Level) andalso check_full_level_at(Ls).

使用下列主程式，先產生全部可能的樹，然後對每一株樹檢查並篩選出完整樹：

complete_trees(Xs) ->
    lists:filter(
      fun check_complete_tree/1,
      all_trees(Xs)
     ).

% lists:filter/2 使用指定的檢查函數 fun check_complete_tree/1
% 判斷一個列表 all_trees(Xs) 中有哪些樹是完整樹。如果是，就篩選出來

執行情況為：

> binary_tree:complete_trees([a,b,c,d,e,f,g]).
[{a,{b,{c,nil,nil},{d,nil,nil}},{e,{f,nil,nil},nil}}]
> binary_tree:complete_trees([a,b,c,d,e,f,g,h]).
[{a,{b,{c,nil,nil},{d,nil,nil}},
    {e,{f,nil,nil},{g,nil,nil}}}]
> binary_tree:complete_trees([a,b,c,d,e,f,g,h,i]).
[{a,{b,{c,{d,nil,nil},nil},{e,nil,nil}},
    {f,{g,nil,nil},{h,nil,nil}}}]
> binary_tree:complete_trees([a,b,c,d,e,f,g,h,i]).
[{a,{b,{c,{d,nil,nil},{e,nil,nil}},{f,nil,nil}},
    {g,{h,nil,nil},{i,nil,nil}}}]

練習題

最大堆積樹 ( max heap ) 有若干性質為： (1) 是樹，擁有樹的各種性質 (2) 任一子樹的左、右子樹每一節點都不大於樹根節點。請仿照本節的程式手法──產生並過濾──撰寫 max_heap:create/1 ，輸入一個數值列表，產生出各種可能的最大堆積樹。

二元搜尋樹

二元搜尋樹是有序的樹結構，可以在其中以二元搜尋法尋找資料。首先，可以用最簡單的二部份來建構二元搜尋樹：關於列表的處理和節點的插入。

-module(bstree).
-compile(export_all).

create([]) ->
    nil;
create([X|Xs]) ->
    insert(X, create(Xs)).

insert(X, nil) ->
    {X, nil, nil};
insert(X, {X, L, R}) ->
    {X, insert(X, L), R};
insert(X, {Y, L, R}) when X > Y ->
    {Y, L, insert(X, R)};
insert(X, {Y, L, R}) ->
    {Y, insert(X, L), R}.

基本上已經可以將任何列表轉換為二元搜尋樹了。樹的結構由列表資料決定：例如，以下案例產生最糟情況的二元搜尋樹，看起來就像是鏈接串列。

> bstree:create([1,2,3,4,5,6,7,8]).
{8,
 {7,{6,{5,{4,{3,{2,{1,nil,nil},nil},nil},nil},nil},nil},nil},
 nil}

可想而知，須調整樹的平衡程度。

樹的平衡

樹的調整步驟可分為樹左移和樹右移。以樹左移來說，是從樹的右子樹取最左端點當做新的樹根，同時將舊樹根插入左子樹，就得到左移一步的新樹。樹右移的步驟與樹左移對稱。

為了做到樹左右移，我們需要幾個函數： node_count/1 求子數的節點總數、 take_leftest/1 取出子樹最左端點並留下餘樹、 take_rightest/1 取出子樹最右端點並留下餘樹。

node_count(nil) ->
    0;
node_count({_,L,R}) ->
    1 + node_count(L) + node_count(R).

take_leftest(nil) ->
    {nil, nil};
take_leftest({Rt,nil,R}) ->
    {Rt, R};
take_leftest({Rt,L,R}) ->
    {Node, Rest} = take_leftest(L),
    {Node, {Rt, Rest, R}}.

take_rightest(nil) ->
    {nil, nil};
take_rightest({Rt,L,nil}) ->
    {Rt, L};
take_rightest({Rt,L,R}) ->
    {Node, Rest} = take_rightest(R),
    {Node, {Rt, L, Rest}}.

已知樹左移與樹右移如下列程式：

shl(nil) ->
    nil;
shl({Rt,L,R}) ->
    {Node, Rest} = take_leftest(R),
    {Node, insert(Rt, L), Rest}.

shr(nil) ->
    nil;
shr({Rt,L,R}) ->
    {Node, Rest} = take_rightest(L),
    {Node, Rest, insert(Rt, R)}.

則樹平衡為函數 balance/1 ：求左右子樹節點數目，當二子樹節點數目相差超過一個，就要做樹左移或樹右移；並且，二子樹也要做樹平衡。

balance(nil) ->
    nil;
balance({Rt,L,R}) ->
    Nl = node_count(L),
    Nr = node_count(R),
    if
        Nl - Nr > 1 ->
	    balance(shr({Rt,L,R}));
	Nr - Nl > 1 ->
	    balance(shl({Rt,L,R}));
	true ->
	    {Rt, balance(L), balance(R)}
    end.

二元搜尋樹的平衡情況如下例：

> bstree:balance(bstree:create([1,2,3,4,5,6,7,8])).
{5,
 {3,{2,{1,nil,nil},nil},{4,nil,nil}},
 {7,{6,nil,nil},{8,nil,nil}}}

練習一

以上述二元搜尋樹為例，撰寫 search/2 函數，在樹中尋找指定資料。當資料找到時，傳回 {Data, Traversal} ， Traversal 為走訪次數。 (由任一樹根走往左子樹樹根算走訪一次，同理，走往右子樹樹根也算走訪一次。) 如果找不到資料，傳回 {nil, Traversal} 。

練習二

撰寫 avg_traversal/1 函數，對指定的二元搜尋樹求平均走訪次數。提示：你須要取出樹的全部節點，並分別使用每個節點走訪這株樹；將每個走訪次數加總求平均。