Criar BST balanceado a partir da lista classificada de números inteiros

15

Dada uma lista exclusiva e ordenada de números inteiros, crie uma árvore de pesquisa binária equilibrada representada como uma matriz sem usar recursão.

Por exemplo:

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

Antes de começarmos, uma dica: podemos simplificar muito esse problema para que não tenhamos que pensar nos números inteiros de entrada (ou em qualquer objeto comparável a esse respeito!).

Se sabemos que a lista de entrada já está classificada, seu conteúdo é irrelevante. Podemos simplesmente pensar sobre isso em termos de índices na matriz original.

Uma representação interna da matriz de entrada se torna:

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

Isso significa que, em vez de escrever algo que tenha que lidar com objetos comparáveis, precisamos realmente apenas escrever uma função que mapeie do intervalo [0, n) à matriz resultante. Depois de termos a nova ordem, podemos simplesmente aplicar o mapeamento aos valores na entrada para criar a matriz de retorno.

As soluções válidas devem:

  • Aceite uma matriz de elemento zero e retorne uma matriz vazia.
  • Aceite uma matriz inteira de comprimento n e retorne uma matriz inteira
    • De comprimento entre n e a próxima potência mais alta de 2 menos 1. (por exemplo, para o tamanho de entrada 13, retorne entre 13 e 15).
    • Matriz que representa um BST em que o nó raiz está na posição 0 e a altura é igual a log (n) em que 0 representa um nó ausente (ou um nullvalor semelhante, se o seu idioma permitir). Nós vazios, se presentes, devem existir apenas no final da árvore (por exemplo, [2,1,0])

A matriz inteira de entrada possui as seguintes garantias:

  • Os valores são números inteiros assinados de 32 bits maiores que zero.
  • Os valores são únicos.
  • Os valores estão em ordem crescente a partir da posição zero.
  • Os valores podem ser escassos (ou seja, não adjacentes um ao outro).

O código mais conciso pela contagem de caracteres ascii vence, mas também estou interessado em ver soluções elegantes para qualquer idioma em particular.

Casos de teste

As saídas para matrizes simples que contêm 1to npara vários n. Como descrito acima, os valores finais 0são opcionais.

[]
[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
fonte
Todas as perguntas neste site, seja um quebra-cabeça de programação ou um código de golfe, devem ter um critério objetivo de vitória primário, para que seja possível decidir indiscutivelmente qual entrada deve ganhar.
Howard
@ Howard Obrigado. Atualizado com critérios definitivos para o vencedor.
Jake Wharton
1
Seria muito útil ter alguns casos de teste que cubram os casos difíceis, e não (como no momento) apenas o mais fácil.
Peter Taylor
Existe alguma razão para excluir a recursão? Não que eu esteja procurando uma solução recursiva, mas isso parece artificial e desnecessário.
dmckee --- ex-moderador gatinho
1
Alguém pode explicar como a lista representa uma BST?
Justinpc #

Respostas:

4

Ruby , 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

É uma versão compactada (vagamente) do código a seguir que basicamente executa um BFS na árvore.

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)

Além disso, por ser BFS, não DFS, um requisito de solução não recursiva não é significativo e coloca alguns idiomas em desvantagem.

Edit: Solução fixa, obrigado a @ PeterTaylor por seu comentário!

dtldarek
fonte
@ PeterTaylor A intenção era colocar 3 à esquerda de 4, mas não há espaços em branco, por isso está errado. Obrigado por apontar isso!
precisa saber é o seguinte
@ PeterTaylor Corrigido durante o almoço, ele deve funcionar agora.
precisa saber é
4

Java , 252

Ok, aqui está a minha tentativa. Eu tenho brincado com operações de bits e criei essa maneira direta de calcular o índice de um elemento no BST a partir do índice na matriz original.

Versão compactada

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

A versão longa segue abaixo.

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
fonte
Você precisa de uma contagem de caracteres e, atualmente, isso não é um jogo de golfe.
dmckee --- ex-moderador gatinho
@dmckee Eu editei o post para incluir uma versão compactada e uma contagem de caracteres
Mikail sheikh
Bom show. Aposto que alguns desses espaços são desnecessários. Em c, int[] b(int[] a)é tão bem expresso quanto int[]b(int[]a).
dmckee --- ex-moderador gatinho
Você tem a.lengthna alocação de matriz. Mude para s. Livre-se do espaço for (várias vezes. Cada loop for cria um int i=0e também int t=0. Crie com n( int n=0,i,t;) e depois apenas i=0nos loops e t=1dentro. Declare o interior long xe long Icom se apenas inicialize no loop ( long s=a.length,I,x;e x=../ I=..). Você não deve precisar de espaços ao redor do binário AND &.
Jake Wharton
Além disso, I=I|..pode ser escritoI|=..
Jake Wharton
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
fonte
2

Não tenho certeza se isso se encaixa exatamente no seu requisito de nós vazios estarem no final da árvore e certamente não ganhará nenhum prêmio por brevidade, mas acho que está correto e tem casos de teste :)

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
fonte
2

Golfe ( 99 89)

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

Basicamente, uma porta direta da minha solução Python, funciona da mesma maneira.

Provavelmente pode ser melhorado um pouco com mais "golfismos", já melhorado em 10 caracteres com a entrada de @ petertaylor :)

Joachim Isaksson
fonte
Eu acho que deveria ser possível em não mais que 70, embora ainda não tenha terminado completamente minha resposta do GolfScript. Existem algumas melhorias fáceis para o seu, no entanto. !{;}{}ifpode ser apenas !{;}*porque !garante a devolução 0ou 1. Você pode usar símbolos não alfabéticos para variáveis, por isso, se você usa ^em vez de r, |em vez de x, &em vez de yvocê pode eliminar tudo o que os espaços em branco.
Peter Taylor
@PeterTaylor Obrigado, não sabia sobre variáveis não alfanuméricos, ainda muito novo para golfscript :)
Joachim Isaksson
2

Java 192

Mapeia o índice na entrada para o índice na saída

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

Versão longa:

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
fonte
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]}])

A função g[l]recebe como entrada a List(por exemplo l={1,2,3,4,...}) e retorna a Listda forma desejada. Funciona da seguinte maneira:

  • x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2) pega uma lista e encontra a raiz do BST associado.
    • i=Length[a]+1 atalho para o comprimento da lista
    • 2^Ceiling@Log2[i]/2 limite superior do valor da raiz
    • Min[i-#/2,#]&@(...)O mínimo dos dois argumentos em que #representa o que está dentro do(...)
  • l//.{...} Aplique repetidamente as regras de substituição a seguir para l
  • {}->{} Nada a fazer (este é o caso extremo para evitar um loop infinito)
  • b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])Dividir um Listem{{lesser}, root, {greater}}
  • Cases[...,_Integer,{m}] Pegue todos os números inteiros no nível (profundidade) m
  • Table[...,{m,1,x[l]}]Para todos, maté x[l](o que é mais do que necessário, na verdade).

Pode ser testado executando

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

Esta implementação não inclui zeros à direita.

MannyC
fonte
1

Python ( 175 171)

Bastante condensado, ainda bastante legível;

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

Ele retorna o resultado, então você pode fazer um loop sobre ele ou (para fins de exibição) imprimi-lo como uma 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
fonte
@dtldarek Seu comentário parece ter sido removido, mas isso parece passar nos casos de teste agora.
Joachim Isaksson
Excluí meu comentário para que as pessoas evitem votar novamente na resposta de @ dtldarek por causa de um comentário dizendo que era de buggy.
Peter Taylor
@PeterTaylor Bem, obrigado por sua consideração ;-)
dtldarek
1

Java

Esta é uma solução de cálculo direto. Eu acho que funciona, mas tem um efeito colateral pragmaticamente inócuo. A matriz que produz pode estar corrompida, mas não de maneira alguma que afete as pesquisas. Em vez de produzir 0 nós (nulos), ele produzirá nós inacessíveis, ou seja, os nós já foram encontrados anteriormente na árvore durante a pesquisa. Ele funciona mapeando a matriz de índices de uma potência regular de matriz de árvore de pesquisa binária de 2 tamanhos em uma matriz de árvore de pesquisa binária de tamanho irregular. Pelo menos, acho 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;
    }

}

Aqui está uma versão mais resumida (apenas a função e os nomes emparelhados). Ainda tem espaço em branco, mas não estou preocupado em ganhar. Além disso, esta versão leva uma matriz. O outro levou apenas um int para o índice mais alto da 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;
}
metafizar
fonte
Como se trata de código-golfe , reduza seus métodos / nomes / etc para o mais curto possível; remova todo o espaço em branco (e métodos / materiais desnecessários) e insira a contagem de caracteres. Caso contrário, você está indo muito bem.
Justin
@Jake Wharton. Eu realmente gostaria de ver sua solução de mapeamento direto. Não tenho 100% de certeza que a mina funcione para matrizes muito grandes porque se baseia em um mapeamento matemático contínuo cujos valores são arredondados. Certamente parece funcionar, mas não tenho certeza de como provar isso.
usar o seguinte método
1

GolfScript ( 79 77 70 caracteres)

Como o exemplo da pergunta usa uma função, eu fiz disso uma função. A remoção de {}:f;para deixar uma expressão que recebe entrada na pilha e deixa o BST na pilha economizaria 5 caracteres.

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

Demonstração online (observação: o aplicativo pode demorar um pouco: se esgotou o tempo limite para mim antes de ser executado em 3 segundos).

Com espaço em branco para mostrar a estrutura:

{
    # 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
fonte
1

J , 52 bytes

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

A função pega uma lista classificada e retorna em ordem de árvore binária

Observe que as árvores têm forma idêntica, mas o nível inferior é reduzido

  • `1: comece com 1
  • <.@(2&^.)@>:@# itera pelo piso de log2 (comprimento + 1)
  • +: , >:@+:@i.@>:@# loop: acrescenta o dobro do último vetor com números ímpares 1,3 .. 2 * comprimento + 1
  • # /:@{. pegue apenas o número necessário de itens e obtenha seus índices de classificação
  • /: aplicar esses índices de classificação à entrada especificada

TIO

Jayprich
fonte
0

Python 2 , 107 bytes

Golfe da resposta de Joachim Isaksson , Input é um singleton que contém a 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:]

Experimente online!

ovs
fonte