BaseAvlSet/Tree use O(n*log n) memory

[Henning Kiel]

A rebalance causes nodes to be recreated though only the pointers need to be adapted, same holds for height value.
I propose to use arrays (or Mutable) to hold and update these values to have O(n) memory usage.

BaseAvlTree inherits from BaseAvlSet. Special care needs to be taken for its map and mapFold function.

record NODE
  Key key "The key of the node.";
  array<Integer> height "Height of tree, used for balancing";
  array<Tree> subtrees "Left+right subtrees.";
end NODE;

function left
  input Tree tree;
  output Tree = tree.subtrees[1];
end left;

function right
  input Tree tree;
  output Tree = tree.subtrees[2];
end right;

[Martin Sjölund]

That would make the AvlSet mutable like the HashTable and introduce all the problems we have with those (you cannot share sets or fail in a matchcontinue after you modified the set). The garbage is collected anyway. What could possibly be done is reduce the number of rebalancing needed by tweaking the allowed height differences.

[Francesco Casella]

Rescheduled to 1.14.0 after 1.13.0 releasee

[Francesco Casella]

Releasing 1.14.0 which is stable and has many improvements w.r.t. 1.13.2. This issue is rescheduled to 1.16.0

[Francesco Casella]

Retargeted to 1.17.0 after 1.16.0 release

[Francesco Casella]

Retargeted to 1.18.0 because of 1.17.0 timed release.

[Francesco Casella]

Ticket retargeted after milestone closed