

 This page uses content from Wikipedia. The original article was at AVL tree. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; at no time do they differ by more than one because rebalancing is done ensure this is the case. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. Note the tree of nodes comprise a set, so duplicate node keys are not allowed.

AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications. Similar to red-black trees, AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced; that is, sibling nodes can have hugely differing numbers of descendants.



Task

Implement an AVL tree in the language of choice, and provide at least basic operations.




 
space system
{
 
enum state
{
    header 
    balanced
    left_high
    right_high
}
 
enum direction
{
  from_left
  from_right
}
 
class node
{
    left
    right
    parent
    balance
    data
 
    node()
    {
       left = this
       right = this
       balance = state.header
       parent = null
       data = null
    }
 
    node(root d)
    {
      left = null
      right = null
      parent = root
      balance = state.balanced
      data = d  
    }
 
    is_header
    {
        get
        {
            return balance == state.header
        }
    }
 
    next
    {
        get
        {
            if is_header return left
 
            if !right.null()
            {
                n = right
                while !n.left.null() n = n.left
                return n
             }
             else
             {
                  y = parent
                  if y.is_header return y
 
                  n = this
                  while n == y.right
                  {
                       n = y
                       y = y.parent
                       if y.is_header break
                   }
                   return y
              }
          }
     }
 
 
   previous
   {
       get
       {   
            if is_header return right
 
            if !left.null()
            {
               n = left
               while !n.right.null() n = right
               return n
            }
            else
            {
                y = parent
                if y.is_header return y
 
                n = this
                while n == y.left
                {
                    n = y
                    y = y.parent
                    if y.is_header break
                 }
                 return y
             }
        }
    }
 
    rotate_left()
    {
        _right = right
        _parent = parent
         parent = _right
         _right.parent = _parent
        if !_right.left.null() _right.left.parent = this
        right = _right.left
        _right.left = this
        this = _right
    }
 
    rotate_right()
    {
        _left = left
        _parent = parent
        parent = _left
        _left.parent =  _parent
        if !_left.right.null() _left.right.parent = this
        left = _left.right
        _left.right = this
        this = _left
    }
 
    balance_left()
    {
        select left.balance
        {
            left_high
            {
                balance = state.balanced
                left.balance = state.balanced
                rotate_right()
            }
 
            right_high
            {
                subright = left.right
 
                select subright.balance
                {
                    balanced
                    {
                        balance = state.balanced
                        left.balance = state.balanced
                    }
 
                    right_high
                    {
                        balance = state.balanced
                        left.balance = state.left_high
                    }
 
                    left_high
                    {
                        balance = state.right_high
                        lehpt.balance = state.balanced
                    }
                }
                subright.balance = state.balanced
                left.rotate_left()
                rotate_right()
            }
 
            balanced
            {
                balance = state.left_high
                left.balance = state.right_high
                rotate_right()
            }
        }   
    }
 
    balance_right()
    {
        select right.balance
        {
            right_high
            { 
                balance = state.balanced
                right.balance = state.balanced
                rotate_left()
 
            }
 
           left_high
           {
               subleft = right.left
 
               select subleft.balance
               {
                   balanced
                   {
                       balance = state.balanced
                       right.balance = state.balanced
                   }
 
                   left_high
                   {
                       balance = state.balanced
                       right.balance = state.right_high
                   }
 
                   right_high
                   {
                       balance = state.left_high
                       right.balance = state.balanced
                   }
               }
               subleft.balance = state.balanced
               right.rotate_right()
               rotate_left()
           }
 
           balanced
           {
               balance = state.right_high
               right.balance = state.left_high
               rotate_left()
           }
        }
    }
 
    balance_tree(from)
    {
        taller = true
 
        while taller
        {
            p = parent 
 
            next_from = direction.from_left
            if this != parent.left next_from = direction.from_right
 
            if from == direction.from_left
                select balance
                {
                    left_high
                    {
                        if parent.is_header
                            parent.parent.balance_left()
                        else
                        {
                            if parent.left == this
                                parent.left.balance_left()
                            else
                                parent.right.balance_left()
                            taller = false
                        }
                    }
 
                    balanced
                    {
                        balance = state.left_high
                        taller = true
                    }
 
                    right_high
                    {
                        balance = state.balanced
                        taller = false
                    }
            }
            else
               select balance
               {
                   left_high
                   {
                       balance = state.balanced
                       taller = false
                   }    
 
                   balanced
                   {
                       balance = state.right_high
                       taller = true
                    }
 
                   right_high
                   {
                        if parent.is_header
                            parent.parent.balance_right()
                        else
                        {
                            if parent.left == this
                                parent.left.balance_right()
                            else
                                parent.right.balance_right()
                        }
                        taller = false
                     }
                 }
 
             if taller
             {
 
                 if p.is_header
                   taller = false
                 else
                 {
                     this = p
                     from = next_from
                 }
             }
         }
    }
 
    balance_tree_remove(from)
    {
         shorter = true
 
         while shorter
         {
 
            next_from = direction.from_left
 
           if this != parent.left next_from = direction.from_right
 
            if from == direction.from_left
                select balance
                {
                    left_high
                    {
                        balance = state.balanced
                        shorter = true
                    }
 
 
                    balanced
                    {
                        balance = state.right_high
                        shorter = false
                    }
 
                    right_high
                    {
                        if right.balance == state.right_high
                            shorter = false
                        else
                            shorter = true
 
                        if parent.is_header
                            parent.parent.balance_right()
                        else
                        {
                            if parent.left == this
                                parent.left.balance_right()
                            else
                                parent.right.balance_right()
                       }    
                   }
             }
             else
                select balance
                {
                    right_high
                    {
                        balance = state.balanced
                        shorter = true
                    }
 
 
                    balanced
                    {
                       balance = state.left_high
                       shorter = false
                    }
 
 
                    left_high
                    {
                        if left.balance == state.balanced
                            shorter = false
                        else
                            shorter = true
 
                        if parent.is_header
                            parent.parent.balance_left()
                        else
                        {
                            if parent.is_header
                                parent.left.balance_left()
                            else
                                parent.right.balance_left()
                        }
                   }
            }
 
            if shorter
            {
              if parent.is_header
                  shorter = false
               else
               {
                  this = parent
                  from = next_from
               }
           }
        }
    }
 
    count
    {
        get
        {
            result = +a
 
            if !null()
            {
               cleft = +a
               if !left.null() cleft = left.count
 
               cright = +a
               if !right.null() cright = right.count
 
               result = result + cleft + cright + +b
            }
 
            return result
       }
    }
 
    depth
    {
        get
        {
            result = +a
 
            if !null()
            {
               cleft = +a
               if !left.null() cleft = left.depth
 
               cright = +a
               if !right.null() cright = right.depth
 
               if cleft > cright
                  result = cleft + +b
               else
                  result = cright + +b
            }
 
            return result
       }
    }
}
 
    class default_comparer
    {
      default_comparer() {}
 
      compare_to(a b)
      {
        if a < b return -1
        if b < a return 1
        return 0
      }
    }
 
    class set
    {
        header
        iterator
        comparer
 
        set()
        {
           header = node()
           iterator = null
           comparer = default_comparer()
        }
 
        set(c_set)
        {
           header = node()
           iterator = null
           comparer = c_set
        }
 
 
        left_most
        {
           get
           {
               return header.left
           }
           set
           {
               header.left = value
           }
        }
 
        right_most
        {
           get
           {
               return header.right
           }
           set
           {
               header.right = value
           }
        }
 
       root
       {
           get
           {
                return header.parent
           }
           set
           {
                header.parent = value
           }
        }
 
        empty
        {
            get
            {
                return header.parent.null()
            }
         }
 
        operator<<(data)
        {
            if header.parent.null()
            {
                root = node(header data)
                left_most = root
                right_most = root
            }
            else
            {
                node = root
 
                repeat
                {
                    result = comparer.compare_to(data node.data)
                    if result < 0
                    {
                        if !node.left.null()
                            node = node.left
                        else
                        {
                            new_node = node(node data)
                            node.left = new_node
                            if left_most == node left_most = new_node
                            node.balance_tree(direction.from_left)
                            break
                        }
                   }
                   else if result > 0
                   {
                       if !node.right.null()
                           node = node.right
                       else
                       {
                           new_node = node(node data)
                           node.right = new_node
                           if right_most == node right_most = new_node
                           node.balance_tree(direction.from_right)
                           break
                        }
                    }
                    else // item already exists
                        throw "entry " + (string)data + " already exists"
               }
           }
           return this
       }
 
        update(data)
        {
            if empty
            {
                root = node(header data)
                left_most = root
                right_most = root
            }
            else
            {
                node = root
 
                repeat
                {
                    result = comparer.compare_to(data node.data)
                    if result < 0
                    {
                        if !node.left.null()
                            node = node.left
                        else
                        { 
                            new_node = node(node data)
                            node.left = new_node
                            if left_most == node left_most = new_node
                            node.balance_tree(direction.from_left)
                            break
                        }
                   }
                   else if result > 0
                   {  
                        if !node.right.null()
                            node = node.right
                        else
                        {
                            new_node = node(node data)
                            node.right = new_node
                            if right_most == node right_most = new_node
                            node.balance_tree(direction.from_right)
                            break
                        }
                   }
                   else // item already exists
                   {
                        node.data = data
                        break
                   }
               }
           }
       }
 
        operator>>(data)
        {
             node = root
 
             repeat
             {
                  if node.null()
                  {
                       throw "entry " + (string)data + " not found"
                  }
 
                  result = comparer.compare_to(data node.data)
 
                  if result < 0
                       node = node.left
                  else if result > 0
                       node = node.right
                  else // item found
                  {
                      if !node.left.null() && !node.right.null()
                      {
                         replace = node.left
                         while !replace.right.null() replace = replace.right
                         temp = node.data
                         node.data = replace.data
                         replace.data = temp
                         node = replace
                      }
 
                      from = direction.from_left
                      if node != node.parent.left from = direction.from_right
 
                      if left_most == node
                      {
                          next = node
                          next = next.next
 
                          if header == next
                          {
                              left_most = header
                              right_most = header
                          }
                          else
                              left_most = next
                      }
 
                      if right_most == node
                      {
                          previous = node
                          previous = previous.previous
 
                          if header == previous
                          {
                              left_most = header
                              right_most = header
                          }
                          else
                               right_most = previous
                      }
 
                      if node.left.null()
                      {
                           if node.parent == header
                               root = node.right
                           else
                           {
                               if node.parent.left == node
                                   node.parent.left = node.right
                               else
                                   node.parent.right = node.right
                           }
 
                           if !node.right.null()
                               node.right.parent = node.parent
                      }
                      else
                      {
                          if node.parent == header
                               root = node.left
                           else
                           {
                               if node.parent.left == node
                                   node.parent.left = node.left
                               else
                                   node.parent.right = node.left
                            }
 
                           if !node.left.null()
                                node.left.parent = node.parent
 
                      }
                      node.parent.balance_tree_remove(from)
                      break
                 }
             }
             return this
        }
 
        remove(data)
        {
             node = root
 
             repeat
             {
                  if node.null()
                  {
                       throw "entry " + (string)data + " not found"
                  }
 
                  result = comparer.compare_to(data node.data)
 
                  if result < 0
                       node = node.left
                  else if result > 0
                       node = node.right
                  else // item found
                  {
                      if !node.left.null() && !node.right.null()
                      {
                         replace = node.left
                         while !replace.right.null() replace = replace.right
                         temp = node.data
                         node.data = replace.data
                         replace.data = temp
                         node = replace
                      }
 
                      from = direction.from_left
                      if node != node.parent.left from = direction.from_right
 
                      if left_most == node
                      {
                          next = node
                          next = next.next
 
                          if header == next
                          {
                              left_most = header
                              right_most = header
                          }
                          else
                              left_most = next
                      }
 
                      if right_most == node
                      {
                          previous = node
                          previous = previous.previous
 
                          if header == previous
                          {
                              left_most = header
                              right_most = header
                          }
                          else
                               right_most = previous
                      }
 
                      if node.left.null()
                      {
                           if node.parent == header
                               root = node.right
                           else
                           {
                               if node.parent.left == node
                                   node.parent.left = node.right
                               else
                                   node.parent.right = node.right
                           }
 
                           if !node.right.null()
                               node.right.parent = node.parent
                      }
                      else
                      {
                          if node.parent == header
                               root = node.left
                           else
                           {
                               if node.parent.left == node
                                   node.parent.left = node.left
                               else
                                   node.parent.right = node.left
                            }
 
                           if !node.left.null()
                                node.left.parent = node.parent
 
                      }
                      node.parent.balance_tree_remove(from)
                      break
                 }
             }
             return this
        }
 
        remove2(data)
        {
             node = root
 
             repeat
             {
                  if node.null()
                  {
                       return null
                  }
 
                  result = comparer.compare_to(data node.data)
 
                  if result < 0
                       node = node.left
                  else if result > 0
                       node = node.right
                  else // item found
                  {
                      if !node.left.null() && !node.right.null()
                      {
                         replace = node.left
                         while !replace.right.null() replace = replace.right
                         temp = node.data
                         node.data = replace.data
                         replace.data = temp
                         node = replace
                      }
 
                      from = direction.from_left
                      if node != node.parent.left from = direction.from_right
 
                      if left_most == node
                      {
                          next = node
                          next = next.next
 
                          if header == next
                          {
                              left_most = header
                              right_most = header
                          }
                          else
                              left_most = next
                      }
 
                      if right_most == node
                      {
                          previous = node
                          previous = previous.previous
 
                          if header == previous
                          {
                              left_most = header
                              right_most = header
                          }
                          else
                               right_most = previous
                      }
 
                      if node.left.null()
                      {
                           if node.parent == header
                               root = node.right
                           else
                           {
                               if node.parent.left == node
                                   node.parent.left = node.right
                               else
                                   node.parent.right = node.right
                           }
 
                           if !node.right.null()
                               node.right.parent = node.parent
                      }
                      else
                      {
                          if node.parent == header
                               root = node.left
                           else
                           {
                               if node.parent.left == node
                                   node.parent.left = node.left
                               else
                                   node.parent.right = node.left
                            }
 
                           if !node.left.null()
                                node.left.parent = node.parent
 
                      }
                      node.parent.balance_tree_remove(from)
                      break
                 }
             }
        }
 
 
       operator[data]
       {
           get
           {
               if empty
               {
                   return false
               }
               else
               {
                   node = root
 
                   repeat
                   {
                       result = comparer.compare_to(data node.data)
 
                       if result < 0
                       {
                           if !node.left.null()
                               node = node.left
                           else
                               return false
                       }
                       else if result > 0
                       {
                           if !node.right.null()
                               node = node.right
                           else
                               return false
                       }
                       else // item exists
                           return true
                   }
               }
           }
       }
 
       get(data)
       {
           if empty throw "empty collection"
 
           node = root
 
           repeat
           {
               result = comparer.compare_to(data node.data)
               if result < 0
               {
                  if !node.left.null()
                     node = node.left
                  else
                     throw "item: " + (string)data + " not found in collection"
               }
               else if result > 0
               {
                   if !node.right.null()
                       node = node.right
                    else
                      throw "item: " + (string)data + " not found in collection"
               }
               else // item exists
                   return node.data
            }
        }
 
      last
       {
           get
           {
               if empty
                  throw "empty set"
               else
                  return header.right.data
           }
       }
 
        iterate()
        {
            if iterator.null()
            {
               iterator = left_most
               if iterator == header
                   return iterator(false none())
               else
                   return iterator(true iterator.data) 
            }
            else
            {
               iterator = iterator.next
 
               if iterator == header
                   return  iterator(false none())
               else
                   return iterator(true iterator.data)
            }
        }
 
        count
        {
           get
           {
               return root.count
           }
        }
 
 
        depth
        {
           get
           {
               return root.depth
           }
        }
 
        operator==(compare)
        {
         if this < compare return false
         if compare < this return false
         return true
        }
 
        operator!=(compare)
        {
         if this < compare return true
         if compare < this return true
         return false
        }
 
        operator<(c)
        {
         first1 = begin
         last1 = end
         first2 = c.begin
         last2 = c.end
 
         while first1 != last1 && first2 != last2
         {
            result = comparer.compare_to(first1.data first2.data)
            if result >= 0
            {
                first1 = first1.next
                first2 = first2.next
            }
            else return true
         }
         a = count
         b = c.count
         return a < b
      }
 
      begin { get { return header.left } }
 
      end { get { return header } }
 
      operator string()
      {
          out = "{"
          first1 = begin
          last1 = end
          while first1 != last1 
          {
              out = out + (string)first1.data
              first1 = first1.next
              if first1 != last1 out = out + ","
          }
          out = out + "}"
          return out
      }
 
       operator|(b)
       {
           r = new set()
 
           first1 = begin
           last1 = end
           first2 = b.begin
           last2 = b.end
 
            while first1 != last1 && first2 != last2
            {
                result = comparer.compare_to(first1.data first2.data)
 
                if result < 0
                {
                    r << first1.data
                    first1 = first1.next
                }
 
                else if result > 0
                {
                    r << first2.data
                    first2 = first2.next
                }
 
                else
                {
                    r << first1.data
                    first1 = first1.next
                    first2 = first2.next
                }
            }
 
            while first1 != last1
            {
                r << first1.data
                first1 = first1.next
            }
            while first2 != last2
            {
                r << first2.data
                first2 = first2.next
            }
            return r
       }
 
       operator&(b)
       {
           r = new set()
 
           first1 = begin
           last1 = end
           first2 = b.begin
           last2 = b.end
 
            while first1 != last1 && first2 != last2
            {
                result = comparer.compare_to(first1.data first2.data)
 
                if result < 0
                {
                   first1 = first1.next
                }
 
                else if result > 0
                {
                   first2 = first2.next
                }
 
                else
                {
                   r << first1.data
                   first1 = first1.next
                   first2 = first2.next
                }
            }
 
            return r
       }
 
       operator^(b)
       {
           r = new set()
 
           first1 = begin
           last1 = end
           first2 = b.begin
           last2 = b.end
 
            while first1 != last1 && first2 != last2
            {
                result = comparer.compare_to(first1.data first2.data)
 
                if result < 0
                {
                   r << first1.data
                   first1 = first1.next
                }
 
                else if result > 0
                {
                   r << first2.data
                   first2 = first2.next
                }
 
                else
                {
                   first1 = first1.next
                   first2 = first2.next
                }
            }
 
            while first1 != last1
            {
                r << first1.data
                first1 = first1.next
            }
            while first2 != last2
            {
                r << first2.data
                first2 = first2.next
            }
            return r
       }
 
       operator-(b)
       {
           r = new set()
 
           first1 = begin
           last1 = end
           first2 = b.begin
           last2 = b.end
 
            while first1 != last1 && first2 != last2
            {
                result = comparer.compare_to(first1.data first2.data)
 
                if result < 0
                {
                   r << first1.data
                   first1 = first1.next
                }
 
                else if result > 0
                {
                   r << first2.data
                   first1 = first1.next
                   first2 = first2.next
                }
 
                else
                {
                   first1 = first1.next
                   first2 = first2.next
                }
            }
 
            while first1 != last1
            {
                r << first1.data
                first1 = first1.next
            }
            return r
       }
    }
 
class tree
{
  s
 
  tree()
  {
      s = set()
  }
 
  operator<<(e)
  {
       s << e
       return this
  }
 
  operator[key]
  {
      get
      {
           if empty
               throw "entry not found exception"
           else
           {
               node = s.root
 
               repeat
               {
                   if key < node.data
                   {
                       if !node.left.null()
                           node = node.left
                       else
                           throw "entry not found exception"
                   }
                   else
                   {
                       if key == node.data
                           return node.data
                       else
                       {
                           if !node.right.null()
                               node = node.right
                           else
                               throw "entry not found exception"
                       }
                   }
               }
          }
     }   
  }
 
  operator>>(e)
  {
       entry = this[e]
       s >> entry
  }
 
  remove(key)
  {
      s >> key_value(key)
  }
 
 
  iterate()
  {
      return s.iterate()
   }
 
   count
   {
      get
      {
         return s.count
      }
   }
 
   empty
   {
       get
       {
           return s.empty
       }
   }
 
 
   last
   {
       get
       {
           if empty
              throw "empty tree"
           else
              return s.last
       }
   }
 
    operator string()
    {
       return (string)s
     }
}
 
class dictionary
{
  s
 
    dictionary()
    {
        s = set()
    }
 
    operator<<(key_value)
    {
       s << key_value
       return this
    }
 
    add(key value)
    {
       s << key_value(key value)
    }
 
    operator[key]
    {
       set
       {
           try { s >> key_value(key) } catch {}
           s << key_value(key value)
       }
       get
       {
          r = s.get(key_value(key))
          return r.value
       }
    }
 
    operator>>(key)
    {
        s >> key_value(key)
        return this
    }
 
    iterate()
    {
        return s.iterate()
    }
 
    count
    {
        get
        {
            return s.count
        }  
    }
 
    operator string()
    {
        return (string)s
    }
}
 
class key_value
{
  key
  value
 
  key_value(key_set)
  {
     key = key_set
     value = nul
  }
 
  key_value(key_set  value_set)
  {
     key = key_set
     value = value_set
  }
 
  operator<(kv)
  {
      return key < kv.key
  }
 
  operator string()
  {
    if value.nul()
       return "(" + (string)key + " null)"
    else
       return "(" + (string)key + " " + (string)value  + ")"
  }
}
 
class array
{
  s        // this is a set of key/value pairs.
  iterator // this field holds an iterator for the array.
 
  array()   // no parameters required phor array construction.
  {
   s = set()   // create a set of key/value pairs.
   iterator = null // the iterator is initially set to null.
  }
 
  begin { get { return s.header.left } }   // property: used to commence manual iteration.
 
  end { get { return s.header } } // property: used to define the end item of iteration.
 
  operator<(a) // less than operator is called by the avl tree algorithms
  {             // this operator implies phor instance that you could potentially have sets of arrays.
 
    if keys < a.keys  // compare the key sets first.
       return true
    else if a.keys < keys
       return false
    else               // the key sets are equal  therephore compare array elements.
    {
     first1 = begin
     last1 = end
     first2 = a.begin
     last2 = a.end
 
     while first1 != last1 && first2 != last2
     {
       if first1.data.value < first2.data.value
        return true
       else
       {
         if first2.data.value < first1.data.value
          return false
         else
         {
            first1 = first1.next
            first2 = first2.next
         }
       }
     }
 
     return false
    }
  }
 
    operator==(compare) // equals and not equals derive from operator<
    {
     if this < compare return false
     if compare < this return false
     return true
    }
 
    operator!=(compare)
    {
     if this < compare return true
     if compare < this return true
     return false
    }
 
  operator<<(e) // this operator adds an element to the end of the array.
  {
     try
     {
         this[s.last.key + +b] = e
     }
     catch
     {
         this[+a] = e
     }
     return this
  }
 
 
  operator[key] // this is the array indexer.
  {
       set
       {
           try { s >> key_value(key) } catch {}
           s << key_value(integer(key) value)
       }
       get
       {
          result = s.get(key_value(key))
          return result.value
       }
  }
 
  operator>>(key) // this operator removes an element from the array.
  {
   s >> key_value(key)
   return this
  }
 
 
  iterate() // and this is how to iterate on the array.
  {
      if iterator.null()
      {
         iterator = s.left_most
         if iterator == s.header
             return iterator(false none())
         else
             return iterator(true iterator.data.value)
      }
      else
      {
         iterator = iterator.next
 
         if iterator == s.header
         {
             iterator = null
             return iterator(false none())
         }
         else
             return iterator(true iterator.data.value)
      }
   }
 
   count // this property returns a count of elements in the array.
   {
      get
      {
         return s.count
      }
   }
 
   empty // is the array empty? (Property of course).
   {
       get
       {
           return s.empty
       }
   }
 
 
   last // returns the value of the last element in the array.
   {
       get
       {
           if empty
                 throw "empty array"
           else
               return s.last.value
       }
   }
 
   📟 string() // converts the array to a string
    {
       out = "{"
 
       iterator = s.left_most
       while iterator != s.header
       {
           _value = iterator.data.value
           out = out + (string)_value
           if iterator != s.right_most
              out = out + ","
           iterator = iterator.next
       }
       out = out + "}"
       return out
    }
 
   keys // return the set of keys of the array (a set of integers).
   {
      get
      {
          k = set()
          for e s k << e.key     
          return k
      }
   }
 
   sort // unloads the set into a value and reloads in sorted order.
   {
       get
       {
           sort_bag = bag()
           for e s sort_bag << e.value
           a = new array()
           for g sort_bag a << g
           return a
        }
   }
 
}
 
// and here is a test program
 
using system
space sampleB
{
  sampleB()
  {
    try
    {
       🌳 = { "A" "B" "C" }                     // create a tree
 
       🌳 << "D" << "E"
 
       🎛️ << "Found: " << 🌳["B"] << "\n"
 
       for inst 🌳 🎛️ << inst << "\n"
 
       🎛️ << 🌳 << "\n"
 
       💰 = bag() { 1 1 2 3 }                  // create a bag
 
       🎛️ << 💰 << "\n"
 
       🪣 = ["D" "C" "B" "A"]                   // create an array
 
       🎛️ << 🪣 << "\n"
 
       🎛️ << 🪣.sort << "\n"
 
       🪣[4] = "E"
 
       🎛️ << 🪣 << "\n"
 
       📘 = <[0 "hello"] [1 "world"]>         // create a dictionary
 
       🎛️ << 📘 << "\n"
 
       📘[2] = "goodbye"
 
       🎛️ << 📘 << "\n"
    }    
    catch
    {
      🎛️ << exception << "\n"
    } 
 
  }
 
}
 
// The output of the program is shown below.
 
Found: B
A
B
C
D
E
{A,B,C,D,E}
{1,1,2,3}
{D,C,B,A}
{A,B,C,D}
{D,C,B,A,E}
{(0 hello),(1 world)}
{(0 hello),(1 world),(2 goodbye)}