Tasodifiy rekursiv daraxt - Random recursive tree

Yilda ehtimollik nazariyasi, a tasodifiy rekursiv daraxt a ildiz otgan daraxt tanlangan bir xil tasodifiy dan rekursiv daraxtlar berilgan tepaliklar soni bilan.

Ta'rif va avlod

Bilan rekursiv daraxtda ${ displaystyle n}$ tepaliklar, tepaliklar raqamlari bilan belgilanadi ${ displaystyle 1}$ ga ${ displaystyle n}$va yorliqlar daraxt ildiziga o'tadigan har qanday yo'l bo'ylab kamayishi kerak. Ushbu daraxtlar tartibsizdir, chunki har bir tepalikning bolalarida alohida tartib yo'q. Tasodifiy rekursiv daraxtda bunday daraxtlarning barchasi bir xil ehtimolga ega.

Shu bilan bir qatorda, tasodifiy rekursiv daraxtni bitta vertikadan, daraxtning ildizidan boshlab, yaratilishi mumkin. ${ displaystyle 1}$va keyin har bir ketma-ket yorliq uchun ${ displaystyle 2}$ ga ${ displaystyle n}$ uning ota-onasi bo'lish uchun kichikroq yorliqli tasodifiy vertikani tanlash. Agar tanlovlarning har biri bir xil bo'lsa va boshqa tanlovlardan mustaqil bo'lsa, natijada hosil bo'lgan daraxt tasodifiy rekursiv daraxt bo'ladi.

Xususiyatlari

Katta ehtimollik bilan ildizdan an bargiga qadar eng uzun yo'l ${ displaystyle n}$-vertex tasodifiy rekursiv daraxti uzunlikka ega ${ displaystyle e log n}$.^[1]Daraxtdagi har qanday tepalikdagi bolalarning maksimal soni, ya'ni daraja, katta ehtimollik bilan, ${ displaystyle (1 pm o (1)) log _ {2} n}$.^[2]The kutilgan masofa ${ displaystyle k}$Ildizning yuqorigi qismi - bu ${ displaystyle k}$th harmonik raqam, undan kelib chiqadigan narsa kutishning lineerligi barcha vertikal yo'l uzunliklari yig'indisi katta ehtimollik bilan, ${ displaystyle (1 pm o (1)) n log n}$.^[3]Daraxtning kutilgan barglari soni ${ displaystyle n / 2}$ bilan dispersiya ${ displaystyle n / 12}$, shuning uchun katta ehtimollik bilan barglar soni ${ displaystyle (1 pm o (1)) n / 2}$.^[4]

Ilovalar

Chjan (2015) modellashtirish hodisalarida tasodifiy rekursiv daraxtlarning bir nechta qo'llanilishini, shu jumladan kasallik tarqalishini, piramida sxemalari, tillarning rivojlanishi va kompyuter tarmoqlarining o'sishi.^[4]

Adabiyotlar