-- SORTED_TREE is an efficient data structure for sortable objects.
-- Time complexity for data adding is O(log n).
-- Space complexity is O(n).

indexing

  names: sorted_tree, sorted_collection;
  size: unlimited;
  contents: sortable, comparable;

  author: "Guichard Damien";
  created: 19,January,1996;
  modified: 19,January,1996

deferred class SORTED_TREE inherit SORTABLE
    rename count as nodes
    export {SORTED_TREE} is_less, is_greater
    end
feature{SORTED_TREE}
  left:like Current
  right:like Current
  attach (other:SORTED_TREE) is
    -- Attach 'other' to current ovject.
    do
      if Current.is_less(other) then
        left := other
      else
        right := other
      end
    end  -- attach
feature{ANY}
  add (element:SORTED_TREE) is
    -- Add 'element' to the tree.
    local previous, next:SORTED_TREE
    do
      from  next := Current
      until next = Void
      loop
        previous := next
        if previous.is_less(element) then
          next := previous.left
        else
          next := previous.right
        end
        previous.attach(element)
      end
    ensure
      -- not empty;
      -- nodes = old nodes + 1
    end  -- add
  nodes:INTEGER is
    -- Count nodes.
    do
      Result := 1
      if left /= Void then Result := Result + left.nodes end
      if right /= Void then Result := Result + right.nodes end
    end  -- nodes
  leaves:INTEGER is
    -- Count leaves.
    do
      if left /= Void then Result := Result + left.leaves end
      if right /= Void then
        Result := Result + right.leaves
      elseif left = Void then    -- Both Void, so a leaf
        Result := Result + 1
      end
    end  -- leaves
end  -- class 'SORTED_TREE'