.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer

.. slideconf::
   :autoslides: False

===================
Binary Trees Part 3
===================

Binary Trees Part 3
-------------------

.. slide:: Binary Tree Implementation (1)

   "Simple" node model.

   .. inlineav:: BTnullpointerCON dgm
      :links: AV/Binary/BTCON.css AV/Binary/BTnullpointerCON.css
      :scripts: AV/Binary/BTnullpointerCON.js
      :align: center

.. slide:: Binary Tree Implementation (2)

   Internal nodes can be different from leaf nodes.

   .. inlineav:: expressionTreeCON dgm
      :links: AV/Binary/BTCON.css AV/Binary/expressionTreeCON.css
      :scripts: AV/Binary/expressionTreeCON.js
      :align: center


.. slide:: Inheritance (1)

   .. codeinclude:: Binary/ExpressionTree
      :tag: ExpressionTree1


.. slide:: Inheritance (2)

   .. codeinclude:: Binary/ExpressionTree
      :tag: ExpressionTree2


.. slide:: Inheritance (3)

   .. inlineav:: expressionTraversalCON ss
      :long_name: Expression Tree Traversal Slideshow
      :links: AV/Binary/BTCON.css
      :scripts: AV/Binary/expressionTraversalCON.js
      :output: show


.. slide:: Design Patterns

   * Design patterns capture reusable pieces of design wisdom.

   * Goals:
      * Quickly communicate design wisdom to new designers
      * Give a shared vocabulary to designers


.. slide:: Composite (1)

   .. codeinclude:: Binary/ExpressionTreeC
      :tag: Composite1


.. slide:: Composite (2)

   .. codeinclude:: Binary/ExpressionTreeC
      :tag: Composite2

.. slide:: Composite (3)

   .. codeinclude:: Binary/ExpressionTreeC
      :tag: Composite3


.. slide:: 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 :math:`(3p + d)n`
      * Overhead: :math:`3pn`
      * If :math:`p = d`, this means :math:`3p/(3p + d) = 3/4` overhead.


.. slide:: Space Overhead (2)

   Eliminate pointers from the leaf nodes

   .. math::

      \frac{n/2(2p)}{n/2(2p) + dn} = \frac{p}{p + d}

   This is 1/2 if :math:`p = d`.

   :math:`(2p)/(2p + d)` if data only at leaves :math:`\Rightarrow`
   2/3 (of a smaller amount!) overhead.

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