Hispanopedia WikiEn informática , un árbol de búsqueda de prioridad es una estructura de datos de árbol para almacenar puntos en dos dimensiones. Fue introducido originalmente por Edward M. McCreight . [ 1 ] Es, en efecto, una extensión de la cola de prioridad con el propósito de mejorar el tiempo de búsqueda de O( n ) a O( s + log n ), donde n es el número de puntos en el árbol y s es el número de puntos devueltos por la búsqueda.
Descripción
El árbol de búsqueda por prioridad se utiliza para almacenar un conjunto de puntos bidimensionales ordenados por prioridad y por un valor clave. Esto se logra creando un híbrido entre una cola de prioridad y un árbol de búsqueda binaria .
El resultado es un árbol donde cada nodo representa un punto del conjunto de datos original. El punto contenido en el nodo es el de menor prioridad. Además, cada nodo contiene un valor clave que se utiliza para dividir los puntos restantes (generalmente la mediana de las claves, excluyendo el punto del nodo) en un subárbol izquierdo y otro derecho. Los puntos se dividen comparando sus valores clave con la clave del nodo, asignando los de menor valor al subárbol izquierdo y los de valor estrictamente mayor al subárbol derecho. [ 2 ]
Operaciones
Construcción
La construcción del árbol requiere un tiempo de O( n log n ) y un espacio de O( n ). A continuación se propone un algoritmo de construcción:
árbol construct_tree ( datos ) { si length ( datos ) > 1 { node_point = find_point_with_minimum_priority ( datos ) // Seleccionar el punto con la prioridad más baja reduced_data = remove_point_from_data ( datos , node_point ) node_key = calculate_median ( reduced_data ) // calcular la mediana, excluyendo el punto seleccionado // Dividir los puntos left_data = [] right_data = [] para ( punto en reduced_data ) { si point . key <= node_key left_data . append ( punto ) else right_data . append ( punto ) }subárbol_izquierdo = construir_árbol ( datos_izquierdos ) subárbol_derecho = construir_árbol ( datos_derechos )return nodo // Nodo que contiene node_key, node_point y los subárboles izquierdo y derecho } else if length ( data ) == 1 { return nodo hoja // Nodo hoja que contiene el único punto de datos restante } else if length ( data ) == 0 { return null // Este nodo está vacío } }Sin embargo, si los puntos se ordenan por sus valores clave, el árbol se puede construir en tiempo lineal. [ 3 ] Esto se puede hacer fácilmente construyendo un árbol binario balanceado sobre los valores clave (como hojas) en tiempo lineal. Cada nodo interno almacena un puntero al nodo de menor prioridad y el recuento del número de elementos en el subárbol con raíz en ese nodo. Por lo tanto, el nodo con prioridad mínima se puede identificar en tiempo constante. La mediana de los puntos restantes y el elemento con la siguiente prioridad más baja se pueden identificar en tiempo O(log n). Por lo tanto, la relación de recurrencia es T(n)=2T(n/2)+O(log n)=O(n).
Búsqueda de rango terrestre
El árbol de búsqueda por prioridad se puede consultar de forma eficiente para una clave en un intervalo cerrado y para un valor de prioridad máximo. Es decir, se puede especificar un intervalo [ min_key , max_key ] y otro intervalo [ -∞ , max_priority ] y devolver los puntos contenidos en él. Esto se ilustra en el siguiente pseudocódigo:
puntos search_tree ( árbol , min_key , max_key , max_priority ) { raíz = obtener_nodo_raíz ( árbol ) resultado = []Si get_child_count ( root ) > 0 { si get_point_priority ( root ) > max_priority return null // No existirá nada interesante en esta rama. RetornarSi min_key <= get_point_key ( root ) <= max_key // ¿ Es el punto raíz uno de interés? result.append ( get_point ( node )) Si min_key < get_node_key ( root ) // ¿ Deberíamos buscar en el subárbol izquierdo ? result.append ( search_tree ( root.left_sub_tree , min_key , max_key , max_priority ) )if get_node_key ( root ) < max_key // ¿ Debemos buscar en el subárbol derecho? result.append ( search_tree ( root.right_sub_tree , min_key , max_key , max_priority ) ) return result else { // Este es un nodo hoja if get_point_priority ( root ) < max_priority and min_key < = get_point_key ( root ) < = max_key // ¿ Es un punto de interés hoja? result.append ( get_point ( node )) } }Véase también
Referencias
- ↑ McCreight, Edward (mayo de 1985). "Árboles de búsqueda de prioridad". SIAM Journal on Scientific Computing . 14 (2): 257– 276. doi : 10.1137/0214021 .
- ↑ Lee, DT; Yu, Hung-I (2018). "19: Árboles de búsqueda de intervalo, segmento, rango y prioridad"En Mehta, Dinesh; Sahni, Sartaj (eds.). Manual de estructuras de datos y aplicaciones (2.ª ed.). Londres: Chapman & Hall/CRC. págs. 19:1–19:17. doi : 10.1201/9781315119335 . ISBN 9781315119335.
- ↑ Mark Berg, Otfried Cheong, Marc Kreveld, Mark Overmars, Geometría computacional, algoritmos y aplicaciones, 3.ª edición, Springer, 2008
- Árboles (estructuras de datos)
- Estructuras de datos geométricos