Tulislah Program Tersingkat Untuk Memeriksa Apakah Pohon Biner Seimbang

15

Untuk setiap simpul dalam pohon biner seimbang, perbedaan maksimum dalam ketinggian subtree anak kiri dan subtree anak kanan paling banyak 1.

Ketinggian pohon biner adalah jarak dari simpul akar ke simpul anak yang paling jauh dari akar.

Di bawah ini adalah contohnya:

           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4 

Tinggi pohon biner: 4

Berikut ini adalah pohon biner dan laporan tentang apakah mereka seimbang atau tidak:

Test Case 1

Pohon di atas tidak seimbang .

Test Case 2

Pohon di atas seimbang .

Tuliskan program sesingkat mungkin yang menerima sebagai input root dari pohon biner dan mengembalikan nilai falsey jika pohon itu tidak seimbang dan nilai yang benar jika pohon itu seimbang.

Memasukkan

Akar pohon biner. Ini mungkin dalam bentuk referensi ke objek root atau bahkan daftar yang merupakan representasi yang valid dari pohon biner.

Keluaran

Mengembalikan nilai kebenaran: Jika pohon seimbang

Mengembalikan nilai falsey: Jika pohon tidak seimbang.

Definisi Pohon Biner

Sebuah pohon adalah objek yang berisi nilai dan dua pohon lain atau pointer ke sana.

Struktur pohon biner terlihat seperti berikut:

typedef struct T
{
   struct T *l;
   struct T *r;
   int v;
}T;

Jika menggunakan representasi daftar untuk pohon biner, itu mungkin terlihat seperti berikut ini:

[root_value, left_node, right_node]
T. Salim
sumber
2
Bolehkah input berupa pohon kosong?
tsh
1
Dalam contoh awal Anda tentang pohon, jika Anda menghilangkan daun 4, apakah pohon yang tersisa seimbang?
Neil
Tidak, bukan contoh itu, maksud saya yang pertama, menggunakan seni ASCII.
Neil
Menurut implementasi saya sendiri "C, 117 byte": Tidak, karena ketinggian pohon subarm kanan mulai dari "5" adalah 2 dan tinggi pohon subarm kiri adalah 0
T. Salim
Suntingan setidaknya 6 karakter tetapi tolong hapus koma dari antara 'seimbang' dan 'biner' - 'pohon biner' adalah frasa kata benda, jadi menulis 'pohon biner seimbang' setara dengan 'merah, salju ponsel' - the tidak diperlukan koma.
Geza Kerecsenyi

Jawaban:

8

Jelly , 11 byte

ḊµŒḊ€IỊ;߀Ạ

Cobalah online!

Pohon kosong diwakili oleh [].

Erik the Outgolfer
sumber
Terima kasih Erik untuk menjadi yang pertama menjawab pertanyaan ini. Jelly tentunya adalah bahasa yang sangat populer di situs ini. Saya pikir saya harus mengambil kebebasan untuk mengimplementasikan bahasa ini. Bagus untuk belajar dari bahasa skrip golf yang kuat.
T. Salim
Selamat Erik the Outgolfer, Anda adalah pemenangnya.
T. Salim
3

Prolog (SWI) , 49 byte

N+_/B/C:-X+B,Y+C,abs(X-Y)<2,N is max(X,Y)+1.
0+e.

Cobalah online!

Merupakan pohon sebagai Value/Left_Child/Right_Child, dengan pohon kosong menjadi atom e. Menentukan +/2, yang menghasilkan melalui keberhasilan atau kegagalan, dengan variabel tidak terikat (atau yang sudah sama dengan tinggi pohon) di sebelah kiri dan pohon di sebelah kanan - jika argumen ketinggian tidak dapat diterima, tambahkan 9 byte untuk didefinisikan -T:-_+T..

N + _/B/C :-            % If the second argument is a tree of the form _Value/B/C,
    X+B,                % X is the height of its left child which is balanced,
    Y+C,                % Y is the height of its right child which is balanced,
    abs(X-Y) < 2,       % the absolute difference between X and Y is strictly less than 2,
    N is max(X,Y)+1.    % and N is the height of the full tree.
0 + e.                  % If, on the other hand, the second argument is e, the first is 0.
String yang tidak terkait
sumber
(Jika nilai setiap node dapat dihilangkan dari input, _/dapat diambil untuk -2 bytes.)
Unrelated String
3

Bahasa Wolfram (Mathematica) , 50 byte

f@_[x_,y_]:=f@x&&f@y&&-2<Depth@x-Depth@y<2;f@_=1>0

Gunakan Nulluntuk null, value[left, right]untuk node. Sebagai contoh, pohon berikut ini ditulis sebagai 2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]].

    2
   / \
  7   5
 / \   \
2   6   9
   / \  /
  5  11 4

Cobalah online!

alephalpha
sumber
Itu sangat cantik!
Greg Martin
3

Python 3.8 (pra-rilis) , 133 125 byte

b=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1)
h=lambda t:b(t)[1]

Cobalah online!

Mengambil pohon dalam format "daftar": Node [value, left, right]dengan leftdan rightmenjadi node.

Meminta fungsi h.

Pengembalian 0atau Falseuntuk pohon yang tidak seimbang. Pengembalian 1atau Trueuntuk pohon seimbang.

Tidak Terkumpul:

# Returns tuple (current height, subtrees are balanced (or not))
def balanced(tree):
  if tree: # [] evaluates to False
    left = balanced(tree[1])
    right = balanced(tree[2])
    # If  the subtrees are not both balanced, nothing to do, just pass it up
    if left[1] and right[1]:
      height = max(left[0], right[0]) + 1
      subtrees_balanced = abs(left[0] - right[0]) < 2
    else:
      height = 0 # Value doesn't matter, will be ignored
      subtrees_balanced = False
  else:
    height = 0
    subtrees_balanced = True
  return (height, subtrees_balanced)

def h(tree):
  return balanced(tree)[1]

-10: Logika terbalik untuk menghilangkan nots

Jika mengambil argumen di tengah panggilan diperbolehkan, ini bisa disingkat menjadi (115 byte)

(b:=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1))(_)[1]

dengan _menjadi pohon untuk diperiksa.

ar4093
sumber
3

JavaScript (Node.js) , 49 byte

h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1

Cobalah online!

-9 byte oleh Arnauld.


JavaScript, 58 byte

h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1

Cobalah online!

Gunakan []untuk null, dan [left, right, value]untuk node.

tsh
sumber
2

JavaScript, 162 byte

f=x=>{for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1];if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}return 1}

Cobalah online!

Format input adalah objek

root={a:{node},b:{node},c:value}

Penjelasan

for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1]

Melakukan pencarian luas pertama menemukan kedalaman node pertama yang hilang satu atau lebih cabang.

if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}

Melanjutkan pencarian pertama yang lebarnya, mengembalikan nol jika ada elemen dua lebih dalam dari kedalaman simpul pertama yang hilang cabang.

return 1}

Jika tidak ada simpul yang ditemukan, kembalikan 1

fəˈnɛtɪk
sumber
1
Mungkin ada beberapa cara untuk melakukan pencarian pertama yang lebih luas tetapi saya tidak bisa memikirkannya.
fəˈnɛtɪk
1
Saya pikir ini gagal untuk beberapa kasus yang valid seperti contoh pertama yang harus seimbang ketika Anda menghapus daun 4.
Neil
1

Julia, 56 byte

f(t)=t!=()&&(-(f.(t.c)...)^2<2 ? maximum(f,t.c)+1 : NaN)

Dengan struct berikut mewakili pohon biner:

struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

c adalah tuple yang mewakili node kiri dan kanan dan tuple kosong () digunakan untuk memberi sinyal tidak adanya node.

Nilai Falsey adalah NaN, bilangan bulat apa pun adalah benar.

pengguna3263164
sumber
1
Dengan asumsi pengkodean adalah UTF-8, ini sebenarnya 57 byte karena , menurut penghitung byte bawaan TIO . Bagaimanapun, selamat datang di CG&CC!
String Tidak Terkait
1
Ya kau benar. Saya memperbaikinya, sehingga sekarang sebenarnya 56 byte
user3263164
0

Kotlin , 67 byte

fun N.c():Int=maxOf(l?.c()?:0,r?.c()?:0)+1
fun N.b()=l?.c()==r?.c()

Dimana

data class N(val l: N? = null, val r: N? = null, val v: Int = 0)

Cobalah online!

Brojowski
sumber
0

C, 117 byte

h(T*r){r=r?1+h(h(r->l)>h(r->r)?r->l:r->r):0;}b(T*r){return r->l&&!b(r->l)||r->r&&!b(r->r)?0:abs(h(r->l)-h(r->r))<=1;}

Implementasi struktur adalah sebagai berikut:

 typedef struct T
    {
        struct T * l;

        struct T * r;

        int v;

    } T;

Coba ini di JDoodle

T. Salim
sumber
Ini tampaknya 117 byte, meskipun Anda dapat melakukan <2pemeriksaan terakhir sebagai gantinya
Jo King
Juga, saya tidak yakin seberapa valid ini, karena ini bergantung pada struktur data yang ditentukan di luar pengajuan
Jo King
0

Python 2 , 99 96 94 byte

lambda A:A==[]or(abs(D(A[1])-D(A[2]))<2)*f(A[1])*f(A[2])
D=lambda A:A>[]and-~max(map(D,A[1:]))

Cobalah online!

3 byte dari Jo King .

Mengambil input sebagai: node kosong [], dan node lainnya [<value>, <leftNode>, <rightNode>]. Output 0/1untuk False / True.

Chas Brown
sumber