Discussion 11: Balanced Search Trees, Tries, and Skip Lists Christine Zhou Agenda Announcements Balanced Search Tree Review Problem 1 Tries Review Problem 2 Skip Lists Review Problem 3 Announcements Midterm grades released! You can submit regrades for a week, but we will not be accepting them at all afterwards! Want to vent? Do you have comments/criticisms about the course? tinyurl.com/placetovent Advising sessions are available at tinyurl.com/cs61b-advising Feel free to email me if you would like to schedule a time! Extra project OH Monday 6-8PM in 273/275 Soda Wednesday 6-8PM in 271/273 Soda No office hours on Friday Project milestone due Monday! Project 2 due Thursday! Discussion survey: tinyurl.com/czdisc11 Balanced Search Trees Bushy was better than spindly trees in terms of runtime 2-3-4 Trees! (also called 2-4 Trees) Should still follow the BST property (less on the left, greater on the right) Each node contains 1-3 elements with 2-4 children nodes If we want to insert an element, we’ll traverse and put it in the corresponding leaf node It’s possible that it will have more than 3 elements Split the node, picking either of the middle elements to send up, this can happen recursively Try inserting 7 and 27 into our 2-4 Tree! Red-Black Trees A binary tree that colors nodes red and black Any red nodes are in the same B-Tree node as its parent Constraints: 1. Each node is (conceptually) colored red or black. 2. Root is black. 3. Every leaf node contains no data (null) and is black. This simplifies the algorithms a little bit. 4. Every leaf has same number of black ancestors. 5. Every internal node has two children. 6. Every red node has two black children. Left-Leaning Red Black Trees We can represent nodes with two elements in two ways Let’s just say that we’ll pick the left representation If we are trying to represent a node with two elements, the red node will be “left leaning” 1 Balanced Search Trees a)