Balanced search trees Balanced search tree. a search-tree data structure for which a height of o(g n)is guaranteed when implementing a dynamic set of n items avl trees 2-3 trees Examples: 2-3-4 trees ●B- trees ●Red- black trees o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.2© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.2 Balanced search trees Balanced search tree: A search-tree data structure for which a height of O(lg n) is guaranteed when implementing a dynamic set of n items. Examples: • AVL trees • 2-3 trees • 2-3-4 trees • B-trees • Red-black trees