class Noeud:
    def __init__(self):
        self.x_median = 0
        self.liste_x = [] # réservé au débogage
        self.x_min = 0
        self.x_max = 0
        self.noeud_gauche = None
        self.noeud_droite = None
                

def generation_arbre(noeud,liste_x):
    n = len(liste_x)
    noeud.liste_x = liste_x
    noeud.x_min = liste_x[0]
    noeud.x_max = liste_x[n-1]
    if n==1:
        return
    else:
        m = int(n/2)
        x_median = liste_x[m]
        noeud.x_median = x_median
        i = m-1
        while i>=0 and liste_x[i]==x_median:
            i -= 1
        i+=1
        if i>0:
            liste_gauche = liste_x[0:i] 
            noeud.noeud_gauche = Noeud()
            generation_arbre(noeud.noeud_gauche,liste_gauche)
            liste_droite = liste_x[i:n] 
            noeud.noeud_droite = Noeud()
            generation_arbre(noeud.noeud_droite,liste_droite)
        else:
            return
                     

def rechercher_valeur(noeud,valeur):
    if noeud.noeud_gauche!=None and noeud.noeud_droite!=None:
        if valeur < noeud.x_median:
            return rechercher_valeur(noeud.noeud_gauche,valeur)
        else:
            return rechercher_valeur(noeud.noeud_droite,valeur)
    else:
        for x in noeud.liste_x:
            if valeur==x:
                return True
        return False
        
def obtenir_arbre(noeud,pile):
    if noeud.noeud_gauche==None and noeud.noeud_droite==None:
        for x in noeud.liste_x:
            pile.append(x)
    else:
        obtenir_arbre(noeud.noeud_gauche,pile)
        obtenir_arbre(noeud.noeud_droite,pile)
        
def rechercher_dans_intervalle(noeud,a,b,pile):
    if noeud==None:
        return
    if noeud.x_min >= a and noeud.x_max <= b: 
        obtenir_arbre(noeud,pile)
    else:
        if not((a<noeud.x_min and b<noeud.x_min) or (a>noeud.x_max and b>noeud.x_max)):
            rechercher_dans_intervalle(noeud.noeud_gauche,a,b,pile)
            rechercher_dans_intervalle(noeud.noeud_droite,a,b,pile)
                

def partition(liste,axe,debut,fin):
    pivot = liste[fin][axe]
    i = debut
    for j in range(debut,fin):
        if liste[j][axe]<=pivot:
            liste[i],liste[j] = liste[j],liste[i]
            i += 1
    liste[i],liste[fin] = liste[fin],liste[i]
    return i
                 

def selection(liste,axe,debut,fin,rang): 
    if debut==fin:
        return liste[debut][axe]
    i = partition(liste,axe,debut,fin)
    k = i-debut+1
    if rang==k:
        return liste[i][axe]
    elif rang < k:
        return selection(liste,axe,debut,i-1,rang)
    else:
        return selection(liste,axe,i+1,fin,rang-k)
                  

def mediane(liste,axe):
    return selection(liste.copy(),axe,0,len(liste)-1,int(len(liste)/2)+1)
                  

import random
N=10
K=2
points = []
for i in range(N):
    p = []
    for axe in range(K):
        p.append(random.random())
    points.append(p)

mediane_x = mediane(points,0)
                  

def separation_mediane(liste,axe):
    m = mediane(liste,axe)
    N = len(liste)
    K = len(liste[0])
    L1 = []
    L2 = []
    for i in range(N):
        if liste[i][axe] < m:
            L1.append(liste[i])
        else:
            L2.append(liste[i])
    return (m,L1,L2)
(m,L1,L2) = separation_mediane(points,0)
                  
import numpy

class NoeudKd:
    def __init__(self):
        self.axe = 0
        self.valeur_mediane = 0
        self.liste_points = [] # réservé au débogage
        self.noeud_gauche = None
        self.noeud_droite = None
                

def generation_arbre_kd(noeud,liste_points,K,profondeur=0):
    noeud.liste_points = liste_points
    if len(liste_points)==1:
        return
    else:
        axe = profondeur%K
        (m,L1,L2) = separation_mediane(liste_points,axe)
        noeud.valeur_mediane = m
        noeud.axe = axe
        if len(L1)!=0:    
            noeud.noeud_gauche = NoeudKd()
            generation_arbre_kd(noeud.noeud_gauche,L1,K,profondeur+1)
        if len(L2)!=0:
            noeud.noeud_droite = NoeudKd()
            generation_arbre_kd(noeud.noeud_droite,L2,K,profondeur+1)