Given \(N\) rectangles, find all the intersections. This algorithm is very similar to the 1-D line intersection search. The difference...
Suppose we have \(N\) 1-D intervals of the form \((a,b)\) where \(a
This is like the 1-D range search, but where the keys can now have two coordinates. It’s finding the number of points in a rectangle...
Sample problems we want to solve: What are all the keys between two keys? (Relevant to databases) How many keys exist between two keys?...
We introduced 2-3 trees with highly desirable properties. Here we’ll convert them into binary trees while maintaining all the...
Let’s use generating functions to count the average number of leaves in a binary tree with \(N\) internal nodes. Definitions Let \(P\)...
A 2-node is like a regular node in a binary search tree: It has one key and two children. A 3-node has 2 keys and 3 children. The middle...
A binary search tree is a fairly useful structure for storing ordered data. The invariant for a binary search tree is straightforward:...
One way to sort a list is to use the heap data structure. Given an array of \(N\) unsorted elements, build a max heap in place. Start...
At times we want a structure similar to a queue or stack, but instead of LIFO or FIFO, we want it to pop the maximum element each time....