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]

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!

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;
}

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

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;
    }
}

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 :)

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;
}

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.

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]

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;
}

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;

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

Python 2 , 107 bytes

Golf de la respuesta de Joachim Isaksson , Input es un singleton que contiene la lista.

def f(a):
 for x in a:
	if x:w=len(x);y=1<<len(bin(w))-3;o=min(w-y+1,y/2)+~-y/2;yield x[o];a+=x[:o],x[o+1:]

Pruébalo en línea!