docs/notes/trees.html

<!doctype html>
<html>

<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">

  <title>Trees</title>

  <link rel="stylesheet" href="css/reset.css">
  <link rel="stylesheet" href="css/reveal.css">
  <link id="theme" rel="stylesheet" href="css/theme/black.css">
  <link rel="stylesheet" href="css/style.css">
  <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/font-awesome/4.5.0/css/font-awesome.min.css">

  <!-- Theme used for syntax highlighting of code -->
  <link rel="stylesheet" href="lib/css/monokai.css">
  <script src="js/diagrams.js"></script>

  <!-- Printing and PDF exports -->
  <script>
    var link = document.createElement('link');
    link.rel = 'stylesheet';
    link.type = 'text/css';
    link.href = window.location.search.match(/print-pdf/gi) ? 'css/print/pdf.css' : 'css/print/paper.css';
    document.getElementsByTagName('head')[0].appendChild(link);
  </script>
</head>

<body>
  <div class="reveal">
    <div class="slides">
      <section class="center">
        <h1>Trees</h1>
      </section>
      <section>
        <section class="center">
          <h2>General Trees</h2>
          <h5>Allowing Hierarchical Relationships</h5>
        </section>
        <section>
          <h3>Key Terms</h3>
          <div class="row">
            <canvas id="general-tree" height="1000" width="800" class="column"></canvas>
            <script>
              var canvas = document.getElementById('general-tree')
              var ctx = canvas.getContext('2d');
              ctx.lineWidth = 3;
              ctx.strokeStyle = "red";
              ctx.beginPath();
              // Root node
              ctx.arc(500, 100, 50, 0, 2 * Math.PI);
              // First Row 
              ctx.moveTo(470, 140);
              ctx.arc(350, 250, 50, 3 * Math.PI / 2, 3 * 3 * Math.PI / 2);

              ctx.moveTo(500, 150);
              ctx.arc(500, 250, 50, 3 * Math.PI / 2, 9 * Math.PI / 2);

              ctx.moveTo(530, 140);
              ctx.arc(650, 250, 50, 3 * Math.PI / 2, 9 * Math.PI / 2);

              // Second Row 
              ctx.moveTo(320, 290);
              ctx.arc(200, 400, 50, 3 * Math.PI / 2, 9 * Math.PI / 2);

              ctx.moveTo(350, 300);
              ctx.arc(350, 400, 50, 3 * Math.PI / 2, 9 * Math.PI / 2);

              ctx.moveTo(650, 300);
              ctx.arc(650, 400, 50, 3 * Math.PI / 2, 9 * Math.PI / 2);

              // Third Row
              ctx.moveTo(200, 450);
              ctx.arc(200, 550, 50, 3 * Math.PI / 2, 9 * Math.PI / 2);

              ctx.moveTo(350, 450);
              ctx.arc(350, 550, 50, 3 * Math.PI / 2, 9 * Math.PI / 2);

              ctx.moveTo(620, 440);
              ctx.arc(500, 550, 50, 3 * Math.PI / 2, 9 * Math.PI / 2);

              // Fourth Row
              ctx.moveTo(350, 600);
              ctx.arc(350, 700, 50, 1.5 * Math.PI, 4.5 * Math.PI);

              // Fifth Row
              ctx.moveTo(320, 740);
              ctx.arc(200, 850, 50, 1.5 * Math.PI, 4.5 * Math.PI);

              ctx.moveTo(350, 750);
              ctx.arc(350, 850, 50, 1.5 * Math.PI, 4.5 * Math.PI);

              ctx.moveTo(380, 740);
              ctx.arc(500, 850, 50, 1.5 * Math.PI, 4.5 * Math.PI);

              ctx.stroke();
              ctx.closePath();
            </script>
            <ul>
              <li class="fragment">Parents / Children</li>
              <li class="fragment">Siblings</li>
              <li class="fragment">Root / Subtrees</li>
              <li class="fragment">Paths</li>
              <li class="fragment">Depth / Height</li>
              <li class="fragment">Descendants / Ancestors</li>
              <li class="fragment">Internal Nodes / Leaves</li>
              <li class="fragment">K-ary</li>
              <li class="fragment">Full / Complete / Perfect</li>
            </ul>
            </p>
          </div>
          <aside class="notes">
            Parents / Children are nodes that are above / below eachother
            <br> Siblings are on the same level
            <br> Root is the topmost, subtrees make up a tree
            <br> A path from v0 to vN is a sequence of connected nodes (length = # edges)
            <br> Internal nodes have children, leaves do not
            <br> Descendants are all nodes in the path from v to a leaf
            <br> Ancestors are all nodes in the path from v to the root
            <br> Depth is length of path from root to v
            <br> Height of v is the length of the path from v to deepest descendant
            <br> k-ary: each node has [0, k] children
            <br> full: every node has 0 or k children
            <br> complete: every level is filled except the deepest, which all nodes are as far left as possible
            <br> perfect: every leaf has the same depth and the tree is full
          </aside>
        </section>
        <section>
          <h3>Implementing General Trees</h3>
          <p class="fragment">What should a node contain?</p>
          <ul class="fragment">
            <li>Data</li>
            <li>Parent</li>
            <li>Array of children</li>
          </ul>
        </section>
        <section class="center">
          <h2>Traversals</h2>
          <p>A traversal is a method that <em>visits</em> every node in a tree once.</p>
        </section>
        <section>
          <h3>Preorder Traversals</h3>
          <pre class="fragment">
            <code class="python" data-trim>
              def preorder(p):
                visit(p)
                for child in p.children:
                  preorder(child)
            </code>
          </pre>
        </section>
        <section>
          <h3>Postorder Traversals</h3>
          <pre class="fragment">
            <code class="python" data-trim>
              def postorder(p):
                for child in p.children:
                  postorder(child)
                visit(p)
            </code>
          </pre>
        </section>
        <section>
          <h3>Inorder Traversals</h3>
          <pre class="fragment">
            <code class="python" data-trim>
              def inorder(p):
                for child in p.children[:len(p.children) // 2]:
                  inorder(child)
                visit(p)
                for child in p.children[len(p.children) // 2:]:
                  inorder(child)
            </code>
          </pre>
        </section>
      </section>
      <section>
        <section class="center">
          <h2>Binary Trees</h2>
          <h5>Fixing k = 2</h5>
        </section>
        <section>
          <h3>Implementing Binary Trees</h3>
          <p class="fragment">What is the minimum a node could contain?</p>
          <ul class="fragment">
            <li>Data</li>
            <li>Left Child</li>
            <li>Right Child</li>
          </ul>
        </section>
        <section class="center">
          <h2>Binary Search Trees</h2>
          <h5>Maintaining systematic ordering</h5>
        </section>
        <section>
          <h3>Binary Search Trees</h3>
          <canvas id="bst" width="1000" height="2000"></canvas>
          <script>
            var ctx = document.getElementById('bst').getContext('2d');
            ctx.lineWidth = 3;
            ctx.strokeStyle = "red";
            ctx.fillStyle = "red";
            ctx.font = "1.5em serif"
            ctx.beginPath();
            // Root
            ctx.arc(500, 100, 50, 1.5 * Math.PI, 4.5 * Math.PI);
            ctx.fillText("50", 500 - 30, 100 + 20);

            // First Row
            ctx.moveTo(470, 140);
            ctx.arc(350, 250, 50, 1.5 * Math.PI, 4.5 * Math.PI);
            ctx.fillText("30", 350 - 30, 250 + 20);

            ctx.moveTo(530, 140);
            ctx.arc(650, 250, 50, 1.5 * Math.PI, 4.5 * Math.PI);
            ctx.fillText("70", 650 - 30, 250 + 20);

            // Second Row
            ctx.moveTo(320, 290);
            ctx.arc(250, 400, 50, 1.5 * Math.PI, 4.5 * Math.PI)
            ctx.fillText("20", 250 - 30, 400 + 20);

            ctx.moveTo(380, 290);
            ctx.arc(450, 400, 50, 1.5 * Math.PI, 4.5 * Math.PI)
            ctx.fillText("35", 450 - 30, 400 + 20);

            ctx.moveTo(680, 290);
            ctx.arc(750, 400, 50, 1.5 * Math.PI, 4.5 * Math.PI)
            ctx.fillText("80", 750 - 30, 400 + 20);

            // Third Row
            ctx.moveTo(220, 440);
            ctx.arc(150, 550, 50, 1.5 * Math.PI, 4.5 * Math.PI)
            ctx.fillText("15", 150 - 30, 550 + 20);

            ctx.moveTo(720, 440);
            ctx.arc(650, 550, 50, 1.5 * Math.PI, 4.5 * Math.PI)
            ctx.fillText("75", 650 - 30, 550 + 20);

            ctx.stroke();
            ctx.closePath();
          </script>
          <aside class="notes">Everything in the left subtree is less than the node, right is greater than.</aside>
        </section>
        <section>
          <h3>Binary Search Trees: Search</h3>
          <div class="row">
            <canvas class="column" id="bst-search" width="900" height="2000"></canvas>
            <script>
              var ctx = document.getElementById('bst-search').getContext('2d');
              ctx.lineWidth = 3;
              ctx.strokeStyle = "red";
              ctx.fillStyle = "red";
              ctx.font = "1.5em serif";

              function node(x, y, text = "") {
                ctx.arc(x, y, 50 + text.includes(' ') * 25, 1.5 * Math.PI, 4.5 * Math.PI);
                ctx.fillText(text, x - 30 - text.includes(' ') * 30, y + 20);
                return [x, y]
              }

              function leftChild(x, y, text = "", offset = 100) {
                ctx.moveTo(x - 30, y + 50 - 10);
                x -= offset;
                y += 150;
                return node(x, y, text);
              }

              function rightChild(x, y, text = "", offset = 100) {
                ctx.moveTo(x + 30, y + 50 - 10);
                x += offset;
                y += 150;
                return node(x, y, text);
              }

              ctx.beginPath();
              // Root
              var root = node(500, 100, text = "50")
              var n30 = leftChild(...root, "30", 150);
              var n70 = rightChild(...root, "70", 150);
              var n20 = leftChild(...n30, "20");
              var n40 = rightChild(...n30, "40", 90);
              var n60 = leftChild(...n70, "60", 90);
              var n80 = rightChild(...n70, "80");
              var n15 = leftChild(...n20, "15");
              var n75 = leftChild(...n80, "75");

              ctx.stroke();
              ctx.closePath();
            </script>
            <p class="column">Pseudocode
              <pre class="fragment"><code class="python" style="font-size: .8em" data-trim>
                def search(key):
                  return search(root, key)
                
                def search(node, key):
                  if not node:
                    return False
                  elif node.data == key:
                    return True
                  elif key > node.data:
                    return search(node.right, key)
                  else: # key must be < data
                    return search(node.left, key)
            </code></pre>
            </p>
          </div>
          <aside class="notes">Hint: Recursion would be a great tool for this</aside>
        </section>
        <section>
          <h3>Binary Search Trees: Insert</h3>
          <div class="row">
            <canvas class="column" id="bst-insert" width="900" height="2000"></canvas>
            <script>
              var ctx = document.getElementById('bst-insert').getContext('2d');
              ctx.lineWidth = 3;
              ctx.strokeStyle = "red";
              ctx.fillStyle = "red";
              ctx.font = "1.5em serif"
              ctx.beginPath();
              // Root
              var root = node(500, 100, text = "50")
              var n30 = leftChild(...root, "30", 150);
              var n70 = rightChild(...root, "70", 150);
              var n20 = leftChild(...n30, "20");
              var n40 = rightChild(...n30, "40", 90);
              var n60 = leftChild(...n70, "60", 90);
              var n80 = rightChild(...n70, "80");
              var n15 = leftChild(...n20, "15");
              var n75 = leftChild(...n80, "75");

              ctx.stroke();
              ctx.closePath();
            </script>
            <p class="column">Pseudocode
              <pre class="fragment"><code class="python" style="font-size: .8em" data-trim>
                def insert(key):
                  insert(root, key)
                def insert(node, key):
                  if not node:
                    return Node(key)
                  elif key < node.data:
                    node.left = insert(
                      node.left, data
                    )
                  elif key > node.data:
                    node.right = insert(
                      node.right, data
                    )
                  return node
              </code></pre>
            </p>
          </div>
          <aside class="notes">Hint: Do not insert a node if it is already in the tree!</aside>
        </section>
        <section>
          <h3>Binary Search Trees: Remove</h3>
          <div class="row">
            <canvas class="column" id="bst-remove" width="900" height="2000"></canvas>
            <script>
              var ctx = document.getElementById('bst-remove').getContext('2d');
              ctx.lineWidth = 3;
              ctx.strokeStyle = "red";
              ctx.fillStyle = "red";
              ctx.font = "1.5em serif"
              ctx.beginPath();
              // Root
              var root = node(500, 100, text = "50")
              var n30 = leftChild(...root, "30", 150);
              var n70 = rightChild(...root, "70", 150);
              var n20 = leftChild(...n30, "20");
              var n40 = rightChild(...n30, "40", 90);
              var n60 = leftChild(...n70, "60", 90);
              var n80 = rightChild(...n70, "80");
              var n15 = leftChild(...n20, "15");
              var n75 = leftChild(...n80, "75");

              ctx.stroke();
              ctx.closePath();
            </script>
            <p class="column">What cases must we consider?
              <ol>
                <li class="fragment">Node is a leaf
                </li>
                <li class="fragment">Node has 1 child</li>
                <li class="fragment">Node has 2 children</li>
              </ol>
            </p>
          </div>
          <aside class="notes">
            <ol>
              <li>Node is leaf
                <ol>
                  <li>Set parent's pointer to nullptr</li>
                  <li>Delete the node</li>
                </ol>
              </li>
              <li>Node has 1 child
                <ol>
                  <li>Set parent's pointer to the only child</li>
                  <li>Delete the node</li>
                </ol>
              </li>
              <li>Node has 2 children
                <ol>
                  <li>Find successor / predecessor</li>
                  <li>copy successor's data to node</li>
                  <li>delete successor</li>
                </ol>
              </li>
            </ol>
          </aside>
        </section>
        <section class="center">
          <h2>Analysis</h2>
          <h5>How does it perform?</h5>
        </section>
        <section>
          <h3>Tree Shape is Important!</h3>
          <canvas id="analysis-shape" width="2000" height="800"></canvas>
          <script>
            var ctx = document.getElementById('analysis-shape').getContext('2d');
            ctx.lineWidth = 3;
            ctx.strokeStyle = "red";
            ctx.fillStyle = "red";
            ctx.font = "1.5em serif";

            ctx.beginPath();
            var root = node(500, 400, "20");
            var n10 = leftChild(...root, "10", 150);
            var n30 = rightChild(...root, "30", 150);
            var n5 = leftChild(...n10, "5");
            var n15 = rightChild(...n10, "15", 90);
            var n25 = leftChild(...n30, "25", 90);
            ctx.stroke();
            ctx.closePath();

            ctx.beginPath();
            var root = node(800, 100, "10");
            var n5 = leftChild(...root, "5");
            var n20 = rightChild(...root, '20');
            var n15 = leftChild(...n20, "15");
            var n30 = rightChild(...n20, "30");
            var n25 = leftChild(...n30, "25");
            var n35 = rightChild(...n30, "35");
            ctx.stroke();
            ctx.closePath();

            ctx.beginPath();
            var root = node(1200, 100, "5");
            rightChild(...rightChild(...rightChild(...rightChild(...root, "10"), "15"), "20"), "25");
            ctx.stroke();
            ctx.closePath();
          </script>
          <p class="fragment">Worst Case? Best Case? Average Case?</p>
          <p class="fragment">Average Case: $\approx 1.39 \log n = O(\log n)$</p>
          <aside class="notes">
            Consider search, insert, remove.

            All are O(h) where h is height.

            For the average case, if n distinct keys are inserted at random, expected number of comparisons is 1.39 log
            n.
            Proof = 1-1 correspondence with quicksort partitioning.
          </aside>
        </section>
        <section>
          <h3>Collections as Arrays</h3>
          <table>
            <thead>
              <tr>
                <td>Function</td>
                <td>Unordered List</td>
                <td>Ordered List</td>
                <td>BST</td>
              </tr>
            </thead>
            <tbody>
              <tr>
                <td>Search</td>
                <td>O(n)</td>
                <td>O(log n)</td>
                <td>O(h)</td>
              </tr>
              <tr>
                <td>Insert</td>
                <td>O(n)</td>
                <td>O(n)</td>
                <td>O(h)</td>
              </tr>
              <tr>
                <td>Delete</td>
                <td>O(n)</td>
                <td>O(n)</td>
                <td>O(h)</td>
              </tr>
              <tr>
                <td>Min / Max</td>
                <td>O(n)</td>
                <td>O(1)</td>
                <td>O(h)</td>
              </tr>
              <tr>
                <td>Floor / Ceil</td>
                <td>O(n)</td>
                <td>O(log n)</td>
                <td>O(h)</td>
              </tr>
              <tr>
                <td>Rank</td>
                <td>O(n)</td>
                <td>O(log n)</td>
                <td>O(h)</td>
              </tr>
            </tbody>
          </table>
        </section>
      </section>
      <section>
        <section class="center">
          <h2>Priority Queues</h2>
          <h5>Introducing the Binary Heap</h5>
        </section>
        <section>
          <h3>Priority Queue: API</h3>
          <ul>
            <li>Push: Places an element into the queue</li>
            <li>Pop: Removes and returns the next highest priority item from the queue.</li>
          </ul>
          <p class="fragment">Real-life applications? <span class="fragment">Hospital Lines!</span>
          </p>
          <p class="fragment">Cost to implement with ordered lists? Unordered Lists?</p>
          <p class="fragment">An unordered list: $O(1), O(n)$.<br> Ordered list: $O(n), O(1)$ <br> We can do better.</p>
        </section>
        <section class="center">
          <h3>Priority Queue: Implementation</h3>
          <h5>What if we maintained a somewhat ordered array?</h5>
        </section>
        <section>
          <h3>Binary Heaps</h3>
          <p>Heap-ordered complete binary trees</p>
          <div class="row">
            <div class="column">
              <canvas height="1000" width="1000" id="binaryheap"></canvas>
              <script>
                var ctx = document.getElementById('binaryheap').getContext('2d');
                ctx.lineWidth = 3;
                ctx.strokeStyle = "red";
                ctx.fillStyle = "red";
                ctx.font = "1.5em serif";

                ctx.beginPath();
                var root = node(500, 100, "5");
                var n10 = leftChild(...root, "10", 200);
                var n12 = rightChild(...root, "12", 200);
                var n14 = leftChild(...n10, "14");
                var n15 = rightChild(...n10, "15", 90);
                var n25 = leftChild(...n12, "25", 90);
                var n17 = rightChild(...n12, "17");
                var n20 = leftChild(...n14, "20");
                var n50 = rightChild(...n14, "50");
                ctx.stroke();
                ctx.closePath();
              </script>
            </div>
            <div class="column">
              <ul>
                <li class="fragment">Heap Ordered</li>
                <li class="fragment">Array Representation</li>
                <li class="fragment">Push</li>
                <li class="fragment">Swimming Up</li>
                <li class="fragment">Pop</li>
                <li class="fragment">Sinking Down</li>
              </ul>
            </div>
          </div>
          <aside class="notes">
            <ul>
              <li>Heap Ordered: Parent's key is no greater than children's</li>
              <li>Push: Insert at the end, then swim up.</li>
              <li>Swimming Up: While the parent node is less, swap them.</li>
              <li>Overall, insertion costs 1 + log n comparisons</li>
              <li>Pop: Exchange root with node at end, then sink it down.</li>
              <li>Sinking Down: Exchange the data with the smaller of the two children. (Why smaller?)</li>
              <li>Removing the max takes at most 2 log n comparisons</li>
              <li>Array Representation: Indices start at 1, nodes are in level order, no explicit links are needed!</li>
              <li>Parents of item k are at k//2, children are 2k and 2k + 1</li>
            </ul>
          </aside>
        </section>
        <section>
          <h3>Binary Heap: Further Considerations</h3>
          <ul>
            <li class="fragment">Underflow: Throw an exception</li>
            <li class="fragment">Overflow: Use a dynamic array</li>
            <li class="fragment">Max-Oriented: Swap the comparisons</li>
            <li class="fragment">Remove: Remove an arbitrary item.</li>
            <li class="fragment">Change Priority of an Item</li>
            <li class="fragment">Immutability of Keys: Client should not be able to change the keys in the array.</li>
          </ul>
          <aside class="notes">Immutability: cannot change the data value once created. Should always try and make
            everything immutable.</aside>
        </section>
        <section>
          <h3>Priority Queue: Costs Summary</h3>
          <table>
            <thead>
              <tr>
                <td>Implementation</td>
                <td>Push</td>
                <td>Pop</td>
                <td>Peek</td>
              </tr>
            </thead>
            <tbody>
              <tr>
                <td>Unordered Array</td>
                <td>1</td>
                <td>n</td>
                <td>n</td>
              </tr>
              <tr>
                <td>Ordered Array</td>
                <td>n</td>
                <td>1</td>
                <td>1</td>
              </tr>
              <tr>
                <td>Binary Heap</td>
                <td>log n</td>
                <td>log n</td>
                <td>1</td>
              </tr>
              <tr>
                <td>d-ary Heap</td>
                <td>$\log_d n$</td>
                <td>$\log_d n$</td>
                <td>1</td>
              </tr>
              <tr>
                <td>Fibonacci</td>
                <td>1</td>
                <td>log n</td>
                <td>1</td>
              </tr>
              <tr>
                <td>Brodal Queue</td>
                <td>1</td>
                <td>log n</td>
                <td>1</td>
              </tr>
              <tr>
                <td>Impossible</td>
                <td>1</td>
                <td>1</td>
                <td>1</td>
              </tr>
            </tbody>
          </table>
          <aside class="notes">
            Assume there is a priority queue that makes constant compares for both push and pop.
            Design a sorting algorithm that uses this queue.
            You've just violated O(n * log n) (see max of three)

            Sweet spot for d is 4-way
          </aside>
        </section>
      </section>
      <section>
        <section class="center">
          <h2>Balanced Search Trees</h2>
          <h5>Guaranteeing $\log n$ performance</h5>
        </section>
        <section>
          <h3>2-3 Trees</h3>
          <ul>
            <li>2-node: one key, two children</li>
            <li>3-node: two keys, three children</li>
          </ul>
          <p>This scheme achieves perfect balance, every path from root to null has same length.</p>
          <canvas id="23-intro" width="2000" height="1000"></canvas>
          <script>
            var ctx = document.getElementById('23-intro').getContext('2d');
            ctx.lineWidth = 3;
            ctx.strokeStyle = "red";
            ctx.fillStyle = "red";
            ctx.font = "1.5em serif";

            ctx.beginPath();
            var root = node(1000, 100, "15");
            var n5_10 = leftChild(...root, "5 10");

            ctx.stroke();
            ctx.closePath();
          </script>
        </section>
      </section>
    </div>
  </div>

  <script src="js/reveal.js"></script>

  <script>
    Reveal.initialize({
      dependencies: [{
          src: 'plugin/markdown/marked.js'
        },
        {
          src: 'plugin/markdown/markdown.js'
        },
        {
          src: 'plugin/notes/notes.js',
          async: true
        },
        {
          src: 'plugin/highlight/highlight.js',
          async: true
        },
        {
          src: 'plugin/math/math.js',
          async: true
        },
        {
          src: 'plugin/menu/menu.js',
          async: true
        },
        {
          src: 'plugin/chalkboard/chalkboard.js',
          async: true
        }
      ],
      hash: true,
      center: false,
      fragmentInURL: true,
      keyboard: {
        // toggle notes canvas when 'c' is pressed
        67: function () {
          RevealChalkboard.toggleNotesCanvas()
        },
        // toggle chalkboard when 'b' is pressed
        66: function () {
          RevealChalkboard.toggleChalkboard()
        },
        // clear chalkboard when 'DEL' is pressed
        46: function () {
          RevealChalkboard.clear()
        },
        // reset chalkboard data on current slide when 'BACKSPACE' is pressed
        8: function () {
          RevealChalkboard.reset()
        },
        // downlad recorded chalkboard drawing when 'd' is pressed
        68: function () {
          RevealChalkboard.download()
        },
      },
      chalkboard: {
        toggleChalkboardButton: {
          left: "80px"
        },
        toggleNotesButton: {
          left: "130px"
        },
        color: ['rgba(255, 255, 255, 1)', 'rgba(255, 255, 255, 1)']
      },
      menu: {
        titleSelector: 'h2',
        hideMissingTitles: true,
      }
    });
  </script>
</body>

</html>