10Data Structures272–327Chapter overviewOverviewAn Introduction to Data Structures272Stack273Queue274linked list275Hash Table287Monotonic Stack288Monotone Queue289Sparse Table290Fenwick Tree297Partition tree309Skip List319K-D Tree324Decomposition Tree325PQ Tree326Finger Trees327Huffman TreeDisjoint Set Union276Disjoint Set Union277Disjoint-Set Union ComplexityHeaps278heap overview279Binary Heap280Pairing Heap281Leftist TreeBlock Data Structures282Block Decomposition283Block Array284Block List285Tree Decomposition286Sqrt TreeSegment Trees291Segment Tree Basics292Segment Tree Merging & Splitting293Li Chao Segment Tree294Cat Tree295Range Extremum Operations & Historical Range Extrema296Kinetic Tournament TreeBinary Search Trees & Balanced Trees298Binary Search Trees & Balanced Trees299Treap300Splay Tree301WBLT302Scapegoat Tree303Cartesian Tree304Size Balanced Tree305AVL tree306Red-Black Tree307Left-Leaning Red-Black Tree308AA treePersistent Data Structures310Introduction to Persistent Data Structures311Persistent Segment Tree312Persistent Balanced Tree313Persistent Trie314Persistent meldable heapTree of Trees315Segment Tree of Segment Trees316Segment Tree of Balanced Trees317Fenwick Tree of Value Segment Trees318Block Decomposition with a Fenwick TreeDynamic Trees320Link-Cut Tree321Global Balanced Binary Tree322Euler Tour Tree323Self-Adjusting Top Tree