Unit 4

Segment Tree

• Datastructure used on Arrays to perform range queries faster
• tree has a range from low to high and the node has value of the sum of the complete tree
• leaf nodes are the array elements
• as we go up, the internal nodes represent the sum of their 2 children
• This continues till the root
• Space complexity -> O(n)
• Updation Time Complexity -> O(n)
• Sum query(O(log(n)) )
• No overlap - The node range is outside the query range. Thus, you’re looking at a useless node here. Nothing to do, move on.
  • low > end || high < start
• Total overlap - The node range is entirely inside the query range. This is a completely valid node and a very useful one. Return the value in this node.
  • low <= start and end <= high
• Partial overlap - A part of this node range belongs the query range, therefore recurse on both children until there is “no overlap” or “total overlap”.
• If the
  size of the input array n
  
  is a power of 2,
  then the size of the segment tree is 2n-1, where number of leaf nodes is n and number of internal nodes is n-1
• If size of array is
  not a power of 2
  , approximately, 2k-1 nodes are required, where k is the smallest power of 2 greater than n!
  • if n = 5, smallest power of 2 greater than n = k = 2^3 i.e. 8
  • Thus, size of tree = 2*k-1 = 2*8-1 = 15
• Time Complexity
  • To Build -> O(n)
  • To search -> O(n)
• sum(l,r) = sum\[l-1] - sum\[r]

Priority Search Trees

• Let S be set of Points
  1. If S is empty return NULL
  2. Find point P (such that it has highest value for Y coordinate) from S and set P as the root
  3. Find S-P(remove P from S)
  4. If S-P is empty, return P
  5. Find X(P) such that
     x divides the points in S-P
     into two equal halves(sets) on
     x coordinate
     
     • To find median, take the middle 2 elements of the current recursion array you have and do a divide by 2 operation on the x elements of them
  6. Recursively apply above steps on left and right half and set the generated trees as left anyd right half of P

Interval Tree
- similar to BST insertion but when you insert the node, you travel back to the root, and replace the the current elements y(interval end) with whatever is higher, the inserted value's y or the current element's y - Interval Tree demonstration

Node x = root
while(x != NULL){
    if(x.interval.intersects(low, high))
        return x.interval
    else if(x.left == NULL || x.left.high < low)
        x = x.right
    else
        x = x.left
}

- Complexity - O(log N) -> Insertion, search, delete - Creating with N nodes -> O(N log N)

KD Tree

• Alternating levels of coordinates based on the number of values in the set to be inserted
• split the points and assign left/right child based on the current level of the tree you are at
• k-dimensional tree, where the dimension on which nodes are sent left, right depends on the dimension number which is level of the tree

• Idea: Each level of the tree compares against 1 dimension.

  insert(Point x, KDNode t, int cd) {
  **<br/>if**<br/> t == **<br/>null**<br/>
  t = **<br/>new**<br/> KDNode(x)
  **<br/>else**<br/> **<br/>if**<br/> (x == t.data)
  // error! duplicate
  **<br/>else**<br/> **<br/>if**<br/> (x[cd] < t.data[cd])
  t.left = insert(x, t.left, (cd+1) % DIM)
  ##### else
  t.right = insert(x, t.right, (cd+1) % DIM)
  ##### return t
  }
  

• 
  Finding Min
  

  findMin(Node* tree, int targetDimension, int currentDimension){
      if(T == NULL)
          return INT_MAX;
  
      if(currentDimension == targetDimension)// the min cannot be on the right at this case
          if(t->left)
              return findMin(tree->left,targetDimension,(currentDimension+1)%k)
          else
              return t->data
  
      return min(t->data[targetDimension],
      findMin(tree->left,targetDimension,(currentDimension+1)%k)[targetDimension],
      findMin(tree->right,targetDimension,(currentDimension+1)%k)[targetDimension]);
  }
  

• 
  Deletion
  

  //dp -> deletePoint
  Node* delete(Node* node, int dp[], int cd){
      if(!node)
          return NULL;
      int nd = (cd+1)%k; //next dimension
      if(dp == node->data){
          if(node->right != NULL){
              node->data = findMin(node->right, cd, nd);
              node->right = delete(node->right, node->data, nd);
          }else if(node->left != NULL){
              node->data = findMin(node->left, cd, nd)
              node->right = delete(node->left, node->data,nd)
          }else // leaf node
              return NULL;                
      }else if(dp[cd] < node->data[cd])
          delete(Node->left, dp, nd)
      else
          delete(Node->right, dp, nd)
  
      return node; // if deletion element not found, return node as the root as it is
  }
  

• Nearest neighbour search

  - Complexity O(\(2^d + log(n)\))