Créer un BST équilibré à partir d'une liste triée d'entiers

15

Étant donné une liste unique et triée d'entiers, créez un arbre de recherche binaire équilibré représenté sous forme de tableau sans utiliser de récursivité.

Par exemple:

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

Avant de commencer, un indice: nous pouvons simplifier ce problème d'une tonne pour ne pas avoir à penser aux entiers d'entrée (ou à tout objet comparable d'ailleurs!).

Si nous savons que la liste d'entrée est déjà triée, son contenu n'a pas d'importance. Nous pouvons simplement y penser en termes d'indices dans le tableau d'origine.

Une représentation interne du tableau d'entrée devient alors:

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

Cela signifie que plutôt que d'écrire quelque chose qui doit traiter avec des objets comparables, nous n'avons vraiment besoin que d'écrire une fonction qui mappe de la plage [0, n) au tableau résultant. Une fois que nous avons la nouvelle commande, nous pouvons simplement appliquer le mappage aux valeurs de l'entrée pour créer le tableau de retour.

Les solutions valides doivent:

  • Acceptez un tableau à zéro élément et renvoyez un tableau vide.
  • Acceptez un tableau entier de longueur n et retournez un tableau entier
    • D'une longueur comprise entre n et la puissance immédiatement supérieure de 2 moins 1. (par exemple, pour la taille d'entrée 13, retournez entre 13 et 15).
    • Tableau qui représente un BST où le nœud racine est à la position 0 et la hauteur est égale à log (n) où 0 représente un nœud manquant (ou une nullvaleur semblable à si votre langue le permet). Les nœuds vides, s'ils sont présents, ne doivent exister qu'à la fin de l'arborescence (par exemple, [2,1,0])

Le tableau d'entiers en entrée présente les garanties suivantes:

  • Les valeurs sont des entiers signés 32 bits supérieurs à zéro.
  • Les valeurs sont uniques.
  • Les valeurs sont en ordre croissant à partir de la position zéro.
  • Les valeurs peuvent être clairsemées (c'est-à-dire non adjacentes les unes aux autres).

Le code le plus laconique par nombre de caractères ascii gagne, mais je suis également intéressé à voir des solutions élégantes pour une langue particulière.

Cas de test

Les sorties pour les tableaux simples contenant 1to npour divers n. Comme décrit ci-dessus, les 0s finaux sont facultatifs.

[]
[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
la source
Toutes les questions sur ce site, qu'il s'agisse d'un casse-tête de programmation ou d'un code de golf, doivent avoir un critère de gain principal objectif, de sorte qu'il est indiscutablement possible de décider quelle inscription doit gagner.
Howard
@Howard Merci. Mis à jour avec des critères définitifs pour le gagnant.
Jake Wharton
1
Il serait très utile de disposer de certains cas de test qui couvrent les cas difficiles, plutôt que (comme actuellement) juste le plus simple.
Peter Taylor
Y a-t-il une raison pour exclure la récursivité? Non pas que je recherche une solution récursive, mais cela semble à la fois artificiel et inutile.
dmckee --- chaton ex-modérateur
1
Quelqu'un peut-il expliquer comment la liste représente un BST?
justinpc

Réponses:

4

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

Il s'agit d'une version (vaguement) compressée du code suivant qui effectue essentiellement un BFS sur l'arborescence.

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)

De plus, parce que c'est BFS, pas DFS, une exigence de solution non récursive n'est pas significative, et elle désavantage certaines langues.

Edit: Solution fixe, merci à @PeterTaylor pour son commentaire!

dtldarek
la source
@PeterTaylor L'intention était de mettre 3 sur la gauche de 4, mais il n'y a pas de blancs, donc c'est faux. Merci d'avoir fait remarquer cela!
dtldarek
@PeterTaylor Fixé pendant le déjeuner, cela devrait fonctionner maintenant.
dtldarek
4

Java , 252

Ok, voici ma tentative. J'ai joué avec les opérations sur les bits et j'ai trouvé cette façon directe de calculer l'index d'un élément dans le BST à partir de l'index dans le tableau d'origine.

Version compressée

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 version longue suit ci-dessous.

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
la source
Vous avez besoin d'un nombre de caractères, et ce n'est pas actuellement joué.
dmckee --- chaton ex-modérateur
@dmckee J'ai édité le message pour inclure une version compressée et un nombre de caractères
mikail sheikh
Bon spectacle. Je parie que certains de ces espaces sont inutiles. En c, int[] b(int[] a)est tout aussi bien exprimé que int[]b(int[]a).
dmckee --- chaton ex-modérateur
Vous avez a.lengthdans l'allocation de tableau. Remplacez-le par s. Débarrassez-vous de l'espace entre for (plusieurs fois. Chaque boucle for crée un int i=0et aussi int t=0. Créez avec n( int n=0,i,t;) puis juste i=0dans les boucles et à l' t=1intérieur. Déclarez l'intérieur long xet long Iavec set initialisez simplement dans la boucle ( long s=a.length,I,x;et x=../ I=..). Vous ne devriez pas avoir besoin d'espaces autour du ET binaire &.
Jake Wharton
Aussi, I=I|..peut être écritI|=..
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
la source
2

Je ne sais pas si cela correspond exactement à vos besoins de nœuds vides à la fin de l'arbre et cela ne gagnera certainement pas de prix pour la brièveté, mais je pense que c'est correct et qu'il a des cas de test :)

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
la source
2

Golfscript ( 99 89)

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

Fondamentalement, un port direct de ma solution Python fonctionne à peu près de la même manière.

Peut probablement être amélioré un peu avec plus de "golfismes", déjà amélioré de 10 caractères avec l'entrée de @ petertaylor :)

Joachim Isaksson
la source
Je pense que cela devrait être possible dans pas plus de 70, même si je n'ai pas encore tout à fait terminé ma réponse GolfScript. Il y a cependant quelques améliorations faciles. !{;}{}ifpeut simplement être !{;}*parce que les !garanties de retour 0ou 1. Vous pouvez utiliser des jetons non alphabétiques pour les variables, donc si vous utilisez ^au lieu de r, |au lieu de x, &au lieu de, yvous pouvez éliminer tout cet espace.
Peter Taylor
@PeterTaylor Merci, je ne connaissais pas les variables non alphanumériques, encore très nouveau pour golfscript :)
Joachim Isaksson
2

Java 192

Mappe l'index en entrée à l'index en sortie

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

Version longue:

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
la source
2

Wolfram Mathematica 11, 175 octets

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 fonction g[l]prend en entrée a List(par exemple l={1,2,3,4,...}) et renvoie a Listde la forme souhaitée. Cela fonctionne comme suit:

  • x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2) prend une liste et trouve la racine du BST associé.
    • i=Length[a]+1 raccourci pour la longueur de la liste
    • 2^Ceiling@Log2[i]/2 limite supérieure sur la valeur de la racine
    • Min[i-#/2,#]&@(...)Minimum des deux arguments où #représente ce qui se trouve à l'intérieur du(...)
  • l//.{...} Appliquez à plusieurs reprises les règles de remplacement qui suivent pour l
  • {}->{} Rien à faire (c'est le cas de bord pour éviter une boucle infinie)
  • b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])Diviser un Listen{{lesser}, root, {greater}}
  • Cases[...,_Integer,{m}] Prendre tous les entiers au niveau (profondeur) m
  • Table[...,{m,1,x[l]}]Pour tous mjusqu'à x[l](ce qui est plus que nécessaire en fait).

Il peut être testé en exécutant

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

Cette implémentation n'inclut pas les zéros de fin.

MannyC
la source
1

Python ( 175 171)

Assez condensé, encore assez lisible;

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

Il renvoie le résultat, vous pouvez donc le parcourir ou (à des fins d'affichage) l'imprimer sous forme de liste;

>>> 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
la source
@dtldarek Son commentaire semble avoir été supprimé, mais cela semble réussir les cas de test maintenant.
Joachim Isaksson
J'ai supprimé mon commentaire de peur que les gens s'abstiennent de voter pour la réponse de @ dtldarek à cause d'un commentaire disant que c'était bogué.
Peter Taylor
@PeterTaylor Eh bien, merci pour votre considération ;-)
dtldarek
1

Java

Il s'agit d'une solution de calcul direct. Je pense que cela fonctionne, mais il a un effet secondaire pragmatiquement inoffensif. Le tableau qu'il produit peut être corrompu, mais pas d'une manière qui pourrait affecter les recherches. Au lieu de produire 0 noeuds (nuls), il produira des noeuds inaccessibles, c'est-à-dire que les noeuds auront déjà été trouvés plus tôt dans l'arborescence pendant la recherche. Il fonctionne en mappant le tableau d'indices d'une puissance régulière de tableau d'arbre de recherche binaire de taille 2 sur un tableau d'arbre de recherche binaire de taille irrégulière. Au moins, je pense que cela fonctionne.

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

}

Voici une version plus condensée (juste la fonction et les noms associés). Il y a toujours un espace blanc, mais je ne suis pas inquiet de gagner. Cette version prend également un tableau. L'autre a juste pris un int pour l'index le plus élevé du tableau.

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;
}
métaphyze
la source
Puisqu'il s'agit de code-golf , raccourcissez vos méthodes / noms / etc au plus court possible; supprimer tous les espaces (et les méthodes / matériel inutiles) et insérer le nombre de caractères. Sinon, vous faites bien.
Justin
@Jake Wharton. J'aimerais vraiment voir votre solution de cartographie directe. Je ne suis pas sûr à 100% que la mienne fonctionne pour de très grands tableaux car elle repose sur une cartographie mathématique continue dont les valeurs sont arrondies. Cela semble certainement fonctionner, mais je ne sais pas comment le prouver.
metaphyze
1

GolfScript ( 79 77 70 caractères)

Étant donné que l'exemple de la question utilise une fonction, j'en ai fait une fonction. Supprimer le {}:f;pour laisser une expression qui prend une entrée sur la pile et laisse le BST sur la pile économiserait 5 caractères.

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

Démo en ligne (note: l'application peut prendre un peu de temps pour s'échauffer: elle a expiré deux fois pour moi avant de fonctionner en 3 secondes).

Avec un espace pour montrer la structure:

{
    # 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
la source
1

J , 52 octets

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

la fonction prend une liste triée et retourne dans l'ordre de l'arbre binaire

remarquez que les arbres ont une forme identique mais le niveau du fond est raccourci

  • `1: commencer par 1
  • <.@(2&^.)@>:@# itérer par étage de log2 (longueur + 1)
  • +: , >:@+:@i.@>:@# boucle: ajoute le double du dernier vecteur avec des nombres impairs 1,3 .. 2 * longueur + 1
  • # /:@{. prendre uniquement le nombre requis d'éléments et obtenir leurs indices de tri
  • /: appliquer ces indices de tri à l'entrée donnée

TIO

Jayprich
la source