4.Binary Tree Implementation (1)§

“Simple” node model.

Binary Tree Implementation (2)

Internal nodes can be different from leaf nodes.

Inheritance (1)

// Base class for expression tree nodes
public interface VarBinNode {
  public boolean isLeaf(); // All subclasses must implement
}

/** Leaf node */
public class VarLeafNode implements VarBinNode {
  private String operand;                 // Operand value

  VarLeafNode(String val) { operand = val; }
  public boolean isLeaf() { return true; }
  public String value() { return operand; }
}

Inheritance (2)

// Internal node
public class VarIntlNode implements VarBinNode {
  private VarBinNode left;                // Left child
  private VarBinNode right;               // Right child
  private Character operator;             // Operator value

  VarIntlNode(Character op, VarBinNode l, VarBinNode r)
    { operator = op; left = l; right = r; }
  public boolean isLeaf() { return false; }
  public VarBinNode leftchild() { return left; }
  public VarBinNode rightchild() { return right; }
  public Character value() { return operator; }
}

Inheritance (3)

Settings

Saving...

Server Error
Resubmit

Design Patterns

Design patterns capture reusable pieces of design wisdom.
Goals:
- Quickly communicate design wisdom to new designers
- Give a shared vocabulary to designers

Composite (1)

   /** Base class: Composite */
   public interface VarBinNode {
     public boolean isLeaf();
     public void traverse();
   }

   /** Leaf node: Composite */
   public class VarLeafNode implements VarBinNode {
     private String operand;                 // Operand value

     VarLeafNode(String val) { operand = val; }
     public boolean isLeaf() { return true; }
     public String value() { return operand; }

     public void traverse() {
       Visit.VisitLeafNode(operand);
     }
   }

Composite (2)

   /** Internal node: Composite */
   public class VarIntlNode implements VarBinNode { // Internal node
     private VarBinNode left;                // Left child
     private VarBinNode right;               // Right child
     private Character operator;             // Operator value

     VarIntlNode(Character op,
                        VarBinNode l, VarBinNode r)
       { operator = op; left = l; right = r; }
     public boolean isLeaf() { return false; }
     public VarBinNode leftchild() { return left; }
     public VarBinNode rightchild() { return right; }
     public Character value() { return operator; }

     public void traverse() {
       Visit.VisitInternalNode(operator);
       if (left != null) { left.traverse(); }
       if (right != null) { right.traverse(); }
     }
   }

Composite (3)

   /** Preorder traversal */
   public static void traverse(VarBinNode rt) {
     if (rt != null) { rt.traverse(); }
   }

Space Overhead (1)

From the Full Binary Tree Theorem:
- Half of the pointers are null.
If leaves store only data, then overhead depends on whether this is full tree.
Ex: Full tree, all nodes the same, with two pointers to children and one to element
- Total space required is \((3p + d)n\)
- Overhead: \(3pn\)
- If \(p = d\), this means \(3p/(3p + d) = 3/4\) overhead.

Space Overhead (2)

Eliminate pointers from the leaf nodes

\[\frac{n/2(2p)}{n/2(2p) + dn} = \frac{p}{p + d}\]

This is 1/2 if \(p = d\).

\((2p)/(2p + d)\) if data only at leaves \(\Rightarrow\) 2/3 (of a smaller amount!) overhead.

Note that some space is needed to distinguish leaves from internal nodes.