class_docstr: !
  @brief Represents balanced static KD-tree that does not provide services to add and remove nodes after
          initialization.
  @details In the term KD 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.
  
  There is an example how to create KD-tree:
  @code
      from pyclustering.container.kdtree import kdtree_balanced, kdtree_visualizer
      from pyclustering.utils import read_sample
      from pyclustering.samples.definitions import FCPS_SAMPLES
  
      sample = read_sample(FCPS_SAMPLES.SAMPLE_LSUN)
      tree_instance = kdtree_balanced(sample)
  
      kdtree_visualizer(tree_instance).visualize()
  @endcode
  
  Output result of the example above - figure 1.
  @image html kd_tree_balanced_lsun.png "Fig. 1. Balanced KD-tree for sample 'Lsun'."
  
  @see kdtree
class_docstr_tok: ["!","@","brief","Represents","balanced","static","KD-tree","that","does","not","provide","services","to","add","and","remove","nodes","after","initialization",".","@","details","In","the","term","KD","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",".","There","is","an","example","how","to","create","KD-tree",":","@","code","from","pyclustering.container.kdtree","import","kdtree_balanced",",","kdtree_visualizer","from","pyclustering.utils","import","read_sample","from","pyclustering.samples.definitions","import","FCPS_SAMPLES","sample","=","read_sample","(","FCPS_SAMPLES.SAMPLE_LSUN",")","tree_instance","=","kdtree_balanced","(","sample",")","kdtree_visualizer","(","tree_instance",")",".visualize","(",")","@","endcode","Output","result","of","the","example","above","-","figure","1",".","@","image","html","kd_tree_balanced_lsun.png","``","Fig",".","1",".","Balanced","KD-tree","for","sample","'Lsun","'",".","''","@","see","kdtree"]
docstr: !
  @brief Creates balanced sub-tree using elements from list `nodes`.
  
  @param[in] nodes (list): List of KD-tree nodes.
  @param[in] parent (node): Parent node that is used as a root to build the sub-tree.
  @param[in] depth (uint): Depth of the tree that where children of the `parent` should be placed.
  
  @return (node) Returns a node that is a root of the built sub-tree.
docstr_tok: ["!","@","brief","Creates","balanced","sub-tree","using","elements","from","list","`","nodes","`",".","@","param","[","in","]","nodes","(","list",")",":","List","of","KD-tree","nodes",".","@","param","[","in","]","parent","(","node",")",":","Parent","node","that","is","used","as","a","root","to","build","the","sub-tree",".","@","param","[","in","]","depth","(","uint",")",":","Depth","of","the","tree","that","where","children","of","the","`","parent","`","should","be","placed",".","@","return","(","node",")","Returns","a","node","that","is","a","root","of","the","built","sub-tree","."]
code: def __create_tree(self, nodes, parent, depth):
      """!
      @brief Creates balanced sub-tree using elements from list `nodes`.
  
      @param[in] nodes (list): List of KD-tree nodes.
      @param[in] parent (node): Parent node that is used as a root to build the sub-tree.
      @param[in] depth (uint): Depth of the tree that where children of the `parent` should be placed.
  
      @return (node) Returns a node that is a root of the built sub-tree.
  
      """
      if len(nodes) == 0:
          return None
  
      discriminator = depth % self._dimension
  
      nodes.sort(key=lambda n: n.data[discriminator])
      median = len(nodes) // 2
  
      # Elements could be the same around the median, but all elements that are >= to the current should
      # be at the right side.
      # TODO: optimize by binary search - no need to use O(n)
      median = find_left_element(
          nodes,
          median,
          lambda n1, n2: n1.data[discriminator]
          < n2.data[discriminator],
      )
      # while median - 1 >= 0 and \
      #         nodes[median].data[discriminator] == nodes[median - 1].data[discriminator]:
      #     median -= 1
  
      new_node = nodes[median]
      new_node.disc = discriminator
      new_node.parent = parent
      new_node.left = self.__create_tree(
          nodes[:median], new_node, depth + 1
      )
      new_node.right = self.__create_tree(
          nodes[median + 1 :], new_node, depth + 1
      )
  
      self._length += 1
      return new_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_balanced obj's underlying member method code with example usage: obj.__create_tree(nodes, parent, depth) and returns: new_node, None