Erlang (programming language)/Tutorials/gb sets

gb_sets

Why go to the bother of using a structure other than a list for sets? Normally for small sets, lists work fine. But operations on lists are slow, and awkward if the list is long. Long depends on the machine and available memory. Generally speaking, a balanced binary tree will give the fastest access time of most any alternative data structure. Generally the speed is O(log(n)) for a binary tree. Whereas a list is order O(n).

Using gb_sets

Lets create a genalized balanced set from a list.

1> A = gb_sets:from_list([1,2,3,4,5]).
{5,{3,{2,{1,nil,nil},nil},{5,{4,nil,nil},nil}}}

     3
    / \
   2   5
  /   / \
 1   4   

Now we remove an element.

2> B = gb_sets:del_element(1,A).
{4,{3,{2,nil,nil},{5,{4,nil,nil},nil}}}

   3
  / \
 2   5
    / \
   4

And remove another element.

4> C = gb_sets:del_element(2,B).
{3,{3,nil,{5,{4,nil,nil},nil}}}
 
    3
   / \ 
      5
     / \
    4

Now we should balance the tree to keep our speed maximized.

5> D = gb_sets:balance(C).
{3,{4,{3,nil,nil},{5,nil,nil}}}

    4
   / \
  3   5