\contentsline {section}{\numberline {1}Introduction: aggregate and potential methods}{1}{}%
\contentsline {subsection}{\numberline {1.1}The problem}{1}{}%
\contentsline {subsection}{\numberline {1.2}Running example: binary counter}{1}{}%
\contentsline {subsubsection}{\numberline {1.2.1}Aggregate method}{1}{}%
\contentsline {subsubsection}{\numberline {1.2.2}Potential method}{2}{}%
\contentsline {section}{\numberline {2}Examples}{3}{}%
\contentsline {subsection}{\numberline {2.1}Stack with multi-pop}{3}{}%
\contentsline {subsection}{\numberline {2.2}Dynamic table (array doubling)}{3}{}%
\contentsline {subsection}{\numberline {2.3}BST in-order traversal via repeated Successor (``Succ-sort'')}{4}{}%
\contentsline {section}{\numberline {3}Heavy examples}{4}{}%
\contentsline {subsection}{\numberline {3.1}Red-Black tree insertion}{4}{}%
\contentsline {subsection}{\numberline {3.2}Splay trees}{6}{}%
\contentsline {subsection}{\numberline {3.3}Scapegoat trees}{8}{}%
\contentsline {subsection}{\numberline {3.4}Move-to-front (MTF) list heuristic}{10}{}%
\contentsline {section}{\numberline {4}Fibonacci heaps}{11}{}%
\contentsline {section}{\numberline {5}Disjoint sets (Union--Find)}{12}{}%
\contentsline {subsection}{\numberline {5.1}Union by rank}{13}{}%
\contentsline {subsection}{\numberline {5.2}Path compression}{13}{}%
\contentsline {subsection}{\numberline {5.3}Example: building and compressing a forest}{13}{}%
\contentsline {subsection}{\numberline {5.4}Combined: union by rank + path compression}{13}{}%