class_docstr: Robust random cut tree data structure as described in:
  
  S. Guha, N. Mishra, G. Roy, & O. Schrijvers. Robust random cut forest based anomaly
  detection on streams, in Proceedings of the 33rd International conference on machine
  learning, New York, NY, 2016 (pp. 2712-2721).
  
  Parameters:
  -----------
  X: np.ndarray (n x d) (optional)
     Array containing n data points, each with dimension d.
     If no data provided, an empty tree is created.
  index_labels: sequence of length n (optional) (default=None)
                Labels for data points provided in X.
                Defaults to [0, 1, ... n-1].
  precision: float (optional) (default=9)
             Floating-point precision for distinguishing duplicate points.
  random_state: int, RandomState instance or None (optional) (default=None)
      If int, random_state is the seed used by the random number generator;
      If RandomState instance, random_state is the random number generator;
      If None, the random number generator is the RandomState instance used by np.random.
  
  Attributes:
  -----------
  root: Branch or Leaf instance
        Pointer to root of tree.
  leaves: dict
          Dict containing pointers to all leaves in tree.
  ndim: int
        dimension of points in the tree
  
  Methods:
  --------
  insert_point: inserts a new point into the tree.
  forget_point: removes a point from the tree.
  disp: compute displacement associated with the removal of a leaf.
  codisp: compute collusive displacement associated with the removal of a leaf
          (anomaly score).
  map_leaves: traverses all nodes in the tree and executes a user-specified
              function on the leaves.
  map_branches: traverses all nodes in the tree and executes a user-specified
                function on the branches.
  query: finds nearest point in tree.
  get_bbox: find bounding box of points under a given node.
  find_duplicate: finds duplicate points in the tree.
  
  Example:
  --------
  # Create RCTree
  >>> X = np.random.randn(100,2)
  >>> tree = RCTree(X)
  
  # Insert a point
  >>> x = np.random.randn(2)
  >>> tree.insert_point(x, index=100)
  
  # Compute collusive displacement of new point (anomaly score)
  >>> tree.codisp(100)
  
  # Remove point
  >>> tree.forget_point(100)
class_docstr_tok: ["Robust","random","cut","tree","data","structure","as","described","in",":","S.","Guha",",","N.","Mishra",",","G.","Roy",",","&","O.","Schrijvers",".","Robust","random","cut","forest","based","anomaly","detection","on","streams",",","in","Proceedings","of","the","33rd","International","conference","on","machine","learning",",","New","York",",","NY",",","2016","(","pp",".","2712-2721",")",".","Parameters",":","--","--","--","--","--","-","X",":","np.ndarray","(","n","x","d",")","(","optional",")","Array","containing","n","data","points",",","each","with","dimension","d.","If","no","data","provided",",","an","empty","tree","is","created",".","index_labels",":","sequence","of","length","n","(","optional",")","(","default=None",")","Labels","for","data","points","provided","in","X.","Defaults","to","[","0",",","1",",","...","n-1","]",".","precision",":","float","(","optional",")","(","default=9",")","Floating-point","precision","for","distinguishing","duplicate","points",".","random_state",":","int",",","RandomState","instance","or","None","(","optional",")","(","default=None",")","If","int",",","random_state","is","the","seed","used","by","the","random","number","generator",";","If","RandomState","instance",",","random_state","is","the","random","number","generator",";","If","None",",","the","random","number","generator","is","the","RandomState","instance","used","by","np.random",".","Attributes",":","--","--","--","--","--","-","root",":","Branch","or","Leaf","instance","Pointer","to","root","of","tree",".","leaves",":","dict","Dict","containing","pointers","to","all","leaves","in","tree",".","ndim",":","int","dimension","of","points","in","the","tree","Methods",":","--","--","--","--","insert_point",":","inserts","a","new","point","into","the","tree",".","forget_point",":","removes","a","point","from","the","tree",".","disp",":","compute","displacement","associated","with","the","removal","of","a","leaf",".","codisp",":","compute","collusive","displacement","associated","with","the","removal","of","a","leaf","(","anomaly","score",")",".","map_leaves",":","traverses","all","nodes","in","the","tree","and","executes","a","user-specified","function","on","the","leaves",".","map_branches",":","traverses","all","nodes","in","the","tree","and","executes","a","user-specified","function","on","the","branches",".","query",":","finds","nearest","point","in","tree",".","get_bbox",":","find","bounding","box","of","points","under","a","given","node",".","find_duplicate",":","finds","duplicate","points","in","the","tree",".","Example",":","--","--","--","--","#","Create","RCTree",">",">",">","X","=","np.random.randn","(","100,2",")",">",">",">","tree","=","RCTree","(","X",")","#","Insert","a","point",">",">",">","x","=","np.random.randn","(","2",")",">",">",">","tree.insert_point","(","x",",","index=100",")","#","Compute","collusive","displacement","of","new","point","(","anomaly","score",")",">",">",">","tree.codisp","(","100",")","#","Remove","point",">",">",">","tree.forget_point","(","100",")"]
docstr: Inserts a point into the tree, creating a new leaf
  
  Parameters:
  -----------
  point: np.ndarray (1 x d)
  index: (Hashable type)
         Identifier for new leaf in tree
  tolerance: float
             Tolerance for determining duplicate points
  
  Returns:
  --------
  leaf: Leaf
        New leaf in tree
  
  Example:
  --------
  # Create RCTree
  >>> tree = RCTree()
  
  # Insert a point
  >>> x = np.random.randn(2)
  >>> tree.insert_point(x, index=0)
docstr_tok: ["Inserts","a","point","into","the","tree",",","creating","a","new","leaf","Parameters",":","--","--","--","--","--","-","point",":","np.ndarray","(","1","x","d",")","index",":","(","Hashable","type",")","Identifier","for","new","leaf","in","tree","tolerance",":","float","Tolerance","for","determining","duplicate","points","Returns",":","--","--","--","--","leaf",":","Leaf","New","leaf","in","tree","Example",":","--","--","--","--","#","Create","RCTree",">",">",">","tree","=","RCTree","(",")","#","Insert","a","point",">",">",">","x","=","np.random.randn","(","2",")",">",">",">","tree.insert_point","(","x",",","index=0",")"]
code: def insert_point(self, point, index, tolerance=None):
      """
      Inserts a point into the tree, creating a new leaf
  
      Parameters:
      -----------
      point: np.ndarray (1 x d)
      index: (Hashable type)
             Identifier for new leaf in tree
      tolerance: float
                 Tolerance for determining duplicate points
  
      Returns:
      --------
      leaf: Leaf
            New leaf in tree
  
      Example:
      --------
      # Create RCTree
      >>> tree = RCTree()
  
      # Insert a point
      >>> x = np.random.randn(2)
      >>> tree.insert_point(x, index=0)
      """
      if not isinstance(point, np.ndarray):
          point = np.asarray(point)
      point = point.ravel()
      if self.root is None:
          leaf = Leaf(x=point, i=index, d=0)
          self.root = leaf
          self.ndim = point.size
          self.leaves[index] = leaf
          return leaf
      # If leaves already exist in tree, check dimensions of point
      try:
          assert point.size == self.ndim
      except ValueError:
          raise ValueError(
              "Point must be same dimension as existing points in tree."
          )
      # Check for existing index in leaves dict
      try:
          assert index not in self.leaves
      except KeyError:
          raise KeyError("Index already exists in leaves dict.")
      # Check for duplicate points
      duplicate = self.find_duplicate(point, tolerance=tolerance)
      if duplicate:
          self._update_leaf_count_upwards(duplicate, inc=1)
          self.leaves[index] = duplicate
          return duplicate
      # If tree has points and point is not a duplicate, continue with main algorithm...
      node = self.root
      parent = node.u
      maxdepth = max([leaf.d for leaf in self.leaves.values()])
      depth = 0
      branch = None
      for _ in range(maxdepth + 1):
          bbox = node.b
          cut_dimension, cut = self._insert_point_cut(point, bbox)
          if cut <= bbox[0, cut_dimension]:
              leaf = Leaf(x=point, i=index, d=depth)
              branch = Branch(
                  q=cut_dimension,
                  p=cut,
                  l=leaf,
                  r=node,
                  n=(leaf.n + node.n),
              )
              break
          elif cut >= bbox[-1, cut_dimension]:
              leaf = Leaf(x=point, i=index, d=depth)
              branch = Branch(
                  q=cut_dimension,
                  p=cut,
                  l=node,
                  r=leaf,
                  n=(leaf.n + node.n),
              )
              break
          else:
              depth += 1
              if point[node.q] <= node.p:
                  parent = node
                  node = node.l
                  side = "l"
              else:
                  parent = node
                  node = node.r
                  side = "r"
      try:
          assert branch is not None
      except:
          raise AssertionError(
              "Error with program logic: a cut was not found."
          )
      # Set parent of new leaf and old branch
      node.u = branch
      leaf.u = branch
      # Set parent of new branch
      branch.u = parent
      if parent is not None:
          # Set child of parent to new branch
          setattr(parent, side, branch)
      else:
          # If a new root was created, assign the attribute
          self.root = branch
      # Increment depths below branch
      self.map_leaves(branch, op=self._increment_depth, inc=1)
      # Increment leaf count above branch
      self._update_leaf_count_upwards(parent, inc=1)
      # Update bounding boxes
      self._tighten_bbox_upwards(branch)
      # Add leaf to leaves dict
      self.leaves[index] = leaf
      # Return inserted leaf for convenience
      return leaf
  
imports: import numpy
label_desc: Use image node_id 9 for calling the RCTree obj's underlying member method code with example usage: obj.insert_point(point, index, tolerance) and returns: leaf, leaf, duplicate