Package components.tree

Interface Tree<T>

Type Parameters:
T - type of Tree labels
All Superinterfaces:
Iterable<T>, Standard<Tree<T>>, TreeKernel<T>
All Known Implementing Classes:
Tree1, TreeSecondary
public interface Tree<T> extends TreeKernel<T>
TreeKernel enhanced with secondary methods.
Mathematical Definitions:
HEIGHT(
  t: tree of T
 ): integer satisfies
 if t = empty_tree
  then HEIGHT(t) = 0
  else there exists root: T, children: string of tree of T
        (t = compose(root, children) and
         HEIGHT(t) = 1 + MAX_HEIGHT(children))

MAX_HEIGHT(
  s: string of tree of T
 ): integer satisfies
 if s = empty_string
  then MAX_HEIGHT(s) = 0
  else there exists t: tree of T, rest: string of tree of T
        (s = <t> * rest and
         MAX_HEIGHT(s) = max(HEIGHT(t), MAX_HEIGHT(rest))

  • Method Details

    • root

      T root()
      Reports the root of this.
      Returns:
      the root entry of this
      Aliases:
      reference returned by root
      Requires:
      this /= empty_tree
      Ensures:
      there exists children: string of tree of T
    (this = compose(root, children))

    • replaceRoot

      T replaceRoot(T x)
      Replaces the root of this with x, and returns the old root.
      Parameters:
      x - the new root
      Returns:
      the old root
      Aliases:
      reference x
      Updates:
      this
      Requires:
      this /= empty_tree
      Ensures:
      there exists children: string of tree of T
    (#this = compose(replaceRoot, children)  and
     this = compose(x, children))

    • height

      int height()
      Reports the height of this.
      Returns:
      the height
      Ensures:
      height = HEIGHT(this)

    • addSubtree

      void addSubtree(int pos, Tree<T> st)
      Adds the tree st at position pos in this; the declaration notwithstanding, the dynamic type of st must be the same as the dynamic type of this.
      Parameters:
      pos - the position at which to add st
      st - the Tree to add
      Updates:
      this
      Clears:
      st
      Requires:
      this /= empty_tree  and
0 <= pos <= [number of children of this]
      Ensures:
      this = [#this with subtree #st inserted at position pos]

    • removeSubtree

      Tree<T> removeSubtree(int pos)
      Removes and returns the subtree at position pos in this.
      Parameters:
      pos - the position of the subtree to remove
      Returns:
      the subtree at position pos in this
      Updates:
      this
      Requires:
      this /= empty_tree  and
0 <= pos < [number of children of this]
      Ensures:
      this =
 [#this with subtree at position pos removed and returned as result]

    • numberOfSubtrees

      int numberOfSubtrees()
      Returns the number of subtrees of the root of this.
      Returns:
      the number of subtrees of the root of this
      Requires:
      this /= empty_tree
      Ensures:
      there exists root: T, children: string of tree of T
    (this = compose(root, children)  and
     numberOfSubtrees = |children|)