Week 5 - Balanced Search Trees

1. 2-3 Search Trees

  • Allow 1 or 2 keys per node.
    • 2-node: one key, two children.
    • 3-node: two keys, three children.
  • Search

    • Compare search key against keys in node.
    • Find interval containing search key.
    • Follow associated link (recursively).
  • Insertion into a 3-node at bottom.
    • Add new key to 3-node to create temporary 4-node.
    • Move middle key in 4-node into parent.
    • Repeat up the tree, as necessary.
    • If you reach the root and it's a 4-node, split it into three 2-nodes.
    • all of the possibilities we may do:
  • Performance
    • Tree height.
      • Worst case: lg N. [all 2-nodes]
      • Best case: log 3 N ≈ .631 lg N. [all 3-nodes]
      • Between 12 and 20 for a million nodes.
      • Between 18 and 30 for a billion nodes.

2. Red-black BSTs

  • This course focuses on Left-leaning red-black BSTs.

  • Represent 2–3 tree as a BST.

  • Use "internal" left-leaning links as "glue" for 3–nodes.

2.1. Elementary red-black BST operations

Left rotation & Right rotation

  • Orient a (temporarily) right-leaning red link to lean left/right.

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

Color flip

  • Recolor to split a (temporary) 4-node.

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

Insertion in a LLRB tree

  • Search is the same as for elementary BST (ignore color).

2.2. Balance in LLRB trees

  • Proposition. Height of tree is ≤ 2 lg N in the worst case.
  • Pf.
    • Every path from root to null link has same number of black links.
    • Never two red links in-a-row.

2.3. Summary

3. B-trees

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

3.1. Insertion in a B-tree

  • Search for new key.
  • Insert at bottom.
  • Split nodes with M key-link pairs on the way up the tree.

4. Geometric Applications of BSTs

  • Keys are point on a line.
  • Find/count points in a given 1d interval.
  • Find all keys between lo and hi.
    • Recursively find all keys in left subtree (if any could fall in range).
    • Check key in current node.
    • Recursively find all keys in right subtree (if any could fall in range).

4.2. Orthogonal line segment intersection

  • Given N horizontal and vertical line segments, find all intersections.
  • Sweep vertical line from left to right.
    • x-coordinates define events.
    • h-segment (left endpoint): insert y-coordinate into BST.
    • h-segment (right endpoint): remove y-coordinate from BST.
    • v-segment: range search for interval of y-endpoints.
  • The sweep-line algorithm takes time proportional to N log N + R to find all R intersections among N orthogonal line segments.

    • Put x-coordinates on a PQ (or sort). <-- N log N
    • Insert y-coordinates into BST. <-- N log N
    • Delete y-coordinates from BST. <-- N log N
    • Range searches in BST. <-- N log N + R
      • R: enumerate all of the intersections, after we got the ranges.

4.3. kd trees

  • Keys are point in the plane.
  • Find/count points in a given h-v rectangle

2d tree construction

  • Data structure. BST, but alternate using x- and y-coordinates as key.
    • Search gives rectangle containing point.
    • Insert further subdivides the plane.

Analysis

  • Typical case. R + log N.
  • Worst case (assuming tree is balanced). R + √N.

Higher dimensions

  • Recursively partition k-dimensional space into 2 halfspaces.
  • Implementation. BST, but cycle through dimensions ala 2d trees.

4.4. interval search trees

  • Create BST, where each node stores an interval ( lo, hi ).
  • Use left endpoint as BST key.
  • Store max endpoint in subtree rooted at node.
  • To search for any one interval that intersects query interval ( lo, hi ) :

    • 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.
  • Node x = root; 
    while (x != null) {
        if (x.interval.intersects(lo, hi)) return x.interval;
        else if (x.left == null) x = x.right;
        else if (x.left.max < lo) x = x.right;
        else x = x.left; 
    } 
    return null;
    

4.5. rectangle intersection

  • sweep-line algorithm. Sweep vertical line from left to right.
    • x-coordinates of left and right endpoints define events.
    • Maintain set of rectangles that intersect the sweep line in an interval search tree (using y-intervals of rectangle).
    • Left endpoint: interval search for y-interval of rectangle; insert y-interval.
    • Right endpoint: remove y-interval.

4.6. Applications of BSTs

results matching ""

    No results matching ""