Data structures and Algorithms: Search Trees

Data structures and Algorithms: Search Trees presents about Binary Search Trees, AVL Trees, Red-Black Trees, Ordered Dictionaries, Performance, AVL Tree Definition, Insertion in an AVL Tree. | Search Trees Data structures and Algorithms Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++ Goodrich, Tamassia and Mount (Wiley, 2004) Outline Binary Search Trees AVL Trees (2,4) Trees Red-Black Trees Trees 2 Binary Search Trees 4 = 1 Trees 8 3 Ordered Dictionaries Keys are assumed to come from a total order. New operations: first(): first entry in the dictionary ordering last(): last entry in the dictionary ordering successors(k): iterator of entries with keys greater than or equal to k; increasing order predecessors(k): iterator of entries with keys less than or equal to k; decreasing order Trees 4 Binary Search Binary search can perform operation find(k) on a dictionary implemented by means of an array-based sequence, sorted by key similar to the high-low game at each step, the number of candidate items is halved terminates after O(log n) steps Example: find(7) 0 1 3 4 5 7 8 1 3 4 5 m l 0 1 1 3 7 14 16 18 19 3 h 8 9 11 14 16 18 19 8 9 11 14 16 18 19 8 9 11 14 16 18 19 h 4 5 7 l 0 11 m l 0 9 m h 4 5 7 l=m .