30.14. Binary Trees Part 3¶

30.14.1. Binary Trees Part 3¶

30.14.1.1. Comparison (1)¶

How do we generalize the concept of comparison?

"<" is not good enough. String < String won't give you what you want.

Need a general way to get the key out of a record

Define a method record.key()?

[Note for C++ users: Operator overloading is effectively the same thing.]

That is not good enough. What if we want to search on different key fields?

30.14.1.2. Comparison (2)¶

Fundamental issue: The key is a property of the context, NOT a property of the record.

30.14.1.3. KVpair¶

This is a truly general way to solve the problem.

// KVPair class definition
public class KVPair implements Comparable {
  Comparable theKey;
  Object theVal;

  KVPair(Comparable k, Object v) {
    theKey = k;
    theVal = v;
  }

  public int compareTo(Object it) throws ClassCastException {
    if (it instanceof KVPair) // Compare two KVPair objects
      return theKey.compareTo(((KVPair)it).key());
    else if (it instanceof Comparable) // Compare against a key value
      return theKey.compareTo(it);
    else
      throw new ClassCastException("Something comparable is expected.");
  }

  public Comparable key() {
    return theKey;
  }

  public Object value() {
    return theVal;
  }

  public String toString() {
    String s = "(";
    if (theKey != null) { s += theKey.toString(); }
    else { s += "null"; }
    s += ", ";
    if (theVal != null) { s += theVal.toString(); }
    else { s += "null"; }
    s += ")";
    return s;
  }
}

// KVPair class definition
class KVPair implements Comparable {
  Comparable theKey;
  Object theVal;

  KVPair(Comparable k, Object v) {
    theKey = k;
    theVal = v;
  }

  int compareTo(Object it) throws ClassCastException {
    if (it instanceof KVPair) // Compare two KVPair objects
      return theKey.compareTo(((KVPair)it).key());
    else if (it instanceof Comparable) // Compare against a key value
      return theKey.compareTo(it);
    else
      throw new ClassCastException("Something comparable is expected.");
  }

  Comparable key() {
    return theKey;
  }

  Object value() {
    return theVal;
  }
}

// KVPair class definition
public class KVPair<K extends Comparable<K>, E> implements Comparable<KVPair<K, E>> {
  K theKey;
  E theVal;

  KVPair(K k, E v) {
    theKey = k;
    theVal = v;
  }

  // Compare KVPairs
  public int compareTo(KVPair<K,E> it) {
    return theKey.compareTo(it.key());
  }

  // Compare against a key
  public int compareTo(K it) {
    return theKey.compareTo(it);
  }

  public K key() {
    return theKey;
  }

  public E value() {
    return theVal;
  }


  public String toString() {
    String s = "(";
    if (theKey != null) { s += theKey.toString(); }
    else { s += "null"; }
    s += ", ";
    if (theVal != null) { s += theVal.toString(); }
    else { s += "null"; }
    s += ")";
    return s;
  }
}

// Container for a key-value pair
class KVPair: public Comparable {
public:
  // Constructors
  KVPair() : k(0), e(nullptr) {}
  KVPair(const KVPair& KV): k(KV.k), e(KV.e) {}
  KVPair& operator=(const KVPair&) = delete;
  KVPair(int kval, void* eval) : k(kval), e(eval) {}

  void print(std::ostream& ostr) const {
    ostr << k;
  }
  bool operator <(const Comparable& other) const { // < operator
    const KVPair& KVother = static_cast<const KVPair&>(other);
    return k < KVother.k;
  }
  bool operator >(const Comparable& other) const { // > operator
    const KVPair& KVother = static_cast<const KVPair&>(other);
    return k > KVother.k;
  }
  bool operator <=(const Comparable& other) const { // <= operator
    const KVPair& KVother = static_cast<const KVPair&>(other);
    return k <= KVother.k;
  }
  bool operator >=(const Comparable& other) const { // >= operator
    const KVPair& KVother = static_cast<const KVPair&>(other);
    return k >= KVother.k;
    }
  KVPair& operator=(const Comparable& i)  {
    auto KV = static_cast<const KVPair&>(i);
    k = KV.k;
    e = KV.e;
    return *this;
  };

  // Data member access functions
  int key() { return k; }
  void setKey(int ink) { k = ink; }
  void* value() { return e; }
  void setValue(void* ine) { e = ine; }
  
private:
  int k;
  void* e;
};

30.14.1.4. .¶

.

30.14.1.5. KVpair: Generics¶

// KVPair class definition
public class KVPair<K extends Comparable<K>, E> implements Comparable<KVPair<K, E>> {
  K theKey;
  E theVal;

  KVPair(K k, E v) {
    theKey = k;
    theVal = v;
  }

  // Compare KVPairs
  public int compareTo(KVPair<K,E> it) {
    return theKey.compareTo(it.key());
  }

  // Compare against a key
  public int compareTo(K it) {
    return theKey.compareTo(it);
  }

  public K key() {
    return theKey;
  }

  public E value() {
    return theVal;
  }


  public String toString() {
    String s = "(";
    if (theKey != null) { s += theKey.toString(); }
    else { s += "null"; }
    s += ", ";
    if (theVal != null) { s += theVal.toString(); }
    else { s += "null"; }
    s += ")";
    return s;
  }
}

30.14.1.6. .¶

.

30.14.1.7. Using the KVpair (1)¶

static <T extends Comparable<T>> void inssort(T[] A) {
  for (int i=1; i<A.length; i++) // Insert i'th record
    for (int j=i; (j>0) && (A[j].compareTo(A[j-1]) < 0); j--)
      swap(A, j, j-1);
}

What is being compared?

What if we want to find the record that has a given key?

30.14.1.8. Binary Tree Implementation (1)¶

"Simple" node model.

A

/
B

C

/
D
/

E
/

F

/
G
/
/
H
/
/
I
/

30.14.1.9. Binary Tree Implementation (2)¶

Internal nodes can be different from leaf nodes.

-

*

c

*

+

4
x

*

a
2
x

30.14.1.10. Inheritance (1)¶

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

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

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

30.14.1.11. Inheritance (2)¶

/** Internal node */
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; }
  boolean isLeaf() { return false; }
  VarBinNode leftchild() { return left; }
  VarBinNode rightchild() { return right; }
  Character value() { return operator; }
}

30.14.1.12. Inheritance (3)¶

1 / 44 Settings
<<<>>>

Preorder traversal begins on pointer-based binary tree.

-
*
c
*
+
4
x
a
*
2
x
rt
-
*
*
4
x
+
*
2
x
a
c

Saving...
Server Error
Resubmit

30.14.1.13. Design Patterns¶

Design patterns capture reusable pieces of design wisdom.

Goals:

Quickly communicate design wisdom to new designers

Give a shared vocabulary to designers

30.14.1.14. Composite (1)¶

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

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

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

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

30.14.1.15. Composite (2)¶

   /** Internal node: Composite */
   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; }
     boolean isLeaf() { return false; }
     VarBinNode leftchild() { return left; }
     VarBinNode rightchild() { return right; }
     Character value() { return operator; }

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

30.14.1.16. Composite (3)¶

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

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

30.14.1.18. 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 overhead.

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

OpenDSA Modules Collection with Slides

Chapter 30 Slides

30.14. Binary Trees Part 3¶

30.14.1. Binary Trees Part 3¶

30.14.1.1. Comparison (1)¶

30.14.1.2. Comparison (2)¶

30.14.1.3. KVpair¶

30.14.1.4. .¶

30.14.1.5. KVpair: Generics¶

30.14.1.6. .¶

30.14.1.7. Using the KVpair (1)¶

30.14.1.8. Binary Tree Implementation (1)¶

30.14.1.9. Binary Tree Implementation (2)¶

30.14.1.10. Inheritance (1)¶

30.14.1.11. Inheritance (2)¶

30.14.1.12. Inheritance (3)¶

30.14.1.13. Design Patterns¶

30.14.1.14. Composite (1)¶

30.14.1.15. Composite (2)¶

30.14.1.16. Composite (3)¶

30.14.1.17. Space Overhead (1)¶

30.14.1.18. Space Overhead (2)¶