Close
Register
Close Window

OpenDSA Modules Collection with Slides

Chapter 30 Slides

Show Source |    | About   «  30.13. Binary Trees Part 2   ::   Contents   ::   30.15. 2-3+ Trees  »

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

void inssort(Comparable[] 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);
}

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

void inssort(Comparable* A[], int n) { // Insertion Sort
  for (int i = 1; i < n; i++) // Insert i'th record
    for (int j = i; (j > 0) && (*A[j] < *A[j-1]); j--)
      swap(A, j, j-1);
}

def inssort(A):
  for i  in range(len(A)):  # Insert i'th record
    j = i;
    while (j != 0) and (A[j] < A[j-1]):
      swap(A, j, j - 1)
      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.

30.14.1.9. Binary Tree Implementation (2)

Internal nodes can be different from leaf nodes.

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)

Settings

Proficient Saving... Error 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.

   «  30.13. Binary Trees Part 2   ::   Contents   ::   30.15. 2-3+ Trees  »

nsf

© Copyright 2016 by OpenDSA Project Contributors and distributed under an MIT license. Last updated on Apr 01, 2019. Created using Sphinx 1.2.
Close Window