.. _BST:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "BST";ODSA.SETTINGS.MODULE_LONG_NAME = "Binary Search Trees";ODSA.SETTINGS.MODULE_CHAPTER = "Binary Trees"; ODSA.SETTINGS.BUILD_DATE = "2020-08-23 13:21:52"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:



.. odsalink:: AV/Binary/BinDiffCON.css

.. odsalink:: AV/Binary/BSTCON.css
.. 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


===================
Binary Search Trees
===================

Binary Search Trees
-------------------
Binary Search Trees
~~~~~~~~~~~~~~~~~~~
   .. inlineav:: BinDiffCON dgm
      :align: center

BST as a Dictionary (1)
~~~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Binary/BST
      :tag: BSTa

BST as a Dictionary (2)
~~~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Binary/BST
      :tag: BSTb

BST ``findhelp``
~~~~~~~~~~~~~~~~
   .. inlineav:: BSTsearchCON ss
      :output: show


BST ``inserthelp``
~~~~~~~~~~~~~~~~~~
   .. inlineav:: BSTinsertCON ss
      :output: show


BST ``deletemax``
~~~~~~~~~~~~~~~~~
   .. inlineav:: BSTdeletemaxCON ss
      :output: show


BST ``removehelp``
~~~~~~~~~~~~~~~~~~
   .. inlineav:: BSTremoveCON ss
      :output: show


.
~
   .


BST Analysis
~~~~~~~~~~~~
   Find: :math:`O(d)`

   Insert: :math:`O(d)`

   Delete: :math:`O(d)`

   :math:`d =` depth of the tree

   :math:`d` is :math:`O(\log n)` if the tree is balanced.

   What is the worst case cost? When?

.. odsascript:: AV/Binary/BinDiffCON.js
.. odsascript:: AV/Binary/BSTsearchCON.js
.. odsascript:: AV/Binary/BSTinsertCON.js
.. odsascript:: AV/Binary/BSTdeletemaxCON.js
.. odsascript:: AV/Binary/BSTremoveCON.js