Data Structures with C++ using STL Chapter 12.ppt

1、1,Binary Search tree, red-black tree, and AVL tree Example Hash Function Open probe addressing Chaining with separate lists (2 slide) Hash Iterator Efficiency of Hash Methods Binary Search Trees 2-3-4 Tree (2 slides) Insertion of 2-3-4 tree (4 slides) Red-Black Trees,Chapter 12 Advanced Associative

2、Structures,Converting 2-3-4 tree to Red-Black tree Four Situations in the Splitting of a 4-Node: left child of a BLACK parent P prior to inserting node oriented left-left from G using a single right rotation oriented left-right from G after the color flip Building a Red-Black Tree (2 slides) Red-Bla

3、ck Tree Representation Summary Slide (8 slides),2,Binary Search Tree, Red-Black Tree and AVL Tree Example,3,Example Hash Function,4,Example Hash Function,5,Hash Table Using Open Probe Addressing Example,6,Chaining with Separate Lists Example,7,Hash Iterator hIter Referencing Element 22 in Table ht,8

4、,Efficiency of Hash Methods,9,Two Binary Search Tree Example,Insertion sequence: 5, 15, 20, 3, 9, 7, 12, 17, 6, 75, 100, 18, 25, 35, 40,10,2-3-4 Tree Method,11,2-3-4 Tree Example,12,Example of Insertion of 2-3-4 Tree,13,Another Example of Insertion of 2-3-4 Tree,Insertion Sequence: 2, 15, 12, 4, 8,

5、10, 25, 35, 55, 11, 9, 5, 7,14,Another Example of Insertion of 2-3-4 Tree (Cont),15,Another Example of Insertion of 2-3-4 Tree (Cont),16,Red-Black Trees,17,Converting a 2-3-4 Tree to Red-Black Tree Example,18,Four Situations in the Splitting of a 4-Node,19,Left child of a Black parent P,20,Prior to

6、inserting node 55,21,Oriented left-left from G Using A Single Right Rotation,22,Oriented Left-Right From G After the Color Flip,23,Building A Red-Black Tree,24,Building A Red-Black Tree (Cont),25,rbnode Representation of Red-Black Tree,26,Summary Slide 1,- Hash Table - simulates the fastest searchin

7、g technique, knowing the index of the required value in a vector and array and apply the index to access the value, by applying a hash function that converts the data to an integer - After obtaining an index by dividing the value from the hash function by the table size and taking the remainder, acc

8、ess the table. Normally, the number of elements in the table is much smaller than the number of distinct data values, so collisions occur. - To handle collisions, we must place a value that collides with an existing table element into the table in such a way that we can efficiently access it later.,

9、27,Summary Slide 2,- Hash Table (Cont) - average running time for a search of a hash table is O(1) - the worst case is O(n),28,Summary Slide 3,- Collision Resolution - Two types: 1) linear open probe addressing - the table is a vector or array of static size - After using the hash function to comput

10、e a table index, look up the entry in the table. - If the values match, perform an update if necessary. - If the table entry is empty, insert the value in the table.,29,Summary Slide 4,- Collision Resolution (Cont) - Two types: 1) linear open probe addressing - Otherwise, probe forward circularly, l

11、ooking for a match or an empty table slot. - If the probe returns to the original starting point, the table is full. - you can search table items that hashed to different table locations. - Deleting an item difficult.,30,Summary Slide 5,- Collision Resolution (Cont) 2) chaining with separate lists.

12、- the hash table is a vector of list objects - Each list is a sequence of colliding items. - After applying the hash function to compute the table index, search the list for the data value. - If it is found, update its value; otherwise, insert the value at the back of the list. - you search only ite

13、ms that collided at the same table location,31,Summary Slide 6,- Collision Resolution (Cont) - there is no limitation on the number of values in the table, and deleting an item from the table involves only erasing it from its corresponding list,32,Summary Slide 7,- 2-3-4 tree - a node has either 1 value and 2 children, 2 values and 3 children, or 3 values and 4 children - construction of 2-3-4 trees is comp