特殊树_binary tries

special purpose trees

Digital Search Trees [1]

• The left child of a node has the next bit 0 (next MSB or next LSB, depending on implementation)
• The right child of a node has the next bit 1

Binary Tries

Multiway Tries

• Supports search in time proportional to the length of the key
• A naive implementation has R links for each key, so there is a time/space tradeoff here.

R-Trees [3][5]

• Insertion is done in a rectangle that needs the least enlargement (or some other heuristic)

• R* tree topological split [6] gives the best tree for spatial map applications. Here, when a node is full, a portion of the nodes are removed and reinserted. Only one reinsert per level is allowed to prevent an infinite loop of overflows.

Hilbert R-Trees [7]

1. Assign the hilbert value to each rectangle
2. Sort rectangles according to hilbert value
3. Create leaf nodes: Evenly divide rectangles based on hilbert value
4. Create inner nodes: Recursively build the tree from the leaf nodes using the extents of the children. The multiple children of one parent node are chosen using the time-based ordering of creation. The time based ordering is just the current value of an integer counter.

Calculating the distance along a Hilbert SFC [8]

• For all points, find max_x and max_y.
• Find the max of max_x and max_y and call this max_xy.
• If max_xy is a power of two, leave it. Else make it the next higher power of two.
• For each point:
  1. Initialize w to be max_xy / 2. Dist = 0.
  2. Find the quadrant on a hilbert curve that the point is in.
  3. Dist += (quadrant * w * w)
  4. Calculate xnew and ynew according to the formulas
  5. w becomes w / 2
  6. Repeat steps 2 to 5 until w becomes 0

• Quadrant = 3. Dist = 3 * w * w = 3 * 4 * 4
• Apply table: x,y=(3, 3)
• Quadrant = 2. Dist += 2 * w * w = 2 * 2 * 2
• Apply table: x,y=(1, 1)
• Quadrant = 2. Dist += 2 * w * w = 2 * 1 * 1
• Dist = 58

k-d trees [9]

Points in a 2D space:	The data structure in memory:

• Insertion is done like a standard unbalanced binary tree

void insert(Point p, TreeNode * curr, bool is_x){
  if(is_x){
    if(p.x < curr->getX()){
      follow_left_node(!is_x);
    } else {
      follow_right_node(!is_x);
    }
  } else {
    if(p.y < curr->getY()){
      follow_left_node(!is_x);
    } else {
      follow_right_node(!is_x);
    }
  }
}