/** @import { Metric } from "../metrics/index.js" */
/** @import { ParametersKDTree } from "./index.js" */
/**
 * @template {number[] | Float64Array} T
 * @typedef {Object} ElementWithIndex
 * @property {number} index
 * @property {T} element
 */
/**
 * KD-Tree (K-dimensional Tree) for efficient nearest neighbor search.
 *
 * KD-Trees partition k-dimensional space by recursively splitting along coordinate axes.
 * At each level, the tree splits points based on the median of the coordinate with the largest spread.
 * This creates a balanced binary tree structure that enables efficient O(log n) search on average.
 *
 * Best suited for:
 * - Low to moderate dimensional data (d < 20-30)
 * - When exact nearest neighbors are needed
 * - When dimensionality is not too high
 *
 * Performance degrades in high dimensions (curse of dimensionality) where approximate
 * methods like HNSW or LSH become more effective.
 *
 * @class
 * @category KNN
 * @template {number[] | Float64Array} T
 * @extends KNN<T, ParametersKDTree>
 * @see {@link https://en.wikipedia.org/wiki/K-d_tree}
 */
export class KDTree<T extends number[] | Float64Array> extends KNN<T, ParametersKDTree> {
  /**
   * Generates a KD-Tree with given `elements`.
   *
   * @param {T[]} elements - Elements which should be added to the KD-Tree
   * @param {ParametersKDTree} [parameters={metric: euclidean}] Default is `{metric: euclidean}`
   */
  constructor(elements: T[], parameters?: ParametersKDTree);
  /**
   * @private
   * @type {KDTreeNode<T> | KDTreeLeaf<T> | null}
   */
  private _root;
  /** @returns {Metric} */
  get _metric(): Metric;
  /**
   * @private
   * @param {ElementWithIndex<T>[]} elements
   * @param {number} depth - Current depth in the tree (determines splitting axis)
   * @returns {KDTreeNode<T> | KDTreeLeaf<T> | null} Root of KD-Tree.
   */
  private _construct;
  /**
   * @param {number} i
   * @param {number} k
   */
  search_by_index(
    i: number,
    k?: number,
  ): {
    element: T;
    index: number;
    distance: number;
  }[];
  /**
   * @param {T} t - Query element.
   * @param {number} [k=5] - Number of nearest neighbors to return. Default is `5`
   * @returns {{ element: T; index: number; distance: number }[]} - List consists of the `k` nearest neighbors.
   */
  search(
    t: T,
    k?: number,
  ): {
    element: T;
    index: number;
    distance: number;
  }[];
  /**
   * @private
   * @param {T} target - Query element.
   * @param {number} k - Number of nearest neighbors to return.
   * @param {KDTreeNode<T> | KDTreeLeaf<T> | null} node - Current node.
   * @param {Heap<{ point: ElementWithIndex<T>; distance: number }>} best - Heap of k best found so far.
   */
  private _search_recursive;
}
export type ElementWithIndex<T extends number[] | Float64Array> = {
  index: number;
  element: T;
};
import type { ParametersKDTree } from "./index.js";
import { KNN } from "./KNN.js";
import type { Metric } from "../metrics/index.js";
//# sourceMappingURL=KDTree.d.ts.map