ctree1.erl

-module(ctree).
-export([merge/2, split/2, add/2, add/3, remove/2, flatten/1, random/1, ordered/1, fromlist/1, remove_list/2, depth/1]).

% null / {Key, Param, Left, Right}

% Объединяет 2 дерева (любой элемент левого меньше любого элемента правого(
merge(null, B) -> B;
merge(A, null) -> A;
merge(A, B) ->
  {A_key, A_param, A_left, A_right} = A,
  {B_key, B_param, B_left, B_right} = B,
  if 
    A_param>B_param -> 
      {A_key, A_param, A_left, merge(A_right, B)};
    true -> 
      {B_key, B_param, merge(A, B_left), B_right}
  end.

% Разбивает дерево на 2 поддерева: <SplitKey, >=SplitKey
split(null, _) -> {null, null};
split(A, SplitKey) ->
  {Key, Param, Left, Right} = A,
  if
    Key<SplitKey -> % Направо 
      {NL, NR} = split(Right, SplitKey), 
      {{Key, Param, Left, NL}, NR};
    true -> % Налево
      {NL, NR} = split(Left, SplitKey), 
      {NL, {Key, Param, NR, Right}}
  end.

% Добавляет ключ Key со случайным параметром в дерево
add(Tree, Key) -> add(Tree, Key, random:uniform()).

% Добавляет ключ NewKey с параметром NewParam в дерево
add(null, NewKey, NewParam) -> {NewKey, NewParam, null, null};
add(Tree, NewKey, NewParam) -> 
  {Key, Param, Left, Right} = Tree,
  if 
    Param<NewParam -> % Новая вершина
      {NL, NR} = split(Tree, NewKey), 
      {NewKey, NewParam, NL, NR};
    NewKey<Key -> % В левое поддерево
      {Key, Param, add(Left, NewKey, NewParam), Right}; 
    true -> % В правое поддерево
      {Key, Param, Left, add(Right, NewKey, NewParam)}
  end.

% Удаляет ключ RemoveKey из дерева
remove(Tree, RemoveKey) -> 
  {Key, Param, Left, Right} = Tree,
  if
    Key==RemoveKey -> % Элемент в вершине - удаляем
      merge(Left, Right);
    Key<RemoveKey -> % Элемент в правом поддереве
      {Key, Param, Left, remove(Right, RemoveKey)};
    true -> % Элемент в левом поддереве
      {Key, Param, remove(Left, RemoveKey), Right}
  end.

% Мелкие функции для работы с деревьями

flatten(null) -> [];
flatten({Key, _, Left, Right}) -> 
  flatten(Left) ++ [Key | flatten(Right)].

random(0) -> null;
random(Size) -> add(random(Size-1), round(random:uniform()*1000)).

ordered(0) -> null;
ordered(Size) -> add(ordered(Size-1), Size).

fromlist([]) -> null;
fromlist([Head | Tail]) -> add(fromlist(Tail), Head).

remove_list(Tree, []) -> Tree;
remove_list(Tree, [Head | Tail]) -> remove_list(remove(Tree, Head), Tail).
 
depth(null) -> 0;
depth({_, _, Left, Right}) -> 
  D1 = depth(Left),
  D2 = depth(Right),
  if 
    D1<D2 -> D2 + 1;
    true -> D1 + 1
  end.