nodes: 0, module; 1, function_definition; 2, function_name:interval_tree; 3, parameters; 4, block; 5, identifier:intervals; 6, expression_statement; 7, if_statement; 8, expression_statement; 9, expression_statement; 10, expression_statement; 11, expression_statement; 12, for_statement; 13, expression_statement; 14, expression_statement; 15, expression_statement; 16, expression_statement; 17, return_statement; 18, comment:"""Construct an interval tree
  
      :param intervals: list of half-open intervals
                        encoded as value pairs *[left, right)*
      :assumes: intervals are lexicographically ordered
                ``>>> assert intervals == sorted(intervals)``
      :returns: the root of the interval tree
      :complexity: :math:`O(n)`
      """; 19, comparison_operator:intervals == []; 20, block; 21, assignment; 22, assignment; 23, assignment; 24, assignment; 25, identifier:I; 26, identifier:intervals; 27, block; 28, assignment; 29, assignment; 30, assignment; 31, assignment; 32, call; 33, identifier:intervals; 34, list; 35, return_statement; 36, identifier:center; 37, subscript; 38, identifier:L; 39, list; 40, identifier:R; 41, list; 42, identifier:C; 43, list; 44, if_statement; 45, identifier:by_low; 46, call; 47, identifier:by_high; 48, call; 49, identifier:IL; 50, call; 51, identifier:IR; 52, call; 53, identifier:_Node; 54, argument_list; 55, None; 56, subscript; 57, integer:0; 58, comparison_operator:I[1] <= center; 59, block; 60, elif_clause; 61, else_clause; 62, identifier:sorted; 63, generator_expression; 64, identifier:sorted; 65, generator_expression; 66, identifier:interval_tree; 67, argument_list; 68, identifier:interval_tree; 69, argument_list; 70, identifier:center; 71, identifier:by_low; 72, identifier:by_high; 73, identifier:IL; 74, identifier:IR; 75, identifier:intervals; 76, binary_operator:len(intervals) // 2; 77, subscript; 78, identifier:center; 79, expression_statement; 80, comparison_operator:center < I[0]; 81, block; 82, block; 83, tuple; 84, for_in_clause; 85, tuple; 86, for_in_clause; 87, identifier:L; 88, identifier:R; 89, call; 90, integer:2; 91, identifier:I; 92, integer:1; 93, call; 94, identifier:center; 95, subscript; 96, expression_statement; 97, expression_statement; 98, subscript; 99, identifier:I; 100, identifier:I; 101, identifier:C; 102, subscript; 103, identifier:I; 104, identifier:I; 105, identifier:C; 106, identifier:len; 107, argument_list; 108, attribute; 109, argument_list; 110, identifier:I; 111, integer:0; 112, call; 113, call; 114, identifier:I; 115, integer:0; 116, identifier:I; 117, integer:1; 118, identifier:intervals; 119, identifier:L; 120, identifier:append; 121, identifier:I; 122, attribute; 123, argument_list; 124, attribute; 125, argument_list; 126, identifier:R; 127, identifier:append; 128, identifier:I; 129, identifier:C; 130, identifier:append; 131, identifier:I
code: def interval_tree(intervals):
      """Construct an interval tree
  
      :param intervals: list of half-open intervals
                        encoded as value pairs *[left, right)*
      :assumes: intervals are lexicographically ordered
                ``>>> assert intervals == sorted(intervals)``
      :returns: the root of the interval tree
      :complexity: :math:`O(n)`
      """
      if intervals == []:
          return None
      center = intervals[len(intervals) // 2][0]
      L = []
      R = []
      C = []
      for I in intervals:
          if I[1] <= center:
              L.append(I)
          elif center < I[0]:
              R.append(I)
          else:
              C.append(I)
      by_low = sorted((I[0], I) for I in C)
      by_high = sorted((I[1], I) for I in C)
      IL = interval_tree(L)
      IR = interval_tree(R)
      return _Node(center, by_low, by_high, IL, IR)