Processing math: 100%

DSA Coursenotes

Chapter 4 Week 5

Show Source | | About « 4.1. Project 2 Design :: Contents :: 4.3. Over-Constrained Code »

4.2. Binary Trees Part 3¶

4.2.1. Binary Trees Part 3¶

4.2.1.1. Binary Tree Implementation (1)¶

“Simple” node model.

A

/
B

C

/
D
/

E
/

F

/
G
/
/
H
/
/
I
/

4.2.1.2. Binary Tree Implementation (2)¶

Internal nodes can be different from leaf nodes.

-

*

c

*

+

4
x

*

a
2
x

4.2.1.3. 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; }
}

4.2.1.4. 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; }
}

4.2.1.5. Inheritance (3)¶

1 / 44 Settings
<<<>>>

Preorder traversal begins on pointer-based binary tree.

public static void traverse(VarBinNode rt) {
if (rt == null) { return; } // Nothing to visit
if (rt.isLeaf()) { // Process leaf node
Visit.VisitLeafNode(((VarLeafNode)rt).value());
}
else { // Process internal node
Visit.VisitInternalNode(((VarIntlNode)rt).value());
traverse(((VarIntlNode)rt).leftchild());
traverse(((VarIntlNode)rt).rightchild());
}
}
-
*
c
*
+
4
x
a
*
2
x
rt
-
*
*
4
x
+
*
2
x
a
c

Saving...
Server Error
Resubmit

4.2.1.6. Design Patterns¶

Design patterns capture reusable pieces of design wisdom.

Goals:

Quickly communicate design wisdom to new designers

Give a shared vocabulary to designers

4.2.1.7. 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);
     }
   }

4.2.1.8. 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(); }
     }
   }

4.2.1.9. Composite (3)¶

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

4.2.1.10. 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.

4.2.1.11. 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.

Contact Us || Privacy | | License « 4.1. Project 2 Design :: Contents :: 4.3. Over-Constrained Code »