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 函數,對指定的二元搜尋樹求平均走訪次數。提示:你須要取出樹的全部節點,並分別使用每個節點走訪這株樹;將每個走訪次數加總求平均。