Data Structures

Professor Abdul-Quader

Lesson 5

Newsfeed

Suppose we are developing a newsfeed app for devices with very small amounts of memory. The app should store links to major news stories as they come in, subject to the following considerations:

  • The app can only store up to a certain number \(N\) of links at a time.
  • When the app is full, as new links come in, old ones get deleted.

Circular Queue

Implementation considerations:

  • Array or linked list?
  • How do we recognize the “front” and “back” of the queue?
  • What happens to the “front” and “back” if we insert into a full queue?
  • How do we recognize if the queue is empty?

Circular Queue Ideas

  • Fixed size? Use an array.
  • Keep track of where to insert (“back”) and remove (“front”).
  • front/back initial values?
  • Recognize if the queue is empty?
  • Recognize if the queue is full?
  • Draw this out on the board (\(N == 5\)).

Video

Circular Queue Overview video:

Implementation

Let’s implement a circular queue together (video shows me using an old-style JUnit in IntelliJ).

GitHub Classrom Space

Tree ADT

A tree is a set of nodes with the following relationships:

  • Every node has an edge (or link) with one parent node
  • There is one, unique root node.

Idea: if our tree is a balanced, binary search tree, we can hope for \(O(\log n)\) for all operations: insertion, removal, lookups. (Compare to a list structure.)

Definitions

  • arity: the maximum number of children a node in a tree has. (This might not be defined on an infinite tree). A tree of arity 2 is called a binary tree.
  • leaf: a node which has no children.
  • path: a path in a tree is a set of nodes \(n_1, n_2, \ldots, n_k\) such that each \(n_i\) is the parent of \(n_{i+1}\). This path has length \(k −1\), because there are \(k − 1\) steps to go from \(n_1\) to \(n_k\).
  • height: the height of a tree is the length of the longest path starting at the root and ending at a leaf.

Picture

Binary tree, from Wikimedia Commons

Search Trees

Idea: a binary search tree has the following property for any node:

  • all data in left subtree is \(\leq\) the data in the node
  • all data in the right subtree are \(\geq\) the data in the node.

This means we can use the “binary search” algorithm on the tree to look for elements.

Video

Implementation

Generic type needs to implement Comparable: see Lesson 1.

public class BinaryTree<T extends Comparable<? super T>>

Nodes

Static inner class:

private static class TreeNode<T> {
    T data;
    TreeNode<T> left;
    TreeNode<T> right;

    TreeNode(T d, TreeNode<T> l, TreeNode<T> r) {
        data = d;
        left = l;
        right = r;
    }
}

Traversals

  • One way to iterate through a list.
  • Many ways to visit a tree.
  • One way: in-order traversal (using recursion)
private void printTree(TreeNode<T> tree) {
    if (tree != null) {
        printTree(tree.left);
        System.out.println(tree.data);
        printTree(tree.right);
    }
}

Exercise

What does this output if the tree contains the following:

Binary search tree

Exercise

What about if we modified the code to use a pre-order traversal:

private void printTree(TreeNode<T> tree) {
    if (tree != null) {
        System.out.println(tree.data);      
        printTree(tree.left);
        printTree(tree.right);
    }
}

Exercise

What would happen if we used a post-order traversal:

private void printTree(TreeNode<T> tree) {
    if (tree != null) {     
        printTree(tree.left);
        printTree(tree.right);
        System.out.println(tree.data);
    }
}

Answers

  • In-order: 1, 3, 4, 6, 7, 8, 10, 13, 14
  • Pre-order: 8, 3, 1, 6, 4, 7, 10, 14, 13
  • Post-order: 1, 4, 7, 6, 3, 13, 14, 10, 8

Video

Insertion

  • Insert / contains / remove: use recursion.
  • Insert: recursively binary search to find the correct place to add new node.
  • If root == null, create a new node with this data item, and make that the new root.
  • If item < root, recursively insert into the root node’s left subtree.
  • Otherwise, recursively insert into the root node’s right subtree.

Video

Code snippet

public void insert(T item) {
    root = insert(root, item);
}

private TreeNode<T> insert(TreeNode<T> subtree, T item) {
    if (subtree == null) {
        return new TreeNode<T>(item, null, null);
    }
    int comparison = item.compareTo(subtree.data);

    if (comparison < 0) {
        subtree.left = insert(subtree.left, item);
    } else if (comparison > 0) {
        subtree.right = insert(subtree.right, item);
    } // if comparison == 0, then it's a duplicate, we ignore it.
      // some tree implementations allow duplicates, then we'd have a decision to make.

    return subtree;
}

Idea

  • Public method that calls private method.
  • Private method handles recursion.
  • Recursive needs to return an updated tree.
  • This will ensure that the root (and its subtrees) gets updated.

Exercise

Implement the contains method. Use a similar paradigm:

  • Recursively binary search for the item.
  • int comparison = item.compareTo(subtree.data);
  • If comparison < 0, check subtree.left for item.
  • If comparison > 0, check subtree.right.
  • If it’s == 0, you found it! Return true!
  • How do you know to return false?
  • Hint: what’s your base case for your recursion?

Removal

You don’t need to submit this, but think about how you might implement the remove method. It’s a bit more involved, so we can talk about it more next time, but try to think it through yourself. Think about the following questions:

  • How do you remove a node if it has no children?
  • How do you remove a node if it has one child?
  • How do you remove a node if it has two children? We have a choice to make, but the idea we will use is to replace the node by its successor (the next largest element in the tree).
// reveal.js plugins