Allow 1 or 2 keys per node.
Search
Insertion into a 3-node at bottom.
Performance
lg N
. [all 2-nodes]log 3 N ≈ .631 lg N
. [all 3-nodes]Represent 2–3 tree as a BST.
Use “internal” left-leaning links as “glue” for 3–nodes.
1 | private Node rotateLeft(Node h) { |
1 | private void flipColors(Node h) { |
Search for new key.
Insert at bottom.
Split nodes with M key-link pairs on the way up the tree.
Given N horizontal and vertical line segments, find all intersections.
Sweep vertical line from left to right.
The sweep-line algorithm takes time proportional to N log N + R to find all R intersections among N orthogonal line segments.
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 ) :
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;