Есть книжка, называется "Concurrent Programming in Erlang", авторы Joe Armstrong, Robert Virding, Claes Wikström и Mike Williams.
Там есть глава по сбалансированным бинарным деревьям (AVL — деревьям) — как реализовать эту структуру данных на функциональном языке. Когда я тупо попытался вколотить этот код в редактор, компилятор дал мне понять, что я был не прав. Пришлось разбираться в этой реализации, заодно вспомнить AVL-деревья и сделать свой вариант (в принципе получилось то же самое, но есть и различия).
Когда мне это удалось, захотелось выложить код с комментариями сюда, потом показалось, что всё это тривиально и желание пропало. Сейчас оно снова появилось, потому что одному человеку стало интересно, чем же хорош паттерн матчинг, и чем он отличается от простых if'ов; Для демонстрации нужен был какой нибудь пример, желательно не совсем уж банальный.
Наверное, это будет интересно (полезно?) многим. В принципе, для гуру здесь ничего нового, они могут пробежаться глазами просто.
Дерево — это кортеж {Ключ, Высота, Меньшее_поддерево, Большее_поддерево}. Элемент Высота нужен для балансировки. В оригинале реализовывалось отображение Key->Value, где ключи располагались в узлах АВЛ-дерева, однако Value только мешается, поэтому его убираем. В левом поддереве все ключи меньше Ключа, в правом — больше. Дублирование исключено. Пустое дерево — это кортеж {nil,0,nil,nil}.
Заголовок.
-module (avltree).
-export ([test0/0, test1/0, test2/0]).
про функции test?() — в конце. Нам понадобятся маленькие вспомогательные функции:
empty_tree() -> {nil, 0, nil, nil}.
elt_k({K, _, _, _}) -> K.
elt_h({_, H, _, _}) -> H.
elt_s({_, _, S, _}) -> S.
elt_b({_, _, _, B}) -> B.
max(X, Y) when X > Y -> X;
max(X, Y) when X =< Y -> Y.
Функция lookup ищет в дереве данный ключ. Каждая функция определяется одним или несколькими "телами" (clauses), каждое "тело" — это реакция на совпадение фактических параметров с данным паттерном. Паттерн может быть сколь угодно сложным. Обратите внимание как сформулировано условие "если первый параметр и первый элемент в кортеже совпадают" (в данном случае совпадение — это равенство) и как сформулировано условие "... различаются"
lookup(_, {nil, 0, nil, nil}) ->
key_not_found;
lookup(Key, {Key, H, S, B}) ->
{Key, H, S, B};
lookup(Key, {Key1, _, Smaller, Bigger}) ->
if
Key < Key1 -> lookup(Key, Smaller);
Key > Key1 -> lookup(Key, Bigger)
end.
Функция insert вставляет ключ Key в дерево. Во втором "теле" вместо паттерна "K, {K,H,S,B}" использовано
соответствующее условие (guard).
insert(Key, {nil, 0, nil, nil}) ->
E = empty_tree(),
{Key, 1, E, E};
insert(Key, {K, H, S, B}) when Key == K ->
{K, H, S, B};
insert(Key, {K, _, S, B}) when Key < K ->
{Ks, _, Ss, Bs} = insert(Key, S),
combine(Ss, Ks, Bs, K, B);
insert(Key, {K, _, S, B}) when Key > K ->
{Kb, _, Sb, Bb} = insert(Key, B),
combine(S, K, Sb, Kb, Bb).
Последние 2 "тела" нужно пояснить. Функция combine собирает сбалансированное дерево из 5 кусочков — трёх деревьев и двух ключей. Между этими кусочками должно выполняться соотношение T1 < Kx < T2 < Kx < T3, где T1, Kx, T2, Kx, T3 — это как раз набор параметров для функции combine (T? — деревья, K? — ключи, T < K означает, что все ключи в T меньше K).
Короче, в первом "теле" ключ Key должен быть добавлен в меньшее поддерево S, после добавление мы получаем сбалансированное дерево {Ks, _, Ss, Bs}, и к этому дереву нужно добавить ещё 2 кусочка K и B. После добавления, дерево может "перекосить",
поэтому надо, чтобы combine снова собрал нам сбалансированное дерево. Аналогично со вторым "телом".
Теперь функция delete — удаления ключа Key из дерева. Удаление несколько сложнее: здесь возникает много мелких частных случаев.
Удаляем из пустого дерева и одноэлементного дерева — здесь всё понятно. Хотя в случае пустого дерева можно вернуть какой-нибудь атом-варнинг.
delete(Key, {nil, 0, nil, nil}) ->
{nil, 0, nil, nil};
delete(Key, {Key, 1, {nil, 0, nil, nil}, {nil, 0, nil, nil}}) ->
{nil, 0, nil, nil};
Далее распознаём следующие вырожденные деревья ({E} — пустое дерево):
% Key
% / \ ===> B
% {E} B
delete(Key, {Key, _, {nil, 0, nil, nil}, B}) ->
B;
% Key
% / \ ===> S
% S {E}
delete(Key, {Key, _, S, {nil, 0, nil, nil}}) ->
S;
Следующие два случая ниже не были учтены, из-за чего валился test1(). S1 должно быть всегда пустым деревом но можно оставить такой, чуть более общий, вариант. (S1 пустое потому, что S1 получается из S удалением элемента, и S не может быть
большим, так как исходное дерево сбалансированное). Аналогично рассуждая, B1 тоже должно быть пустым деревом, но опять же, оставим B1.
%
% Key Key
% / \ ===> / \
% S {E} S1 {E}
delete(Key, {K, _, S, {nil, 0, nil, nil}}) when Key < K ->
S1 = delete(Key, S),
{K, elt_h(S1) + 1, S1, {nil, 0, nil, nil}};
% Key Key
% / \ ===> / \
% {E} B {E} B1
delete(Key, {K, _, {nil, 0, nil, nil}, B}) when Key > K ->
B1 = delete(Key, B),
{K, elt_h(B1) + 1, {nil, 0, nil, nil}, B1};
Наконец, остался случай невырожденного дерева. Если искомый ключ меньше или больше текущего, то нужно удалить его в соответствующем поддереве и перебалансировать дерево (см. случаи Key < K и Key > K). Если же искомый ключ равен текущему, то удаление ключа Key разбивает дерево на два несвязных поддерева:
% Key
% / \ ===>
% S B S B
и из этих двух кусочков нам нужно собрать новое дерево. Как? Нужно найти новый корень. Претендентами на новый корень являются либо максимальный ключ в S, либо минимальный ключ в B. Случаи совершенно равноправные, поэтому не сильно заморачиваясь выберем максимальный ключ в S. После этого удаляем этот ключ из S, для оставшегося куска будет справедливо S1 < K:
% K
% S ===> /
% S1
Взглянув в деревце B более пристально, увидим, что оно есть {Kb, ?, Sb, Bb} и получим снова 5 кусочков (S1 < K < Sb < Kb < Bb), из которых мы можем собрать новое сбалансированное дерево:
% K K Kb
% / ===> / / \ ===> combine(S1, K, Sb, Kb, Bb)
% S1 B S1 Sb Bb
delete(Key, {K, _, S, B}) ->
if
Key == K ->
{K1, S1} = extract_max(S),
combine(S1, K1, elt_s(B), elt_k(B), elt_b(B));
Key < K ->
S1 = delete(Key, S),
combine(S1, K, elt_s(B), elt_k(B), elt_b(B));
Key > K ->
B1 = delete(Key, B),
combine(elt_s(S), elt_k(S), elt_b(S), K, B1)
end.
Функция extract_max (бывшая deletesp) ищет максимальный ключ в дереве, удаляет его оттуда и возвращает пару из этого ключа и оставшегося после удаления дерева.
extract_max({K, _, S, {nil, 0, nil, nil}}) ->
{K, S};
extract_max({_, _, {nil, 0, nil, nil}, B}) ->
extract_max(B);
extract_max({K, _, {K1, _, S1, B1}, B}) ->
{K2, B2} = extract_max(B),
{K2, combine(S1, K1, B1, K, B2)}.
Осталась функция combine. Для функции combine важно, чтобы для параметров сохранялось условие T1 < Kx < T2 < Ky < T3, иначе результатом будет
combine(T1, Kx, T2, Ky, T3) ->
H1 = elt_h(T1),
H2 = elt_h(T2),
H3 = elt_h(T3),
if
H2 > H1, H2 > H3 ->
{elt_k(T2), H2 + 2, {Kx, H2 + 1, T1, elt_b(T2)}, {Ky, H2 + 1, elt_s(T2), T3}};
H1 >= H2, H1 >= H3 ->
Hy = max(H2, H3) + 1,
Hx = max(H1, Hy) + 1,
{Kx, Hx, T1, {Ky, Hy, T2, T3}};
H3 >= H2, H3 >= H1 ->
Hx = max(H1, H2) + 1,
Hy = max(Hx, H3) + 1,
{Ky, Hy, {Kx, Hx, T1, T2}, T3}
end.
Сборка нового дерева зависит от того, какое дерево самое высокое. Если T2 самое высокое, то:
K2
/ \
Kx Ky Kx K2 Ky Kx Ky
/ T2 \ ===> / / \ \ ===> / \ / \
T1 T3 T1 S2 B2 T3 T1 S2 B2 T3
если T1, то
Kx
/ \
Kx Ky T1 Ky
/ T2 \ ===> / \
T1 T3 T2 T3
наконец, если самое высокое T3, то
Ky
/ \
Kx Ky Kx T3
/ T2 \ ===> / \
T1 T3 T1 T2
Для сравнения, вот как выглядели функции combine и deletesp раньше:
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}
}.
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)}.
Вроде бы получилось лучше
Что осталось? Осталось распечатать деревце, и написать небольшие тестики.
write_tree(T) ->
write_tree(0, T),
io:format("\n").
write_tree(D, nil) ->
indent(D),
io:format('nil', []);
write_tree(D, {K, H, S, B}) ->
D1 = D + 4,
write_tree(D1, B),
io:format('~n', []),
indent(D),
io:format('~w:~w ==>|~n', [K, H]),
write_tree(D1, S).
indent(D) when D > 0 ->
io:format("\t"),
indent(D-4);
indent(D) when D =< 0 ->
noop.
test0() ->
E = empty_tree(),
T1 = insert(13, E),
T2 = insert(13, T1),
T = insert(15, T2),
TE = lookup(13, T),
TN = lookup(99, T),
write_tree(T),
write_tree(TE),
io:format(TN).
test1() ->
E = empty_tree(),
T1 = insert(1,E),
T2 = insert(2,T1),
T3 = insert(3,T2),
T4 = insert(4,T3),
T5 = insert(5,T4),
T6 = insert(6,T5),
T7 = insert(7,T6),
T8 = insert(8,T7),
T9 = insert(9,T8),
T10 = insert(10,T9),
T11 = insert(11,T10),
T12 = insert(12,T11),
T13 = insert(13,T12),
T14 = insert(14,T13),
T15 = insert(15,T14),
T16 = insert(16,T15),
write_tree(T16),
T17 = delete(16, T16),
write_tree(T17).
test2() ->
E = empty_tree(),
X1 = {13, 1, E, E},
X2 = {15, 1, E, E},
X3 = {17, 1, E, E},
write_tree(combine(X1, 14, X2, 16, X3)).
Работает!
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
