class_docstr: !
  @brief   Represents KD Tree that is a space-partitioning data structure for organizing points
            in a k-dimensional space.
  @details In the term k-d tree, k denotes the dimensionality of the space being represented. Each data point is
            represented as a node in the k-d tree in the form of a record of type node. The tree supports
            dynamic construction when nodes can be dynamically added and removed. As a result KD-tree might not be
            balanced if methods `insert` and `remove` are used to built the tree. If the tree is built using
            constructor where all points are passed to the tree then balanced tree is built. Single point search and
            range-search procedures have complexity is `O(n)` in worse case in case of unbalanced tree.
            If there is no need to build dynamic KD-tree, then it is much better to use static KD-tree
            `kdtree_balanced`.
  
  There is an example how to use KD-tree to search nodes (points from input data) that are nearest to some point:
  @code
      # Import required modules
      from pyclustering.samples.definitions import SIMPLE_SAMPLES;
      from pyclustering.container.kdtree import kdtree;
      from pyclustering.utils import read_sample;
      
      # Read data from text file
      sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3);
      
      # Create instance of KD-tree and initialize (fill) it by read data.
      # In this case the tree is balanced.
      tree_instance = kdtree(sample);
      
      # Search for nearest point
      search_distance = 0.3;
      nearest_node = tree_instance.find_nearest_dist_node([1.12, 4.31], search_distance);
      
      # Search for nearest point in radius 0.3
      nearest_nodes = tree_instance.find_nearest_dist_nodes([1.12, 4.31], search_distance);
      print("Nearest nodes:", nearest_nodes);
  @endcode
  
  In case of building KD-tree using `insert` and `remove` method, the output KD-tree might be unbalanced - here
  is an example that demonstrates this:
  @code
      from pyclustering.container.kdtree import kdtree, kdtree_visualizer
      from pyclustering.utils import read_sample
      from pyclustering.samples.definitions import FCPS_SAMPLES
  
      sample = read_sample(FCPS_SAMPLES.SAMPLE_TWO_DIAMONDS)
  
      # Build tree using constructor - balanced will be built because tree will know about all points.
      tree_instance = kdtree(sample)
      kdtree_visualizer(tree_instance).visualize()
  
      # Build tree using `insert` only - unbalanced tree will be built.
      tree_instance = kdtree()
      for point in sample:
          tree_instance.insert(point)
  
      kdtree_visualizer(tree_instance).visualize()
  @endcode
  
  There are two figures where difference between balanced and unbalanced KD-trees is demonstrated.
  
  @image html kd_tree_unbalanced_two_diamonds.png "Fig. 1. Balanced KD-tree for sample 'TwoDiamonds'."
  @image html kd_tree_unbalanced_two_diamonds.png "Fig. 2. Unbalanced KD-tree for sample 'TwoDiamonds'."
  
  @see kdtree_balanced
class_docstr_tok: ["!","@","brief","Represents","KD","Tree","that","is","a","space-partitioning","data","structure","for","organizing","points","in","a","k-dimensional","space",".","@","details","In","the","term","k-d","tree",",","k","denotes","the","dimensionality","of","the","space","being","represented",".","Each","data","point","is","represented","as","a","node","in","the","k-d","tree","in","the","form","of","a","record","of","type","node",".","The","tree","supports","dynamic","construction","when","nodes","can","be","dynamically","added","and","removed",".","As","a","result","KD-tree","might","not","be","balanced","if","methods","`","insert","`","and","`","remove","`","are","used","to","built","the","tree",".","If","the","tree","is","built","using","constructor","where","all","points","are","passed","to","the","tree","then","balanced","tree","is","built",".","Single","point","search","and","range-search","procedures","have","complexity","is","`","O","(","n",")","`","in","worse","case","in","case","of","unbalanced","tree",".","If","there","is","no","need","to","build","dynamic","KD-tree",",","then","it","is","much","better","to","use","static","KD-tree","`","kdtree_balanced","`",".","There","is","an","example","how","to","use","KD-tree","to","search","nodes","(","points","from","input","data",")","that","are","nearest","to","some","point",":","@","code","#","Import","required","modules","from","pyclustering.samples.definitions","import","SIMPLE_SAMPLES",";","from","pyclustering.container.kdtree","import","kdtree",";","from","pyclustering.utils","import","read_sample",";","#","Read","data","from","text","file","sample","=","read_sample","(","SIMPLE_SAMPLES.SAMPLE_SIMPLE3",")",";","#","Create","instance","of","KD-tree","and","initialize","(","fill",")","it","by","read","data",".","#","In","this","case","the","tree","is","balanced",".","tree_instance","=","kdtree","(","sample",")",";","#","Search","for","nearest","point","search_distance","=","0.3",";","nearest_node","=","tree_instance.find_nearest_dist_node","(","[","1.12",",","4.31","]",",","search_distance",")",";","#","Search","for","nearest","point","in","radius","0.3","nearest_nodes","=","tree_instance.find_nearest_dist_nodes","(","[","1.12",",","4.31","]",",","search_distance",")",";","print","(","``","Nearest","nodes",":","''",",","nearest_nodes",")",";","@","endcode","In","case","of","building","KD-tree","using","`","insert","`","and","`","remove","`","method",",","the","output","KD-tree","might","be","unbalanced","-","here","is","an","example","that","demonstrates","this",":","@","code","from","pyclustering.container.kdtree","import","kdtree",",","kdtree_visualizer","from","pyclustering.utils","import","read_sample","from","pyclustering.samples.definitions","import","FCPS_SAMPLES","sample","=","read_sample","(","FCPS_SAMPLES.SAMPLE_TWO_DIAMONDS",")","#","Build","tree","using","constructor","-","balanced","will","be","built","because","tree","will","know","about","all","points",".","tree_instance","=","kdtree","(","sample",")","kdtree_visualizer","(","tree_instance",")",".visualize","(",")","#","Build","tree","using","`","insert","`","only","-","unbalanced","tree","will","be","built",".","tree_instance","=","kdtree","(",")","for","point","in","sample",":","tree_instance.insert","(","point",")","kdtree_visualizer","(","tree_instance",")",".visualize","(",")","@","endcode","There","are","two","figures","where","difference","between","balanced","and","unbalanced","KD-trees","is","demonstrated",".","@","image","html","kd_tree_unbalanced_two_diamonds.png","``","Fig",".","1",".","Balanced","KD-tree","for","sample","'TwoDiamonds","'",".","''","@","image","html","kd_tree_unbalanced_two_diamonds.png","``","Fig",".","2",".","Unbalanced","KD-tree","for","sample","'TwoDiamonds","'",".","''","@","see","kdtree_balanced"]
docstr: !
  @brief Delete node and return root of subtree.
  
  @param[in] node_removed (node): Node that should be removed.
  
  @return (node) Minimal node in line with coordinate that is defined by discriminator.
docstr_tok: ["!","@","brief","Delete","node","and","return","root","of","subtree",".","@","param","[","in","]","node_removed","(","node",")",":","Node","that","should","be","removed",".","@","return","(","node",")","Minimal","node","in","line","with","coordinate","that","is","defined","by","discriminator","."]
code: def __recursive_remove(self, node_removed):
      """!
      @brief Delete node and return root of subtree.
  
      @param[in] node_removed (node): Node that should be removed.
  
      @return (node) Minimal node in line with coordinate that is defined by discriminator.
  
      """
  
      # Check if it is leaf
      if (node_removed.right is None) and (node_removed.left is None):
          return None
  
      discriminator = node_removed.disc
  
      # Check if only left branch exist
      if node_removed.right is None:
          node_removed.right = node_removed.left
          node_removed.left = None
  
      # Find minimal node in line with coordinate that is defined by discriminator
      minimal_node = self.__find_minimal_node(
          node_removed.right, discriminator
      )
      parent = minimal_node.parent
  
      if parent.left is minimal_node:
          parent.left = self.__recursive_remove(minimal_node)
      elif parent.right is minimal_node:
          parent.right = self.__recursive_remove(minimal_node)
  
      minimal_node.parent = node_removed.parent
      minimal_node.disc = node_removed.disc
      minimal_node.right = node_removed.right
      minimal_node.left = node_removed.left
  
      # Update parent for successors of previous parent.
      if minimal_node.right is not None:
          minimal_node.right.parent = minimal_node
  
      if minimal_node.left is not None:
          minimal_node.left.parent = minimal_node
  
      return minimal_node
  
imports: import numpy
  import matplotlib.pyplot
  from pyclustering.utils import euclidean_distance_square, find_left_element
label_desc: Use image node_id 4 for calling the kdtree obj's underlying member method code with example usage: obj.__recursive_remove(node_removed) and returns: minimal_node, None