Buat BST Seimbang dari Daftar Bilangan Bulat yang Diurutkan

15

Diberikan daftar unik, diurutkan dari bilangan bulat, buat pohon pencarian biner seimbang yang diwakili sebagai array tanpa menggunakan rekursi.

Sebagai contoh:

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

Sebelum kita mulai, sebuah petunjuk: kita dapat menyederhanakan masalah ini satu ton sehingga kita tidak benar-benar harus memikirkan bilangan bulat input (atau objek yang sebanding dalam hal ini!).

Jika kita tahu daftar input sudah disortir, isinya tidak relevan. Kita bisa memikirkannya dalam hal indeks ke dalam array asli.

Representasi internal dari array input kemudian menjadi:

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

Ini berarti daripada menulis sesuatu yang harus berurusan dengan objek yang sebanding, kita benar-benar hanya perlu menulis fungsi yang memetakan dari rentang [0, n) ke array yang dihasilkan. Setelah kami memiliki orde baru, kami cukup menerapkan pemetaan kembali ke nilai-nilai dalam input untuk membuat array kembali.

Solusi yang valid harus:

  • Terima array elemen-nol dan kembalikan array kosong.
  • Terima array integer dengan panjang n dan kembalikan array integer
    • Panjang antara n dan daya tertinggi berikutnya 2 minus 1. (misalnya, untuk ukuran input 13 kembali di mana saja antara 13 dan 15).
    • Array yang mewakili BST di mana simpul akar berada di posisi 0 dan tingginya sama dengan log (n) di mana 0 mewakili simpul yang hilang (atau nullnilai -seperti jika bahasa Anda memungkinkan). Node kosong, jika ada, harus hanya ada di ujung pohon (misalnya, [2,1,0])

Array integer input memiliki jaminan berikut:

  • Nilai adalah bilangan bulat bertanda 32-bit yang lebih besar dari nol.
  • Nilai unik.
  • Nilai berada dalam urutan menaik dari posisi nol.
  • Nilai mungkin jarang (yaitu, tidak berdekatan satu sama lain).

Kode paling singkat menurut jumlah karakter ascii menang, tapi saya juga tertarik melihat solusi elegan untuk bahasa tertentu.

Uji kasus

Output untuk array sederhana yang berisi 1untuk nuntuk berbagai n. Seperti dijelaskan di atas, trailing 0s adalah opsional.

[]
[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
sumber
Semua pertanyaan di situs ini, apakah teka-teki pemrograman atau kode golf, harus memiliki kriteria pemenang utama yang objektif, sehingga dimungkinkan untuk memutuskan entri mana yang harus dimenangkan.
Howard
@Howard, terima kasih. Diperbarui dengan kriteria definitif untuk pemenang.
Jake Wharton
1
Akan sangat berguna untuk memiliki beberapa kasus uji yang mencakup kasus-kasus sulit, daripada (seperti saat ini) yang paling mudah.
Peter Taylor
Apakah ada alasan untuk mengesampingkan rekursi? Bukannya saya sedang mencari solusi rekursif, tapi itu sepertinya buatan dan tidak perlu.
dmckee --- ex-moderator kitten
1
Adakah yang bisa menjelaskan bagaimana daftar ini mewakili BST?
justinpc

Jawaban:

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

Ini adalah (secara longgar) versi terkompresi dari kode berikut yang pada dasarnya melakukan BFS di pohon.

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)

Selain itu, karena BFS, bukan DFS, persyaratan solusi non-rekursif tidak signifikan, dan menempatkan beberapa bahasa pada posisi yang kurang menguntungkan.

Sunting: Solusi tetap, terima kasih kepada @PeterTaylor untuk komentarnya!

dtldarek
sumber
@PeterTaylor Tujuannya adalah untuk meletakkan 3 di sebelah kiri 4, tetapi tidak ada yang kosong, jadi itu salah. Terima kasih telah menunjukkan itu!
dtldarek
@PeterTaylor Memperbaiki makan siang, seharusnya sudah berfungsi sekarang.
dtldarek
4

Jawa , 252

Ok, ini usahaku. Saya telah bermain-main dengan operasi bit dan saya datang dengan cara langsung menghitung indeks elemen dalam BST dari indeks dalam array asli.

Versi terkompresi

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

Versi panjangnya mengikuti di bawah ini.

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;
}
syekh mikail
sumber
Anda memerlukan jumlah karakter, dan saat ini tidak ada golf.
dmckee --- ex-moderator kitten
@dmckee Saya telah mengedit posting untuk menyertakan versi terkompresi dan jumlah karakter
mikail sheikh
Pertunjukan yang bagus. Saya berani bertaruh bahwa beberapa ruang itu tidak perlu. Dalam c, int[] b(int[] a)diekspresikan juga int[]b(int[]a).
dmckee --- ex-moderator kitten
Anda memiliki a.lengthalokasi array. Ubah ke s. Singkirkan ruang antara for (beberapa kali. Masing-masing untuk loop menciptakan int i=0dan juga int t=0. Buat dengan n( int n=0,i,t;) dan kemudian hanya i=0di loop dan t=1di dalam. Deklarasikan bagian dalam long xdan long Idengan sdan baru saja diinisialisasi dalam loop ( long s=a.length,I,x;dan x=../ I=..). Anda seharusnya tidak memerlukan spasi di sekitar biner DAN &.
Jake Wharton
Juga, I=I|..dapat ditulisI|=..
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
sumber
2

Tidak yakin apakah ini cocok dengan kebutuhan Anda akan node kosong berada di ujung pohon dan itu pasti tidak akan memenangkan hadiah untuk singkatnya, tapi saya pikir itu benar dan ia memiliki test case :)

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

Golfscript ( 99 89)

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

Pada dasarnya port langsung dari solusi Python saya, bekerja dengan cara yang hampir sama.

Mungkin bisa ditingkatkan sedikit dengan lebih banyak "golfisms", sudah ditingkatkan oleh 10 karakter dengan input @ petertaylor :)

Joachim Isaksson
sumber
Saya pikir itu harus mungkin tidak lebih dari 70, meskipun saya masih belum menyelesaikan jawaban GolfScript saya. Ada beberapa perbaikan mudah untuk Anda. !{;}{}ifbisa saja !{;}*karena !jaminan untuk kembali 0atau 1. Anda dapat menggunakan token non-abjad untuk variabel, jadi jika Anda menggunakan ^bukan r, |bukan x, &bukan yAnda dapat menghilangkan semua spasi itu.
Peter Taylor
@PeterTaylor Terima kasih, tidak tahu tentang variabel non alfanumerik, masih sangat baru untuk skrip golf :)
Joachim Isaksson
2

Jawa 192

Indeks peta di input ke indeks di output

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

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

Fungsi ini g[l]mengambil input a List(misalnya l={1,2,3,4,...}) dan mengembalikan a Listdari bentuk yang diinginkan. Ia bekerja sebagai berikut:

  • x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2) mengambil daftar dan menemukan akar BST terkait.
    • i=Length[a]+1 pintas untuk panjang daftar
    • 2^Ceiling@Log2[i]/2 batas atas pada nilai root
    • Min[i-#/2,#]&@(...)Minimal dari dua argumen di mana #singkatan dari apa yang ada di dalam(...)
  • l//.{...} Terapkan berulang kali aturan penggantian yang diikuti l
  • {}->{} Tidak ada yang dilakukan (ini adalah tepi kasus untuk menghindari loop tak terbatas)
  • b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])Membagi Listmenjadi{{lesser}, root, {greater}}
  • Cases[...,_Integer,{m}] Ambil semua bilangan bulat di level (kedalaman) m
  • Table[...,{m,1,x[l]}]Untuk semua msampai dengan x[l](yang lebih dari yang diperlukan sebenarnya).

Itu bisa diuji dengan menjalankan

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

Implementasi ini tidak termasuk trailing zero.

MannyC
sumber
1

Python ( 175 171)

Cukup padat, masih cukup mudah dibaca;

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

Ini menghasilkan hasilnya kembali, sehingga Anda dapat mengulanginya atau (untuk tujuan tampilan) mencetaknya sebagai daftar;

>>> 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
sumber
@ dtldarek Komentarnya sepertinya sudah dihapus, tapi ini sepertinya lolos dari ujian sekarang.
Joachim Isaksson
Saya menghapus komentar saya agar orang tidak menahan jawaban @ dtldarek karena komentar yang mengatakan itu buggy.
Peter Taylor
@ PeterTaylor Baiklah, terima kasih atas pertimbangan Anda ;-)
dtldarek
1

Jawa

Ini adalah solusi perhitungan langsung. Saya pikir itu berhasil, tetapi memiliki satu efek samping yang pragmatis tidak berbahaya. Array yang dihasilkannya mungkin rusak tetapi tidak dengan cara apa pun yang akan memengaruhi pencarian. Alih-alih menghasilkan 0 (null) node, itu akan menghasilkan node yang tidak dapat dijangkau, yaitu node yang sudah ditemukan sebelumnya di pohon selama pencarian. Ia bekerja dengan memetakan larik indeks kekuatan reguler 2 susunan pohon pencarian biner ke susunan pohon pencarian biner berukuran tidak teratur. Setidaknya, saya pikir itu berhasil.

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

}

Ini versi yang lebih ringkas (hanya fungsi dan nama yang dipasangkan). Masih ada ruang putih, tapi saya tidak khawatir menang. Versi ini juga membutuhkan array. Yang lain hanya mengambil int untuk indeks tertinggi dalam array.

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;
}
metafisis
sumber
Karena ini adalah kode-golf , persingkat metode / nama / etc Anda sesingkat mungkin; hapus semua spasi putih (dan metode / materi yang tidak perlu), dan masukkan jumlah karakter. Jika tidak, Anda baik-baik saja.
Justin
@ Jake Wharton. Saya benar-benar ingin melihat solusi pemetaan langsung Anda. Saya bukan 100% yakin tambang bekerja untuk array yang sangat besar karena bergantung pada pemetaan matematika terus menerus yang nilainya dibulatkan. Tampaknya memang berhasil, tetapi saya tidak yakin bagaimana membuktikannya.
metafisis
1

GolfScript ( 79 77 70 karakter)

Karena contoh dalam pertanyaan menggunakan fungsi, saya membuat fungsi ini. Menghapus {}:f;untuk meninggalkan ekspresi yang mengambil input pada stack dan meninggalkan BST pada stack akan menghemat 5 karakter.

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

Demo online (catatan: aplikasi mungkin butuh sedikit pemanasan: waktunya habis untuk saya sebelum berjalan dalam 3 detik).

Dengan spasi untuk menampilkan struktur:

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

J , 52 byte

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

fungsi mengambil daftar yang diurutkan dan mengembalikan dalam urutan pohon biner

perhatikan bahwa pohon memiliki bentuk yang identik tetapi level bawahnya lebih pendek

  • `1: mulai dengan 1
  • <.@(2&^.)@>:@# beralih dengan lantai log2 (panjang + 1)
  • +: , >:@+:@i.@>:@# loop: menambahkan dua kali lipat dari vektor terakhir dengan angka ganjil 1,3 .. 2 * panjang + 1
  • # /:@{. hanya ambil jumlah item yang diperlukan dan dapatkan indeks sortirnya
  • /: terapkan indeks semacam itu ke input yang diberikan

TIO

jayprich
sumber
0

Python 2 , 107 byte

Golf dari jawaban Joachim Isaksson , Input adalah singleton yang berisi daftar.

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

Cobalah online!

ovs
sumber