Arbre kd

Un arbre kd tridimensional. La primera divisió (roig) talla la cela raïl (blanc) en dos subceldas, que són dividides a la seua volta (vert) en dos subceldas. Finalment, cada una d'eixes quatre és dividida (blava) en dos subceldas. Ya que no hi ha més divisions, les huit finals es diuen fulls. Les esferes grogues representen els nodos de l'arbre.

En ciències de la computació, un Arbre kd (abreviatura d'arbre k-dimensional) és una estructura de senyes de particionado de l'espai que organisa els punts en un Espai euclídeo de k dimensions. Els arbres kd són un cas especial dels arbres BSP.

Un arbre kd ampra només plans perpendicularés a un dels eixos del sistema de coordenades. Açò diferix dels arbres BSP, a on els plans poden ser arbitraris. Ademés, tots els nodos d'un arbre kd, des del nodo raïl fins als nodos full, almagasenen un punt. Mentrestant, en els arbres BSP són els fulls els únics nodos que contenen punts (o unes atres primitives geomètriques). Com a conseqüència, cada pla deu passar a través d'un dels punts de l'arbre kd.

Tècnicament, la lletra k es referix al número de dimensions. Un arbre kd tridimensional podria ser cridat un arbre 3d. No obstant se sol amprar l'expressió "arbre kd tridimensional". (També és més descriptivo, ya que un arbre tridimensional pot ser vàries coses, pero el terme arbre kd es referix a un tipo en concret d'arbre de particionado.) Les lletres k i d s'escriuen en minúscules, inclús al principi d'una oració. La k s'escriu en cursiva, encara que són també comunes les formes "arbre KD" i "arbre Kd".

Operacions en arbres k

Construir un arbre k

Ya que hi ha moltes maneres possibles d'elegir plans alineats als eixos, hi ha moltes maneres de generar arbres kd. El sistema habitual és:

• Conforme es descendix en l'arbre, s'ampren cicles a través dels eixos per a seleccionar els plans. (Per eixemple, la raïl pot tindre un pla alineat en l'eix x, els seus descendents tindrien plans alineats en el i i els nets de la raïl alineats en el z, i aixina successivament)

• En cada pas, el punt seleccionat per a crear el pla de cort serà la mijana dels punts posats en l'arbre kd, lo que respecta les seues coordenades en l'eix que està sent usat.

Este método du a un arbre kd balancejat, a on cada nodo full està a la mateixa distància de la raïl. De totes formes, els arbres balancejats no són necessàriament òptims per a totes les aplicacions.

Donada una llista de n punts, el següent algoritme genera un arbre kd balancejat que conté dits punts.

function kdtree (list of points pointList, int depth)
{
    if pointList is empty
        return nil;
    else
    {
        // Select axis based on depth baix that axis cycles through all valid values
        var int axis := depth mod k;

        // Sort point list and choose medien as pivot element
        sort pointList using predicate: point1[axis] < point2[axis];
        choose medien from pointList;

        // Create node and construct subtrees
        var tree_node node;
        node.location := medien;
        node.leftChild := kdtree(points in pointList before medien, depth+1);
        node.rightChild := kdtree(points in pointList after medien, depth+1);
        return node;
    }
}

Este algoritme implementat en Python seria:

class Node:pass

def kdtree(pointList, depth=0):
    if not pointList:
        return

    # Select axis based on depth baix that axis cycles through all valid values
    k = len(pointList[0]) # assumes all points have the same dimension
    axis = depth % k

    # Sort point list and choose medien as pivot element
    pointList.sort(key=lambda x:x[axis])
    medien = len(pointList)/2 # choose medien

    # Create node and construct subtrees
    node = Node()
    node.location = pointList[medien]
    node.leftChild = kdtree(pointList[0:medien], depth+1)

node.rightChild = kdtree(pointList[medien+1:], depth+1)
    return node

Un eixemple d'us:

pointList = [(2,3),(5,4),(9,1),(4,7),(8,1)]
tree = kdtree(pointList)

Este algoritme crea el invariante per a qualsevol nodo. Tots els nodos en el subárbol de l'esquerra estan en un costat del pla de tall, i tots els nodos del subárbol de la dreta estan en l'atre costat. El pla de tall d'un nodo passa a través del punt associat en eixe nodo (referenciado en el còdic per node.location)

Afegir elements a un arbre kd

Els nodos s'afigen a un arbre kd de la mateixa forma que s'afigen a qualsevol atre arbre. Primer, es recorre l'arbre escomençant per la raïl i seguint pel nodo de l'esquerra o de la dreta depenent de si el punt que es vol insertar està en la dreta o en l'esquerra del pla de cort. Una volta que s'aplega a un nodo full, s'afig el nou punt a l'esquerra o a la dreta del nodo full, de nou depenent d'en que costat del pla es troba el nou punt.

Eliminar elements d'un arbre kd

Per a eliminar un element d'un arbre kd, lo primer que es deu fer és com en qualsevol estructura és verificar l'existència de l'en este cas, punt a eliminar, suponent la localisació d'est va ser exitós com a nodo full de la nostra estructura, s'elimina este nodo i procedim al rebalanceo.

El rebalanceo consistix en revisar des del nodo pare del nodo eliminat si té associat un o dos fills (que són la possibilitats reals que té), si té solament 1 fill, es trepa al nodo fill a la posició del pare i s'elimina eixe tall, passant a revisar al nodo pare, si té 2 fills, podem concloure la revisió.

D'igual manera que l'inserció, l'algoritme s'eixecuta en temps logaritmico.

Equilibrar un arbre kd

Cal ser cuidadós en equilibrar un arbre kd. Com estos arbres estan ordenats en múltiples dimensions, no es pot amprar la tècnica de rotació d'arbres per a equilibrar-los — açò trencaria el invariante.

Quan s'eliminen varis nodos (al voltant de la mitat), o quan s'afigen molts nodos (quan s'acosta a duplicar la cantitat de nodos full), podem dir que la millor opció per a no trencar l'equilibri d'esta estructura de senyes, és optar per tornar a construir l'estructura, ya que en qüestió de temps nos va a prendre la mateixa complexitat el fer tots els canvis de colp que el construir una nova estructura segons els canvis proposts, pero nos dona més segfuridad de mantindre la invariante.

Usos d'un arbre kd

• Archiu:Kdtreeogg.ogvImplementació en CBR ( Raonament Basat En Casos)

Busca ortogonal en un arbre kd

Usar un arbre kd per a trobar tots els punts que es troben en un rectàngul determinat (o anàlec de més dimensions). Esta operació també es denomina ranc de busca ortogonal.

Determinar on evaluar una superfície

En les regressió locals és comuna evaluar la superfície continguda directament solament pels vèrtiços de l'arbre kd i interpolar en algun punt. Este us, reflectit en l'image de dalt, busca assegurar que només es realisaran les evaluacions directes necessàries. Com els arbres kd es "adapten" a l'espai, este método pot suministrar una excelent aproximació a les verdaderes superfícies de regressió local. Si l'aproximació és pobra, pot millorar-se en més subdivisions.