Balanced Search Trees

BalancedSearchTrees

1. 2-3 Search Trees
	1. Allows 1 or 2 keys per node
		1. 2-node: one key two children
		2. 3-node: two keys three children
		3. when search target is between 2 keys in 3-node go middle
		4. Insert into a 3-node at bottom, add new key to 3-node temporarily and move middle key in 4-node into parent, repeat up as necessary
	2. Maintain symmetric order and perfect balance
	3. Worst case lgN, best case ~0.631lgN
	4. search insert deletion O(clgN)
	5. Difficult to implement the original version
2. Red-black BSTs
		1. left-leaning red-black BST
		2. use internal left-leaning links as glue for 3-nodes
		3. red-links glue nodes within a 3-node, black links connect 2-nodes and 3-nodes
		4. Perfect black balance
		5. Red links lean left
		6. Search is the same as the elementary BST (ignore color)
		7. If red links lean right accidentally, it need to be rotate to left
		8. flip colors: turn red colors (both left right links to black, promote a 4-nodes)
		9. Basic operations: left roate, right roate, flip colors
		10. Worst case: search insert delete 2lgN, average case 1lgN
		11. Name from laser printing
3. B-trees
		1. File system model: access data using minimum number of probes
		2. Generalized balanced tree by allowing up to M-1 key-link pairs per node
		3. A search or an insertin in a b-tree of order M with N keys requires between logM-1N and logM/2N probes
		4. Widely used for file systems and databases (SQL)
4. Geometric Applications of BSTs
	1. Intersections among geometric objects
	2. sweep line algorithm: line segment intersection
	3. kd-trees
		1. 2dimensional keys in geometric space
		2. Grid implementation
			1. space-time tradeoff
			2. space M^2+N
			3. Time 1+N/M^2 per square examined on average
			4. rule of thumb : sqrt(N) by sqrt(N) grid
			5. Fast, simple solution for evenly distributed points
		3. Clustering
			1. use a tree to represent a recursive subdivision of 2d space
			2. 2d tree: recursively divide space into two halfplanes
			3. kd tree: recursively partition k-dimentional space into 2 halfplanes
			4. nearest neighbor search
			5. Efficient range search: Typical case R+logN, worst case R+sqrt(N)
			6. Nearest neighbour: typical case logN, worst case N
		4. Flocking Boids
			1. collision avoidance: point away from k nearest boids
			2. flock centering: point towards the center of mass of k nearest boids
			3. velocity matching: update velocity to the average of k nearest boids
			4. kd tree
			5. efficient data structure for k-dimensional data
		5. Interval search
			1. create BST where each node stores an interval (lo,hi), left point as key
			2. store max endpoint in subtree rotted at node
			3. Search
				1. if interval in node intersects query interval, return it
				2. else if left subtree is null, go right
				3. else if max endpoint in left subtree is less than lo, go right
				4. else go left
			4. Use red-black BST to guarantee performance
				1. insert interval logN
				2. find interval logN
				3. delete interval logN
				4. find any one interval that intersects(lo,hi) logN
		6. Rectangle Intersection
			1. microprocessor design
			2. interval search tree using sweeping line
			3. NlogN