.. _Union-Find:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Union-Find";ODSA.SETTINGS.MODULE_LONG_NAME = "Union/FIND";ODSA.SETTINGS.MODULE_CHAPTER = "Week 11"; ODSA.SETTINGS.BUILD_DATE = "2016-11-29 20:59:56"; 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:


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

.. avmetadata::
   :author: Cliff Shaffer


==========
Union/FIND
==========

Union/FIND
----------

Disjoint Sets and Equivalence Classes
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   Sometimes we have a collection of objects that we want to divide
   into separate sets.

   .. odsalink:: AV/General/UFCON.css

   .. inlineav:: UFconcomCON dgm
      :align: left

   .. odsascript:: AV/General/UFconcomCON.js


Approach
~~~~~~~~
   Each object initially is a separate node in its own tree.

   When two objects are "equivalent", then add them to the same tree.

   Key question: **Given two nodes, are they in the same tree?**


Parent Pointer Implementation
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: UFfigCON dgm
      :align: fill

   .. odsascript:: AV/General/UFfigCON.js


Union/FIND
~~~~~~~~~~
   .. codeinclude:: General/ParPtrTree1
      :tag: UF1, UF2


Weighted Union
~~~~~~~~~~~~~~
   A key goal is to keep the depth of nodes as shallow as possible
   (consistent with efficient processing).

   Weighted Union rule:
    * When two trees are union'ed, add one with fewer nodes as a child
      of the root of the tree with more nodes.
    * Depth is :math:`O(\log n)`


Algorithm Visualization
~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: ufCON ss
      :long_name: Union/Find Example
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/General/ufCON.js


.
~
   .


Path Compression
~~~~~~~~~~~~~~~~
   .. inlineav:: pathcompCON ss
      :long_name: Union/Find Path Compression Example
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/General/pathcompCON.js