Árbol kd

Un árbol kd tridimensional. La primera división (rojo) corta la celda raíz (blanco) en dos subceldas, que son divididas a su vez (verde) en dos subceldas. Finalmente, cada una de esas cuatro es dividida (azul) en dos subceldas. Dado que no hay más divisiones, las ocho finales se llaman hojas. Las esferas amarillas representan los nodos del árbol.

En ciencias de la computación, un Árbol kd (abreviatura de árbol k-dimensional) es una estructura de datos de particionado del espacio que organiza los puntos en un Espacio euclídeo de k dimensiones. Los árboles kd son un caso especial de los árboles BSP.

Un árbol kd emplea sólo planos perpendiculares a uno de los ejes del sistema de coordenadas. Esto difiere de los árboles BSP, donde los planos pueden ser arbitrarios. Además, todos los nodos de un árbol kd, desde el nodo raíz hasta los nodos hoja, almacenan un punto. Mientras tanto, en los árboles BSP son las hojas los únicos nodos que contienen puntos (u otras primitivas geométricas). Como consecuencia, cada plano debe pasar a través de uno de los puntos del árbol kd.

Técnicamente, la letra k se refiere al número de dimensiones. Un árbol kd tridimensional podría ser llamado un árbol 3d. Sin embargo se suele emplear la expresión "árbol kd tridimensional". (También es más descriptivo, ya que un árbol tridimensional puede ser varias cosas, pero el término árbol kd se refiere a un tipo en concreto de árbol de particionado.) Las letras k y d se escriben en minúsculas, incluso al principio de una oración. La k se escribe en cursiva, aunque son también comunes las formas "árbol KD" y "árbol Kd".

Contenido

Operaciones en árboles k

Construir un árbol k

Dado que hay muchas maneras posibles de elegir planos alineados a los ejes, hay muchas maneras de generar árboles kd. El sistema habitual es:

  • Conforme se desciende en el árbol, se emplean ciclos a través de los ejes para seleccionar los planos. (Por ejemplo, la raíz puede tener un plano alineado con el eje x, sus descendientes tendrían planos alineados con el y y los nietos del raíz alineados con el z, y así sucesivamente)
  • En cada paso, el punto seleccionado para crear el plano de corte será la mediana de los puntos puestos en el árbol kd, lo que respeta sus coordenadas en el eje que está siendo usado.

Este método lleva a un árbol kd balanceado, donde cada nodo hoja está a la misma distancia de la raíz. De todas formas, los árboles balanceados no son necesariamente óptimos para todas las aplicaciones.

Dada una lista de n puntos, el siguiente algoritmo genera un árbol kd balanceado que contiene dichos puntos.

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

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

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

Este algoritmo implementado en Python sería:

class Node:pass
 
def kdtree(pointList, depth=0):
    if not pointList:
        return
 
    # Select axis based on depth so 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 median as pivot element
    pointList.sort(key=lambda x:x[axis])
    median = len(pointList)/2 # choose median
 
    # Create node and construct subtrees
    node = Node()
    node.location = pointList[median]
    node.leftChild = kdtree(pointList[0:median], depth+1)
    node.rightChild = kdtree(pointList[median+1:], depth+1)
    return node

Un ejemplo de uso:

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

Este algoritmo crea el invariante para cualquier nodo. Todos los nodos en el subárbol de la izquierda están en un lado del plano de corte, y todos los nodos del subárbol de la derecha están en el otro lado. El plano de corte de un nodo pasa a través del punto asociado con ese nodo (referenciado en el código por node.location)

Añadir elementos a un árbol kd

Los nodos se añaden a un árbol kd de la misma forma que se añaden a cualquier otro árbol. Primero, se recorre el árbol empezando por la raíz y siguiendo por el nodo de la izquierda o de la derecha dependiendo de si el punto que se quiere insertar está en la derecha o en la izquierda del plano de corte. Una vez que se llega a un nodo hoja, se añade el nuevo punto a la izquierda o a la derecha del nodo hoja, de nuevo dependiendo de en que lado del plano se encuentra el nuevo punto.

Eliminar elementos de un árbol kd

Eliminar un punto de un árbol kd sin romper el invariante. (POR HACER)

Equilibrar un árbol kd

Hay que ser cuidadoso al equilibrar un árbol kd. Como estos árboles están ordenados en múltiples dimensiones, no se puede emplear la técnica de rotación de árboles para equilibrarlos — esto rompería el invariante.

Usos de un árbol kd

Búsqueda ortogonal en un árbol kd

Usar un árbol kd para encontrar todos los puntos que se encuentran en un rectángulo determinado (o análogo de más dimensiones). Esta operación también se denomina rango de búsqueda ortogonal.

Determinar dónde evaluar una superficie

En las regresiones locales es común evaluar la superficie contenida directamente sólo por los vértices del árbol kd e interpolar en algún punto. Este uso, reflejado en la imagen de arriba, busca asegurar que sólo se realizarán las evaluaciones directas necesarias. Como los árboles kd se "adaptan" al espacio, este método puede suministrar una excelente aproximación a las verdaderas superficies de regresión local. Si la aproximación es pobre, puede mejorarse con más subdivisiones.

Complejidad

  • Construir un árbol kd estático a partir de n puntos es de O(nlogn).
  • Insertar un nuevo punto en un árbol kd balanceado es de O(logn).
  • Eliminar un punto de un árbol kd balanceado es de O(logn).


Enlaces externos (inglés)


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • árbol — (Del lat. arbor, ŏris). 1. m. Planta perenne, de tronco leñoso y elevado, que se ramifica a cierta altura del suelo. 2. Pieza de hierro en la parte superior del husillo de la prensa de imprimir. 3. En los órganos, eje que, movido a voluntad del… …   Diccionario de la lengua española

  • árbol — sustantivo masculino 1. Planta leñosa de tronco elevado que se ramifica a cierta altura del suelo: Han plantado muchos árboles. Este árbol da una sombra deliciosa. árbol del Paraíso Árbol de tronco gris, hojas blanquecinas, estrechas, y flores… …   Diccionario Salamanca de la Lengua Española

  • Arbol — is programming language, primarily developed to serve for Genetic Programming experiments. It is functional programming language inspired by the ideas of other small and esoteric languages. An Arbol program looks like: // Simple I/O ((Z a)b) =… …   Wikipedia

  • Arbol.bb — (Ассемини,Италия) Категория отеля: Адрес: Via Belli 6, 09032 Ассемини, Италия …   Каталог отелей

  • árbol — 1. (en anatomía) estructura anatómica con ramas que se extienden hacia fuera como las de un árbol, como el árbol bronquial. 2. patrón de búsqueda de información en una base de datos de un ordenador, siguiendo una serie de opciones ramificadas a… …   Diccionario médico

  • Árbol — (Del lat. arbor.) ► sustantivo masculino 1 BOTÁNICA Planta de tronco leñoso que se ramifica a mayor o menor altura del suelo, formando una copa. 2 NÁUTICA Madero redondo o cilíndrico fijo en una embarcación que sostiene las vergas a las que se… …   Enciclopedia Universal

  • Árbol-B — Ejemplo de árbol B. En las ciencias de la computación, los árboles B o B árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Son árboles binarios de búsqueda en… …   Wikipedia Español

  • Árbol — Para otros usos de este término, véase Árbol (desambiguación). Un roble en Dinamarca …   Wikipedia Español

  • Árbol 2-3 — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 2 de febrero de 2009. También puedes… …   Wikipedia Español

  • Árbol AA — En informática un árbol AA es un tipo de árbol binario de búsqueda auto balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, Arne Andersson. Los árboles AA son …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.