2017-01-28

# balanced search trees

Allow 1 or 2 keys per node

• 2-node: one key, two children
• 3-node: two keys, three children

Perfect balance: every path from root to null link has same length.
Symmetric order: Inorder traversal yields keys in ascending order

If has a temp 4-node, move the middle key above.
2-node can be converted to 3-node.

Maintains symetric order and perfect balance.

Direct implementation is complicated

## red-black BSTs

Use “internal” left-leaning as “glue” for 3-nodes.

• no node has two red links connected to it
• every path from root to null link has the same number of black links

Search is the same as for elementary BST (ignore color)
Most of other ops like ceiling, selection are also identical

Encode the color of links in nodes (the link pointing to their parent)

private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node
{
Key key;
Value val;
Node left, right;
boolean color; // color of parent link
}
private boolean isRed(Node x)
{
if (x == null) return false;
return x.color == RED;
}


rotate left: right child red, left child black

private Node rotateLeft(Node h)
{
assert isRed(h.right);
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}


rotate right: left child, left-left gradchild red

private Node rotateLeft(Node h)
{
assert isRed(h.right);
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}


flip color (while one parent node has two red son links)

private void flipColors(Node h)
{
assert !isRed(h);
assert isRed(h.left);
assert isRed(h.right);
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}


### insertion

private Node put(Node h, Key key, Value val)
{
if (h == null) return new Node(key, val, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else if (cmp == 0) h.val = val;
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
return h;
}


Height of tree is $\le 2 \lg N$ in the worst case

## B-trees

Generalize 2-3 trees by allowing up to M-1 key-link pairs per node.

# Geometric applications of BSTs

extension of ordered symbol table

• insert key-value pair
• search for key k
• delete key k
• range search: find all keys between k1 and k2
• range count: number of keys between k1 and k2

Geometric interpretation

• keys are points on a line
• find and count points in given 1-d interval

## line segment intersection

sweep line algorithm, horizontally.

• put x-coordinates on a PQ (or sort)
• insert y-coordinates into BST
• delete y-coordinates from BST
• range searches in BST

## Kd-tree

extension of ordered symbol-table to 2d keys

• insert a 2d key
• delete a 2d key
• search for a 2d key
• range search: find all keys that lie in a 2d range
• range count: number of keys that lie in a 2d range

recursively partition plane into two halfplanes

### kd-tree

works for k dimensions

## interval search trees

Data are intervals.

Find all intervals in data structure that intersects a given interval.

use lo as the key
store max endpoint in subtree rooted at node

• if interval in node intersects query interval, return it
• else if left subtree is null, go right
• else if max endpoint in left subtree is less than lo, go right
• else go left

sweep line