Crear BST equilibrado a partir de una lista ordenada de enteros

15

Dada una lista única y ordenada de enteros, cree un árbol de búsqueda binaria equilibrado representado como una matriz sin utilizar la recursividad.

Por ejemplo:

func( [1,2,3,5,8,13,21] ) => [5,2,13,1,3,8,21]

Antes de comenzar, una pista: podemos simplificar este problema una tonelada para que no tengamos que pensar en los enteros de entrada (¡ni en ningún objeto comparable para el caso!).

Si sabemos que la lista de entrada ya está ordenada, su contenido es irrelevante. Simplemente podemos pensarlo en términos de índices en la matriz original.

Una representación interna de la matriz de entrada se convierte en:

func( [0,1,2,3,4,5,6] ) => [3,1,5,0,2,4,6]

Esto significa que, en lugar de escribir algo que tenga que tratar con objetos comparables, realmente solo necesitamos escribir una función que asigne desde el rango [0, n) a la matriz resultante. Una vez que tenemos el nuevo orden, simplemente podemos aplicar la asignación a los valores de la entrada para crear la matriz de retorno.

Las soluciones válidas deben:

  • Acepte una matriz de elementos cero y devuelva una matriz vacía.
  • Acepte una matriz entera de longitud n y devuelva una matriz entera
    • De longitud entre n y la siguiente potencia más alta de 2 menos 1. (por ejemplo, para el tamaño de entrada 13 regrese en cualquier lugar entre 13 y 15).
    • Matriz que representa un BST donde el nodo raíz está en la posición 0 y la altura es igual a log (n) donde 0 representa un nodo faltante (o un nullvalor similar si su idioma lo permite). Los nodos vacíos, si están presentes, solo deben existir al final del árbol (por ejemplo, [2,1,0])

La matriz de enteros de entrada tiene las siguientes garantías:

  • Los valores son enteros con signo de 32 bits mayores que cero.
  • Los valores son únicos.
  • Los valores están en orden ascendente desde la posición cero.
  • Los valores pueden ser escasos (es decir, no adyacentes entre sí).

El código más conciso por recuento de caracteres ascii gana, pero también estoy interesado en ver soluciones elegantes para cualquier idioma en particular.

Casos de prueba

Las salidas para matrices simples que contienen 1a npara diversos n. Como se describió anteriormente, los 0s finales son opcionales.

[]
[1]
[2,1,0]
[2,1,3]
[3,2,4,1,0,0,0]
[4,2,5,1,3,0,0]
[4,2,6,1,3,5,0]
[4,2,6,1,3,5,7]
[5,3,7,2,4,6,8,1,0,0,0,0,0,0,0]
[6,4,8,2,5,7,9,1,3,0,0,0,0,0,0]
[7,4,9,2,6,8,10,1,3,5,0,0,0,0,0]
[8,4,10,2,6,9,11,1,3,5,7,0,0,0,0]
[8,4,11,2,6,10,12,1,3,5,7,9,0,0,0]
[8,4,12,2,6,10,13,1,3,5,7,9,11,0,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]
Jake Wharton
fuente
Todas las preguntas en este sitio, ya sea un rompecabezas de programación o un código de golf, deben tener un criterio objetivo primario ganador, para que sea posible decidir indiscutiblemente qué participación debe ganar.
Howard
@ Gracias Gracias. Actualizado con criterios definitivos para el ganador.
Jake Wharton
1
Sería muy útil tener algunos casos de prueba que cubran los casos difíciles, en lugar de (como en la actualidad) solo el más fácil.
Peter Taylor
¿Hay alguna razón para descartar la recurrencia? No es que esté buscando una solución recursiva, pero parece artificial e innecesaria.
dmckee --- ex gatito moderador
1
¿Alguien puede explicar cómo la lista representa un BST?
justinpc

Respuestas:

4

Rubí , 143

s=ARGV.size;r,q=[],[[0,s]];s.times{b,e=q.shift;k=Math::log2(e-b).to_i-1;m=(e-b+2)>(3<<k)?b+(2<<k)-1:e-(1<<k);r<<ARGV[m];q<<[b,m]<<[m+1,e]};p r

Es una versión comprimida (más o menos) del siguiente código que básicamente hace un BFS en el árbol.

def l(n)
    k = Math::log2(n).to_i-1
    if n+2 > (3<<k) then
        (2<<k)-1
    else
        n-(1<<k) 
    end
end

def bfs(tab)
  result = []
  queue = [[0,tab.size]]
  until queue.empty? do
    b,e = queue.shift
    m = b+l(e-b)
    result << tab[m]
    queue << [b,m] if b < m
    queue << [m+1,e] if m+1 < e
  end
  result
end

p bfs(ARGV)

Además, debido a que es BFS, no DFS, un requisito de solución no recursiva no es significativo, y pone a algunos idiomas en desventaja.

Editar: Solución fija, ¡gracias a @PeterTaylor por su comentario!

dtldarek
fuente
@PeterTaylor La intención era poner 3 a la izquierda de 4, pero no hay espacios en blanco, por lo que está mal. ¡Gracias por señalar eso!
dtldarek
@PeterTaylor Reparado durante el almuerzo, debería funcionar ahora.
dtldarek
4

Java , 252

Ok, aquí está mi intento. He estado jugando con operaciones de bits y se me ocurrió esta forma directa de calcular el índice de un elemento en el BST a partir del índice en la matriz original.

Versión comprimida

public int[]b(int[]a){int i,n=1,t;long x,I,s=a.length,p=s;int[]r=new int[(int)s];while((p>>=1)>0)n++;p=2*s-(1l<<n)+1;for(i=0;i<s;i++){x=(i<p)?(i+1):(p+2*(i-p)+1);t=1;while((x&1<<(t-1))==0)t++;I=(1<<(n-t));I|=((I-1)<<t&x)>>t;r[(int)I-1]=a[i];}return r;}

La versión larga sigue a continuación.

public static int[] makeBst(int[] array) {
  long size = array.length;
  int[] bst = new int[array.length];

  int nbits = 0;
  for (int i=0; i<32; i++) 
    if ((size & 1<<i)!=0) nbits=i+1;

  long padding = 2*size - (1l<<nbits) + 1;

  for (int i=0; i<size; i++) {
    long index2n = (i<padding)?(i+1):(padding + 2*(i-padding) + 1);

    int tail=1;
    while ((index2n & 1<<(tail-1))==0) tail++;
    long bstIndex = (1<<(nbits-tail));
    bstIndex = bstIndex | ((bstIndex-1)<<tail & index2n)>>tail;

    bst[(int)(bstIndex-1)] = array[i];
  }
 return bst;
}
mikail sheikh
fuente
Necesitas un recuento de personajes, y esto no está actualmente golfizado.
dmckee --- ex-gatito moderador
@dmckee He editado la publicación para incluir una versión comprimida y un recuento de personajes
mikail sheikh
Buen espectaculo. Apuesto a que algunos de esos espacios son innecesarios. En c, int[] b(int[] a)se expresa tan bien como int[]b(int[]a).
dmckee --- ex gatito moderador
Tienes a.lengthen la matriz de asignación. Cámbialo a s. Deshágase del espacio entre for (varias veces. Cada bucle for crea un int i=0y también int t=0. Crea con n( int n=0,i,t;) y luego solo i=0en los bucles y t=1dentro. Declare el interno long xy long Icon sy simplemente inicialice en el bucle ( long s=a.length,I,x;y x=../ I=..). No debería necesitar espacios alrededor del binario AND &.
Jake Wharton el
Además, I=I|..se puede escribirI|=..
Jake Wharton el
3
def fn(input):
    import math
    n = len(input)
    if n == 0:
        return []
    h = int(math.floor(math.log(n, 2)))
    out = []
    last = (2**h) - 2**(h+1) + n

    def num_children(level, sibling, lr):
        if level == 0:
            return 0
        half = 2**(level-1)
        ll_base = sibling * 2**level + lr * (half)
        ll_children = max(0, min(last, ll_base + half - 1) - ll_base + 1)
        return 2**(level-1) - 1 + ll_children

    for level in range(h, -1, -1):
        for sibling in range(0, 2**(h-level)):
            if level == 0 and sibling > last:
                break
            if sibling == 0:
                last_sibling_val = num_children(level, sibling, 0)
            else:
                last_sibling_val += 2 + num_children(level, sibling - 1, 1) \
                    + num_children(level, sibling, 0)
            out.append(input[last_sibling_val])
    return out
aarkay
fuente
2

No estoy seguro de si esto se ajusta exactamente a su requisito de nodos vacíos al final del árbol y ciertamente no ganará ningún premio por brevedad, pero creo que es correcto y tiene casos de prueba :)

public class BstArray {
    public static final int[] EMPTY = new int[] { };
    public static final int[] L1 = new int[] { 1 };
    public static final int[] L2 = new int[] { 1, 2 };
    public static final int[] L3 = new int[] { 1, 2, 3 };
    public static final int[] L4 = new int[] { 1, 2, 3, 5 };
    public static final int[] L5 = new int[] { 1, 2, 3, 5, 8 };
    public static final int[] L6 = new int[] { 1, 2, 3, 5, 8, 13 };
    public static final int[] L7 = new int[] { 1, 2, 3, 5, 8, 13, 21 };
    public static final int[] L8 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35 };
    public static final int[] L9 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56 };
    public static final int[] L10 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56, 91 };

    public static void main(String[] args) {
        for (int[] list : Arrays.asList(EMPTY, L1, L2, L3, L4, L5, L6, L7, L8, L9, L10)) {
            System.out.println(Arrays.toString(list) + " => " + Arrays.toString(bstListFromList(list)));
        }
    }

    private static int[] bstListFromList(int[] orig) {
        int[] bst = new int[nextHighestPowerOfTwo(orig.length + 1) - 1];

        if (orig.length == 0) {
            return bst;
        }

        LinkedList<int[]> queue = new LinkedList<int[]>();
        queue.push(orig);

        int counter = 0;
        while (!queue.isEmpty()) {
            int[] list = queue.pop();
            int len = list.length;

            if (len == 1) {
                bst[counter] = list[0];
            } else if (len == 2) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(new int[] { 0 });
            } else if (len == 3) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(getSubArray(list, 2, 1));
            } else {
                int divide = len / 2;
                bst[counter] = list[divide];
                queue.add(getSubArray(list, 0, divide));
                queue.add(getSubArray(list, divide + 1, len - (divide + 1)));
            }
            counter++;
        }

        return bst;
    }

    private static int nextHighestPowerOfTwo(int n) {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

    private static int[] getSubArray(int[] orig, int origStart, int length) {
        int[] list = new int[length];
        System.arraycopy(orig, origStart, list, 0, length);
        return list;
    }
}
Andrew Flynn
fuente
2

Golfscript ( 99 89)

~]:b[]:^;{b}{{:|.,.2base,(2\?:&[-)&2/]{}$0=&(2/+:o[=]^\+:^;|o<.!{;}*|o)>.!{;}*}%:b}while^p

Básicamente, un puerto directo de mi solución Python, funciona casi de la misma manera.

Probablemente se puede mejorar bastante con más "golfismos", ya mejorado en 10 caracteres con la entrada de @ petertaylor :)

Joachim Isaksson
fuente
Creo que debería ser posible en no más de 70, aunque todavía no he terminado mi respuesta de GolfScript. Sin embargo, hay algunas mejoras fáciles para la suya. !{;}{}ifsolo puede ser !{;}*porque !garantiza regresar 0o 1. Puede usar tokens no alfabéticos para las variables, por lo que si usa en ^lugar de r, en |lugar de x, en &lugar dey que puede eliminar todo ese espacio en blanco.
Peter Taylor
@PeterTaylor Gracias, no sabía sobre variables no alfanuméricas, todavía muy nuevo en golfscript :)
Joachim Isaksson
2

Java 192

Asigna el índice en la entrada al índice en la salida

int[]b(int[]o){int s=o.length,p=0,u=s,i=0,y,r[]=new int[s],c[]=new int[s];while((u>>=1)>0)p++;for(int x:o){y=p;u=i;while(u%2>0){y--;u/=2;}r[(1<<y)-1+c[y]++]=x;i+=i>2*s-(1<<p+1)?2:1;}return r;}

Versión larga:

static int[] bfs(int[] o) {
  int rowCount = 32 - Integer.numberOfLeadingZeros(o.length); // log2
  int slotCount = (1<<rowCount) - 1; // pow(2,rowCount) - 1

  // number of empty slots at the end
  int emptySlots = slotCount - o.length;
  // where we start to be affected by these empty slots
  int startSkippingAbove = slotCount - 2 * emptySlots; // = 2 * o.length - slotCount

  int[] result = new int[o.length];
  int[] rowCounters = new int[rowCount]; // for each row, how many slots in that row are taken
  int i = 0; // index of where we would be if this was a complete tree (no trailing empty slots)
  for (int x : o) {
    // the row (depth) a slot is in is determined by the number of trailing 1s
    int rowIndex = rowCount - Integer.numberOfTrailingZeros(~i) - 1;
    int colIndex = rowCounters[rowIndex]++; // count where we are
    int rowStartIndex = (1 << rowIndex) - 1; // where this row starts in the result array

    result[rowStartIndex + colIndex] = x;

    i++;
    // next one has to jump into a slot that came available by not having slotCount values
    if (i > startSkippingAbove) i++;
  }

  return result;
}
Wouter Coekaerts
fuente
2

Wolfram Mathematica 11, 175 Bytes

g[l_]:=(x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2);Join@@Table[Cases[l//.{{}->{},b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])},_Integer,{m}],{m,x[l]}])

La función g[l]toma como entrada a List(p l={1,2,3,4,...}. Ej. ) Y devuelve a Listde la forma deseada. Funciona de la siguiente manera:

  • x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2) toma una lista y encuentra la raíz del BST asociado.
    • i=Length[a]+1 atajo para la longitud de la lista
    • 2^Ceiling@Log2[i]/2 límite superior en el valor de la raíz
    • Min[i-#/2,#]&@(...) Mínimo de los dos argumentos donde # representa lo que está dentro del(...)
  • l//.{...} Aplicar repetidamente las reglas de reemplazo que siguen a l
  • {}->{} Nada que hacer (este es el caso límite para evitar un bucle infinito)
  • b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])Dividir un Listen{{lesser}, root, {greater}}
  • Cases[...,_Integer,{m}] Toma todos los enteros a nivel (profundidad) m
  • Table[...,{m,1,x[l]}]Para todos mhasta x[l](que es más de lo necesario en realidad).

Se puede probar ejecutando

Table[g[Range[a]], {a, 0, 15}]//MatrixForm

Esta implementación no incluye ceros finales.

MannyC
fuente
1

Pitón ( 175 171)

Bastante condensado, aún bastante legible;

def f(a):
 b=[a]
 while b:
  c,t=((s,2**(len(bin(len(s)))-3))for s in b if s),[]
  for x,y in c:
   o=min(len(x)-y+1,y/2)+(y-1)/2
   yield x[o]
   t+=[x[:o],x[o+1:]]
  b=t

Devuelve el resultado, por lo que puede recorrerlo o (para fines de visualización) imprimirlo como una lista;

>>> for i in range(1,17): print i-1,list(f(range(1,i)))
 0 []
 1 [1]
 2 [2, 1]
 3 [2, 1, 3]
 4 [3, 2, 4, 1]
 5 [4, 2, 5, 1, 3]
 6 [4, 2, 6, 1, 3, 5]
 7 [4, 2, 6, 1, 3, 5, 7]
 8 [5, 3, 7, 2, 4, 6, 8, 1]
 9 [6, 4, 8, 2, 5, 7, 9, 1, 3]
10 [7, 4, 9, 2, 6, 8, 10, 1, 3, 5]
11 [8, 4, 10, 2, 6, 9, 11, 1, 3, 5, 7]
12 [8, 4, 11, 2, 6, 10, 12, 1, 3, 5, 7, 9]
13 [8, 4, 12, 2, 6, 10, 13, 1, 3, 5, 7, 9, 11]
14 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13]
15 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
Joachim Isaksson
fuente
@dtldarek Parece que su comentario fue eliminado, pero ahora parece pasar los casos de prueba.
Joachim Isaksson
Eliminé mi comentario para que la gente no votara por la respuesta de @ dtldarek debido a un comentario que decía que tenía errores.
Peter Taylor
@PeterTaylor Bueno, gracias por su consideración ;-)
dtldarek
1

Java

Esta es una solución de cálculo directo. Creo que funciona, pero tiene un efecto secundario pragmáticamente inocuo. La matriz que produce puede estar corrupta, pero no de ninguna manera que afecte las búsquedas. En lugar de producir 0 nodos (nulos), producirá nodos inalcanzables, es decir, los nodos ya se habrán encontrado anteriormente en el árbol durante la búsqueda. Funciona mapeando la matriz de índices de una potencia regular de una matriz de árbol de búsqueda binaria de 2 tamaños en una matriz de árbol de búsqueda binaria de tamaño irregular. Al menos, creo que funciona.

import java.util.Arrays;

public class SortedArrayToBalanceBinarySearchTreeArray
{
    public static void main(String... args)
    {
        System.out.println(Arrays.toString(binarySearchTree(19)));
    }

    public static int[] binarySearchTree(int m)
    {
        int n = powerOf2Ceiling(m + 1);
        int[] array = new int[n - 1];

        for (int k = 1, index = 1; k < n; k *= 2)
        {
            for (int i = 0; i < k; ++i)
            {
                array[index - 1] = (int) (.5 + ((float) (m)) / (n - 1)
                        * (n / (2 * k) * (1 + 2 * index) - n));
                ++index;
            }
        }

        return array;
    }

    public static int powerOf2Ceiling(int n)
    {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

}

Aquí hay una versión más condensada (solo la función y los nombres emparejados). Todavía tiene el espacio en blanco, pero no me preocupa ganar. Además, esta versión en realidad toma una matriz. El otro simplemente tomó un int para el índice más alto en la matriz.

public static int[] b(int m[])
{
    int n = m.length;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;

    int[] a = new int[n - 1];

    for (int k = 1, j = 1, i; k < n; k *= 2)
    {
        for (i = 0; i < k; ++i)
        {
            a[j - 1] = m[(int) (.5 + ((float) m.length) / (n - 1)
                    * (n / (2 * k) * (1 + 2 * j) - n)) - 1];
            ++j;
        }
    }

    return a;
}
metaphyze
fuente
Como se trata de código de golf , acorte sus métodos / nombres / etc. lo más breve posible; elimine todos los espacios en blanco (y métodos / materiales innecesarios) e inserte el recuento de caracteres. De lo contrario, lo estás haciendo genial.
Justin
@Jake Wharton. Realmente me gustaría ver su solución de mapeo directo. No estoy 100% seguro de que la mía funcione para matrices muy grandes porque se basa en un mapeo matemático continuo cuyos valores se redondean. Ciertamente parece funcionar, pero no estoy seguro de cómo probarlo.
metaphyze
1

GolfScript ( 79 77 70 caracteres)

Como el ejemplo en la pregunta usa una función, he hecho de esto una función. Eliminar el {}:f;para dejar una expresión que toma la entrada en la pila y deja el BST en la pila ahorraría 5 caracteres.

{[.;][{{.!!{[.,.)[1]*{(\(@++}@(*1=/()\@~]}*}%.{0=}%\{1>~}%.}do][]*}:f;

Demostración en línea (nota: la aplicación puede tardar un poco en calentarse: se agotó el tiempo de espera dos veces antes de ejecutarse en 3 segundos).

Con espacios en blanco para mostrar la estructura:

{
    # Input is an array: wrap it in an array for the working set
    [.;]
    [{
        # Stack: emitted-values working-set
        # where the working-set is essentially an array of subtrees
        # For each subtree in working-set...
        {
            # ...if it's not the empty array...
            .!!{
                # ...gather into an array...
                [
                    # Get the size of the subtree
                    .,
                    # OEIS A006165, offset by 1
                    .)[1]*{(\(@++}@(*1=
                    # Split into [left-subtree-plus-root right-subtree]
                    /
                    # Rearrange to root left-subtree right-subtree
                    # where left-subtree might be [] and right-subtree might not exist at all
                    ()\@~
                ]
            }*
        }%
        # Extract the leading element of each processed subtree: these will join the emitted-values
        .{0=}%
        # Create a new working-set of the 1, or 2 subtrees of each processed subtree
        \{1>~}%
        # Loop while the working-set is non-empty
        .
    }do]
    # Stack: [[emitted values at level 0][emitted values at level 1]...]
    # Flatten by joining with the empty array
    []*
}:f;
Peter Taylor
fuente
1

J , 52 bytes

t=:/:(#/:@{.(+:,>:@+:@i.@>:@#)^:(<.@(2&^.)@>:@#`1:))

la función toma una lista ordenada y regresa en orden de árbol binario

Observe que los árboles tienen una forma idéntica pero el nivel inferior se acorta

  • `1: comenzar con 1
  • <.@(2&^.)@>:@# iterar por el piso de log2 (longitud + 1)
  • +: , >:@+:@i.@>:@# loop: agrega el doble del último vector con números impares 1,3 .. 2 * longitud + 1
  • # /:@{. tomar solo la cantidad requerida de artículos y obtener sus índices de clasificación
  • /: aplicar esos índices de clasificación a la entrada dada

TIO

jayprich
fuente