Discussion 8: LLRB’s, Hashing, Heaps Christine Zhou Administrivia Project 2AB released. ○ ArrayHeapMinPQ due Saturday 3/16 ○ K-D Tree due Saturday 3/23 Lab 8 is out, due Friday 3/15! ○ Labs will likely be released Sundays now. ○ You implement a HashMap! Did you know Challenge Labs are a thing? Discussion survey: tinyurl.com/cz-disc8-sp19 Balanced Search Trees Bushy was better than spindly trees in terms of runtime 2-3 Trees! (also called 2-4 Trees) Should still follow the BST property (less on the left, greater on the right) Each node contains 1-2 elements with 2-3 children nodes If we want to insert an element, traverse down the tree and put it in the corresponding leaf node (we will always add to leaf nodes) It’s possible that it will have more than 2 elements After inserting, split the node by picking the middle element to send up. This can happen recursively Try inserting z into our 2-3 Tree! LLRB Tree Implemented like a BST, but use different colored links to represent 2-3 trees Black link: connects parent 2-3 tree node to child 2-3 tree node (same as regular tree) Red link: “glues” child to parent, child and parent are in the same 2-3 tree node Has one-to-one mapping with 2-3 tree, which means for every LLRB there is a corresponding 2-3 tree! Exercise 1.2 Convert the following tree into a RB tree Problem 1.1/1.2 Problem 1.1/1.2 Exercise 1.1 Draw what the following 2-3 tree left-leaning red black tree would look like after inserting 18, 38, 12, 13, and 20. Problem 1.1/1.2 + 18 What colored links should we use to add? Problem 1.1/1.2 +18 Problem 1.1/1.2 +18 Is this left leaning?