Jumlah kemungkinan jalur pencarian saat mencari di BST

Saya punya pertanyaan berikut, tetapi tidak punya jawaban untuk ini. Saya akan sangat menghargai jika metode saya benar:

Q. Saat mencari nilai kunci 60 dalam pohon pencarian biner, node yang berisi nilai kunci 10, 20, 40, 50, 70, 80, 90 dilintasi, tidak harus dalam urutan yang diberikan. Berapa banyak pesanan berbeda yang memungkinkan di mana nilai-nilai kunci ini dapat terjadi pada jalur pencarian dari simpul akar yang berisi nilai 60?

(A) 35 (B) 64 (C) 128 (D) 5040

Dari pertanyaan itu, saya mengerti bahwa semua node yang diberikan harus dimasukkan dalam traversal dan pada akhirnya kita harus mencapai kunci, 60. Misalnya, satu kombinasi tersebut adalah:

10, 20, 40, 50, 90, 80, 70, 60.

Karena kita harus melintasi semua node yang diberikan di atas, kita harus mulai dengan 10 atau 90. Jika kita mulai dengan 20, kita tidak akan mencapai 10 (karena 60> 20 dan kita akan melintasi subtree kanan 20)

Demikian pula, kita tidak dapat memulai dengan 80, karena kita tidak akan dapat mencapai 90, karena 80> 60, kita akan melintasi sub pohon kiri 80 & dengan demikian tidak mencapai 90.

Mari kita ambil 10. Node yang tersisa adalah 20, 40, 50, 70, 80, 90. Node selanjutnya bisa 20 atau 90. Kita tidak bisa mengambil node lain karena alasan yang disebutkan sebelumnya sama.

Jika kita mempertimbangkan hal yang sama, pada setiap level kita memiliki dua pilihan. Karena ada 7 node, dua pilihan untuk 6 pertama & tidak ada pilihan untuk yang terakhir. Jadi benar-benar ada

$2*2*2*2*2*2*1$ permutasi = = $2^6$ $64$

Apakah ini jawaban yang benar?
Jika tidak, apa pendekatan yang lebih baik?
Saya ingin menggeneralisasi. Jika node diberikan maka total jalur pencarian yang mungkin adalah $n$ $2^{n-1}$

data-structures combinatorics binary-trees search-trees graph-traversal avi
sumber

Jawaban:

Jika mencari kunci 60 kita mencapai sejumlah kurang dari 60, kita pergi kanan (di mana angka-angka yang lebih besar) dan kami tidak pernah bertemu nomor kurang dari . Argumen itu dapat diulang, sehingga angka 10, 20, 40, 50 harus muncul di sepanjang pencarian dalam urutan itu. $K$ $K$

Demikian pula, jika mencari kunci 60 kita mencapai jumlah yang lebih besar dari 60, kita pergi leftt (di mana angka-angka yang lebih kecil) dan kami tidak pernah nomor bertemu lebih besar dari . Karenanya angka 90, 80, 70 harus terjadi di sepanjang pencarian dalam urutan itu. $K$ $K$

Urutan 10, 20, ~~30,~~ 40, 50 dan 90, 80, 70 kemudian dapat dikocok bersama, selama urutannya tetap utuh. Dengan demikian kita dapat memiliki 10, 20, 40, 50, 90, 80, 70, tetapi juga 10, 20, 90, 30, 40, 80, 70, 50.

Kita sekarang dapat menghitung angka, memilih posisi angka besar dan kecil. Lihat komentar oleh Aryabhata. Kami memiliki dua urutan 4 dan 3 angka. Berapa banyak cara yang bisa saya kocok? Dalam 7 posisi akhir saya harus memilih 3 posisi untuk angka yang lebih besar (dan 4 posisi sisanya untuk angka yang lebih kecil). Saya dapat memilih ini dalam cara. Setelah memperbaiki posisi ini kita tahu urutan lengkapnya. Misalnya, contoh pertama saya memiliki posisi SSSSLLL yang kedua memiliki SSLSLL S. $7 \choose 3$

Anda meminta generalisasi. Selalu angka kurang dari angka yang ditemukan, dan angka lebih besar ditetapkan dalam urutan relatifnya. Angka yang lebih kecil harus naik, angka arger harus turun. Jumlahnya kemudian . $x$ $y$ $x+y \choose y$

PS (diedit). Terima kasih kepada Gilles, yang mencatat bahwa 30 tidak ada dalam pertanyaan.

Hendrik Jan
sumber

Saya pasti ingin mencoba. Karena no.s 90,80,70 harus bersama, mari kita anggap mereka sebagai no tunggal. dan itu dapat ditempatkan di antara 6 tempat: _ 10 _ 20 _ 30 _ 40 _ 50 _ Jadi itu Jika dengan analogi yang sama, no.s [10,20,30,40,50] dapat ditempatkan di 4 tempat, itu Tapi itu harus dibagi dengan kombinasi umum yang terjadi (yang saya tidak bisa mengetahuinya)

2^{6}

$2^6$

2^{4}

$2^4$

avi

@ Iavi Tidak, mereka tidak harus bersama, hanya dalam urutan: 10, 20, 90, 30, 40, 80, 70, 50 tidak apa-apa.

Hendrik

@avi: Coba pikirkan seperti ini: Besar dan Kecil. Sekarang Anda memiliki 8 tempat, dengan 5 Kecil dan 3 Besar. Bagaimana Anda mengisinya? 8 pilih 3. Yang datang ke 56, dan saya kira itu yang didapat Hendrik juga.

Aryabhata

@ HendrikJan Tidak ada 30 dalam pertanyaan asli, hanya ada 7 nilai. Dan 7 pilih 3 adalah (A).

Gilles 'SO- stop being evil'

@ HendrikJan - dapatkah Anda menjelaskan hal ini kepada saya: Selalu angka kurang dari angka yang ditemukan, dan angka lebih besar diperbaiki dalam urutan relatifnya

x

$x$

y

$y$

avi

Kami akan mengonversi Pindah ke Teks. Diberikan bahwa Selama Pencarian kami telah melintasi node ini

karena dapat dilihat bahwa yang Merah lebih besar dari 60 dan yang biru lebih kecil dari 60.

Path ke node 60 telah melibatkan node tersebut. Jadi, salah satu solusi yang mungkin untuk masalah ini adalah solusi lain hanya akan berisi gerakan ini. karena pada suatu waktu pada sebuah node kita bisa mendapatkan arah sebagai S atau L pada perbandingan dan karena itu diberikan bahwa node itu ditemui itu berarti arah diambil dari set itu.

{S, S, S, S, L, L, L}

$\{S,S,S,S,L,L,L\}$

Karenanya, jumlah total solusi yang mungkin = semua Permutasi dari set itu, yang diberikan oleh answer = opsi A

\frac{7!}{4! \times 3!} = 35

$\frac{7!}{4! \times 3!} = 35$

amarVashishth
sumber