algorithm - recorrido - como hacer un arbol binario
Obtener padre de un vértice en un árbol binario perfecto (7)
Tengo un árbol binario perfecto que se enumera de forma posterior al pedido. Un ejemplo de tal árbol sería
15
7 14
3 6 10 13
1 2 4 5 8 9 11 12
El tamaño del árbol me es conocido. Estoy buscando una fórmula o un algoritmo simple que tome un solo número como entrada (el ID del vértice en el que estoy interesado) y también devuelva un solo número: el ID del padre. Es bastante fácil atravesar el árbol desde la parte superior y obtener el resultado en O(log n) . ¿Hay una solución más rápida? Estoy más interesado en las hojas, así que si hay una solución para el caso especial, tráela también.
Cuando dices ''que se enumeran a la manera de orden posterior'' ¿quieres decir que tienes una representación indexada del árbol? Quiero decir, ¿la estructura de datos interna es una matriz o algo similar?
Además, ¿tiene el índice del elemento que le interesa en su padre?
Si la respuesta para ambas preguntas es ''sí'': asumiendo que el índice del elemento hijo es k, el índice del elemento padre viene dado por
(k - 1) / 2
Echemos un vistazo a tu árbol:
15
7 14
3 6 10 13
1 2 4 5 8 9 11 12
Reescriba la etiqueta n como 15-n . Entonces obtenemos:
0
8 1
12 9 5 2
14 13 11 10 7 6 4 3
que también podría ser escrito como
0
+8 +1
+4 +1 +4 +1
+2 +1 +2 +1 +2 +1 +2 +1
Bueno, hay un patrón para ti. Entonces, en este esquema de etiquetado, los niños izquierdos son 2^(i+1) más que sus padres, donde i es la altura del niño, mientras que los niños derechos son 1 más que sus padres. Sin embargo, ¿cómo podemos calcular la altura de un niño y si es un niño de izquierda o de derecha?
Desafortunadamente, no puedo encontrar ninguna forma de obtener esta información sin calcular la ruta completa al nodo, lo que significa tiempo logarítmico. Sin embargo, puede deducir la ruta al nodo directamente desde la etiqueta del nodo (como se muestra aquí para un árbol de altura-3):
- Supongamos que tenemos una etiqueta
n - Si
n == 0, es la raíz. - De otra manera:
- Si
n - 8 >= 0, está en el subárbol izquierdo de la raíz. Establecern = n-8. - Si
n - 8 < 0, está en el subárbol derecho de la raíz. Establecern = n-1.
- Si
- Si
n == 0ahora, es la raíz de cualquier subárbol que se descubrió en el último paso. - De otra manera:
- Si
n - 4 >= 0, está en el subárbol izquierdo de cualquier subárbol que se descubrió en el último paso. Setn = n-4 - Si
n - 4 < 0, está en el subárbol correcto de cualquier subárbol descubierto en el último paso. Establecern = n-1.
- Si
- Etcétera hasta que tengas que probar
n-1 >= 0.
Podría hacer todo esto usando aritmética de bits y -1 s, y sería espectacularmente rápido en términos del mundo real (calcular esto en un árbol de trillones de nodos solo tomaría ~ 12 veces más que un árbol de 10 nodos (ignorando los problemas de memoria) ) pero todavía va a ser el tiempo logarítmico.
De todos modos, una vez que conozca la altura de la etiqueta y si es un niño de derecha o de izquierda, puede calcular fácilmente la etiqueta del padre utilizando las relaciones que mencioné anteriormente.
Lo siento por la respuesta que no responde, pero no creo que sea posible hacerlo en menos de O(log n) , incluso permitiendo operaciones aritméticas de tiempo constante y operaciones lógicas a nivel de bits.
Cada bit en el índice del nodo potencialmente tiene un efecto en casi todas las decisiones de izquierda / derecha / parada en el recorrido desde el nodo a la raíz, incluida la primera. Además, al examinar los índices de los nodos en cada nivel del árbol, son aperiódicos (y no solo en potencias de 2). Esto significa (creo) que un número constante de operaciones aritméticas no es suficiente para identificar el nivel, o si el nodo es un niño izquierdo o derecho.
Sin embargo, es un problema fascinante, y me encantaría que se demuestre lo contrario. Acabo de rastrear mi copia de Hacker''s Delight . Tenía grandes esperanzas en algunas de las bases numéricas exóticas con las que juegan, pero nada encaja.
Si se le permite consultar las ID de los hijos de un nodo, puede hacer algunas cosas útiles.
Caso trivial 1: si x = size , es la raíz.
Caso trivial 2: si x es una hoja (consulte las ID de niños para averiguarlo), intente x + 1 . Si x + 1 no es una hoja (otra consulta de ID de hijo), x fue el hijo correcto de x + 1 . Si x + 1 es una hoja, x es el hijo izquierdo de x + 2 .
Para nodos internos: los hijos de x son x - 1 (niño derecho) y x - (1 << height(x) - 1) (niño izquierdo, el niño derecho es un árbol binario perfecto, por lo que tiene 2 nodos h -1 ). Entonces, al usar la diferencia entre x y left_child(x) , se puede determinar la altura de x : height(x) =ctz(x - left_child(x)) , pero en realidad es el tamaño de ese subárbol que se requiere para que puedas tomar 1 << height todos modos, por lo que el ctz se puede caer.
Así que el padre de x es x + 1 (iff right_child(x + 1) == x ) o el padre de x es
x + (x - left_child(x)) * 2 (de lo contrario).
Eso no es tan bueno como hacer matemáticas en la identificación, pero suponiendo que se le permita solicitar los hijos de un nodo en un tiempo constante, este es un algoritmo de tiempo constante.
El índice primario se puede encontrar en O (log * n) tiempo y O (1) espacio.
Aquí log * n significa logaritmo iterado : el número de veces que la función de logaritmo debe aplicarse iterativamente antes de que el resultado sea menor o igual a 1.
En realidad, eso se puede hacer incluso más rápido, en tiempo O (1) si pudiéramos permitirnos el espacio O (n) para una tabla de búsqueda grande (almacenar el índice principal para cada nodo en el árbol).
A continuación, dibujaré varios algoritmos que no necesitan espacio adicional y darán como resultado el tiempo de peor caso O (log n), el tiempo esperado O (log n), el tiempo peor O (log log) y el O (log). * n) el peor de los casos. Se basan en las siguientes propiedades de los índices posteriores al pedido para un árbol binario perfecto:
- Todos los índices en la ruta más a la izquierda del árbol son iguales a 2 i -1.
- Los índices de cada elemento secundario derecho del nodo en la ruta de la izquierda son iguales a 2 i -2.
- Cualquier nodo en la ruta de la izquierda y su subárbol derecho están etiquetados con índices que tienen el bit no cero más significativo en la misma posición:
i. - El subárbol izquierdo de cualquier nodo en la ruta de la izquierda contiene 2 nodos i- 1. (Lo que significa que después de restar 2 i -1 obtendremos un nodo que está posicionado de manera similar a su padre, tiene la misma profundidad, pero está más cerca de los nodos "especiales" que satisfacen las propiedades # 1 y # 2).
Las propiedades # 1 y # 2 proporcionan algoritmos simples para obtener un nodo primario para algunos nodos del árbol: para los índices de la forma 2 i -1, multiplique por 2 y agregue 1 ; para los índices de la forma 2 i -2, solo agregue 1 . Para otros nodos, podríamos usar repetidamente la propiedad # 4 para llegar al nodo que satisface la propiedad # 1 o # 2 (al restar los tamaños de varios subárboles izquierdos), luego encontrar un nodo primario ubicado en la ruta más a la izquierda, y luego volver a agregar todo lo anterior Valores restados. Y la propiedad # 3 permite encontrar rápidamente el tamaño de los subárboles que se deben restar. Así que tenemos el siguiente algoritmo:
- Mientras que
((x+1) & x) != 0y((x+2) & (x+1)) != 0repite el paso 2. - Borre el bit no cero más significativo y agregue
1. Acumula la diferencia. - Si
((x+1) & x) == 0, multiplica por2y suma1; de lo contrario, si((x+2) & (x+1)) == 0, agregue1. - Vuelva a agregar todas las diferencias acumuladas en el paso 2.
Por ejemplo, 12 (en forma binaria 0b1100 ) se transforma en el paso # 2 a 0b0101 , luego a 0b0010 (o 2 en decimal). La diferencia acumulada es 10 . El paso # 3 agrega 1 y el paso # 4 agrega 10 , por lo que el resultado es 13 .
Otro ejemplo: 10 (en forma binaria 0b1010 ) se transforma en el paso # 2 a 0b0011 (o 3 en decimal). El paso # 3 lo duplica ( 6 ), luego agrega 1 ( 7 ). El paso # 4 agrega la diferencia acumulada ( 7 ), por lo que el resultado es 14 .
La complejidad del tiempo es O (log n), pero solo cuando todas las operaciones elementales se ejecutan en tiempo O (1).
Para mejorar la complejidad del tiempo podríamos realizar varias iteraciones del paso # 2 en paralelo. Podríamos obtener n/2 bits de alto orden del índice y calcular la población de ellos. Si después de agregar el resultado a los bits de orden inferior restantes, la suma no se desborda a estos bits de orden superior, podríamos aplicar este enfoque de forma recursiva, con complejidad O (log log n). Si tenemos un desbordamiento, podríamos volver al algoritmo original (bit a bit). Tenga en cuenta que todos los bits de orden inferior establecidos también deben tratarse como desbordamiento. Entonces, la complejidad resultante es O (log log n) el tiempo esperado .
En lugar de retroceder a bit a bit, podríamos manejar el desbordamiento utilizando la búsqueda binaria. Podríamos determinar cuántos bits de orden superior (menos de n/2 ) se seleccionarán para que no tengamos desbordamiento o (como para el índice 0b00101111111111 ) el número de bits seleccionados de orden superior distintos de cero es exactamente 1 . Tenga en cuenta que no es necesario que apliquemos este procedimiento de búsqueda binaria más de una vez porque el segundo desbordamiento no ocurrirá mientras el número de bits en el número sea mayor que O (registro log n). Entonces, la complejidad resultante es O (log log n), el peor de los casos . Se supone que todas las operaciones elementales se ejecutan en tiempo O (1). Si algunas operaciones (recuento de población, recuento de cero inicial) se implementan en tiempo O (log log n), entonces nuestra complejidad de tiempo aumenta a O (log 2 log n).
En lugar de dividir los bits del índice en dos conjuntos iguales, podríamos usar una estrategia diferente:
- Calcular el recuento de la población del índice y agregarlo al valor del índice. El bit más significativo que cambió de
0a1determina el punto de separación para los bits de orden superior / orden inferior. - Calcule el conteo de la población en bits de orden superior, luego agregue el resultado a los bits de orden inferior.
- Si el bit de "separación" es distinto de cero y
((x+1) & x) != 0y((x+2) & (x+1)) != 0, continúe desde el paso # 1. - Si todos los bits de orden inferior están configurados y el bit de orden superior menos significativo está configurado, procese este caso de esquina como elemento secundario derecho.
- Si
((x+1) & x) != 0y((x+2) & (x+1)) != 0, también procese esto como hijo derecho. - Si
((x+1) & x) == 0, multiplica por2y suma1; de lo contrario, si((x+2) & (x+1)) == 0, agregue1.
Si se cumple la condición del paso # 3, esto significa que la adición en el paso # 2 dio como resultado un bit de "separación". Otros bits de orden inferior representan un número que no puede ser mayor que el conteo de la población original. El número de bits establecidos en este número no puede ser mayor que el logaritmo del conteo de población del valor original. Esto significa que el número de bits establecidos después de cada iteración es a lo sumo un logaritmo del número de bits establecidos en la iteración anterior. Por lo tanto, la complejidad en el peor de los casos es O (log * n). Esto está muy cerca de O (1). Por ejemplo, para números de 32 bits necesitamos aproximadamente 2 iteraciones o menos.
Cada paso de este algoritmo debe ser obvio, excepto probablemente el paso # 5, cuya exactitud se debe probar. Tenga en cuenta que este paso se ejecuta solo cuando la adición de resultados de conteo de población se lleva a un bit de "separación", pero la adición de un conteo de población de solo bits de orden superior no da lugar a este mantenimiento. El bit de "separación" corresponde al valor 2 i . La diferencia entre el recuento de población de todos los bits y el recuento de población de solo bits de orden superior es a lo sumo i . Entonces el paso # 5 trata con un valor de al menos 2 i - i . Apliquemos algoritmo bit a bit a este valor. 2 i - i es lo suficientemente grande como para que se establezca el bit i-1 . Borre este bit y agregue 1 al valor en los bits 0..i-2 . Este valor es al menos 2 i-1 - (i-1) porque solo restamos 2 i-1 y agregamos 1 . O si movemos el índice una posición a la derecha, tenemos nuevamente al menos 2 i -i. Si repetimos este procedimiento, siempre encontraremos un bit distinto de cero en la posición i-1 . Cada paso disminuye gradualmente la diferencia entre el valor en los bits 0..i-1 y la potencia más cercana de 2 . Cuando esta diferencia llega a 2 , podríamos detener este algoritmo bit a bit porque el nodo actual es claramente un hijo correcto. Dado que este algoritmo bit a bit siempre tiene el mismo resultado, podríamos omitirlo y procesar el nodo actual como un elemento secundario correcto.
Aquí está la implementación en C ++ de este algoritmo. Más detalles y algunos otros algoritmos se pueden encontrar en ideone .
uint32_t getMSBmask(const uint32_t x)
{ return 1 << getMSBindex(x); }
uint32_t notSimpleCase(const uint32_t x)
{ return ((x+1) & x) && ((x+2) & (x+1)); }
uint32_t parent(const uint32_t node)
{
uint32_t x = node;
uint32_t bit = x;
while ((x & bit) && notSimpleCase(x))
{
const uint32_t y = x + popcnt(x);
bit = getMSBmask(y & ~x);
const uint32_t mask = (bit << 1) - 1;
const uint32_t z = (x & mask) + popcnt(x & ~mask);
if (z == mask && (x & (bit << 1)))
return node + 1;
x = z;
}
if (notSimpleCase(x))
return node + 1;
else
return node + 1 + (((x+1) & x)? 0: x);
}
Si necesitamos encontrar el padre solo para un nodo hoja , este algoritmo y este código pueden simplificarse. ( Ideone ).
uint32_t parent(const uint32_t node)
{
uint32_t x = node;
while (x > 2)
{
const uint32_t y = x + popcnt(x);
const uint32_t bit = getMSBmask(y & ~x);
const uint32_t mask = (bit << 1) - 1;
x = (x & mask) + popcnt(x & ~mask);
}
return node + 1 + (x == 1);
}
function getParent(node, size)
{
var rank = size, index = size;
while (rank > 0) {
var leftIndex = index - (rank + 1)/2;
var rightIndex = index - 1;
if (node == leftIndex || node == rightIndex) {
return index;
}
index = (node < leftIndex ? leftIndex : rightIndex);
rank = (rank - 1)/2;
}
}
Comienza desde la raíz, decide en qué rama se debe bajar y se repite hasta que se encuentra el nodo. El rango es el índice del nodo más a la izquierda en el mismo nivel: 1, 3, 7, 15, ..., k^2 - k + 1 .
Los parámetros de entrada son:
-
node: el índice del nodo del que desea el padre. (Basado en 1) -
size: el índice del nodo raíz;15en tu ejemplo.
Ejemplo:
>>> r = []; for (var i = 1; i <= 15; i++) r.push(parent(i,15)); r;
[3, 3, 7, 6, 6, 7, 15, 10, 10, 14, 13, 13, 14, 15, undefined]
import math
def answer(h,q=[]):
ans=[]
for x in q:
if(True):
curHeight=h;
num=int(math.pow(2,h)-1)
if(x==num):
ans.append(-1)
else:
numBE=int(math.pow(2,curHeight)-2)
numL=int(num-int(numBE/2)-1)
numR=int(num-1)
flag=0
while(x!=numR and x!=numL and flag<10):
flag=flag+1
if(x>numL):
num=numR
else:
num=numL
curHeight=curHeight-1
numBE=int(math.pow(2,curHeight)-2)
numL=num-(numBE/2)-1
numR=num-1
ans.append(num)
return ans