Tries and String Matching Slides 2009 (Small09) 计算机科学

Tries and String MatchingWhere We've Been● Fundamental Data Structures ● Red/black trees, B-trees, RMQ, etc.● Isometries ● Red/black trees ≡ 2-3-4 trees, binomialheaps ≡ binary numbers, etc.● Amortized Analysis ● Aggregate, banker's, and potential methods.Where We're Going● String Data Structures ● Data structures for storing and manipulatingtext.● Randomized Data Structures ● Using randomness as a building block.● Integer Data Structures ● Breaking the Ω(n log n) sorting barrier.● Dynamic Conne