شجرة ثنائية عشوائية

في علوم الحاسوب ونظرية الاحتمالات ، تُعرَّف الشجرة الثنائية العشوائية بأنها شجرة ثنائية مختارة عشوائيًا من توزيع احتمالي معين على الأشجار الثنائية. وقد استُخدمت توزيعات مختلفة، مما أدى إلى خصائص مختلفة لهذه الأشجار.

تُستخدم الأشجار الثنائية العشوائية لتحليل تعقيد الحالة المتوسطة لهياكل البيانات القائمة على أشجار البحث الثنائية . في هذا التطبيق، من الشائع استخدام أشجار عشوائية تُشكّل بإضافة عقدة تلو الأخرى وفقًا لتبديل عشوائي . ^{[ 1 ]} من المرجح أن يكون للأشجار الناتجة عمق لوغاريتمي ورقم ستراهلر لوغاريتمي . تستخدم شجرة البحث الثنائية المتوازنة treap وما يرتبط بها عمليات تحديث تحافظ على هذا الهيكل العشوائي حتى عندما يكون تسلسل التحديث غير عشوائي.

تشمل التوزيعات الأخرى على الأشجار الثنائية العشوائية التوزيع المنفصل المنتظم الذي تكون فيه جميع الأشجار المتميزة متساوية الاحتمالية، والتوزيعات على عدد معين من العقد التي يتم الحصول عليها عن طريق التقسيم المتكرر، والأشجار الثنائية وأشجار الجذر للبيانات العشوائية، والأشجار ذات الحجم المتغير التي يتم إنشاؤها بواسطة عمليات التفرع .

للاطلاع على الأشجار العشوائية التي ليست بالضرورة ثنائية، انظر الشجرة العشوائية .

الشجرة الثنائية هي شجرة جذرية، حيث يمكن أن تحتوي كل عقدة على ما يصل إلى عقدتين فرعيتين (العقدتان اللتان تقعان أسفلها مباشرةً في الشجرة)، وتُصنف هاتان العقدتان الفرعيتان إما إلى عقدة يسارية أو عقدة يمينية. في بعض الأحيان، يكون من الأنسب النظر إلى الأشجار الثنائية الممتدة، حيث تكون كل عقدة إما عقدة خارجية بدون عقد فرعية، أو عقدة داخلية بعقدتين فرعيتين فقط. يمكن تحويل الشجرة الثنائية غير الممتدة إلى شجرة ثنائية ممتدة بمعاملة جميع عقدها كعقد داخلية، وإضافة عقدة خارجية لكل عقدة فرعية مفقودة من عقدة داخلية. وبالعكس، يمكن تحويل الشجرة الثنائية الممتدة التي تحتوي على عقدة داخلية واحدة على الأقل إلى شجرة ثنائية غير ممتدة بإزالة جميع عقدها الخارجية. وبهذه الطريقة، يكون هذان الشكلان متكافئين تقريبًا لأغراض التحليل الرياضي، باستثناء أن الشكل الممتد يسمح بوجود شجرة تتكون من عقدة خارجية واحدة، وهو ما لا يقابله أي شيء في الشكل غير الممتد. أما لأغراض هياكل بيانات الحاسوب، فيختلف الشكلان، حيث يمكن تمثيل العقد الخارجية في الشكل الأول صراحةً ككائنات في بنية البيانات. ^{[ 2 ]}

في شجرة البحث الثنائية، تُرقّم العقد الداخلية بأرقام أو قيم مرتبة أخرى تُسمى المفاتيح ، بحيث يُرتب اجتياز الشجرة ترتيبًا تصاعديًا لعرض هذه المفاتيح. أما العقد الخارجية فتبقى بدون ترقيم. ^{[ 3 ]} يمكن أيضًا دراسة الأشجار الثنائية مع ترك جميع العقد بدون ترقيم، أو مع ترقيم غير تصاعدي. على سبيل المثال، تستخدم بنية بيانات الشجرة الديكارتية أشجارًا ثنائية مرقمة، وهي ليست بالضرورة أشجار بحث ثنائية. ^{[ 4 ]}

الشجرة الثنائية العشوائية هي شجرة عشوائية مُستمدة من توزيع احتمالي مُحدد على الأشجار الثنائية. في كثير من الحالات، تُحدد هذه التوزيعات الاحتمالية باستخدام مجموعة مُعينة من المفاتيح، وتصف احتمالات احتواء أشجار البحث الثنائية على تلك المفاتيح. مع ذلك، توجد توزيعات أخرى ممكنة، لا تُولد بالضرورة أشجار بحث ثنائية، ولا تُعطي بالضرورة عددًا ثابتًا من العُقد. ^{[ 5 ]}

لأي تسلسل من المفاتيح المرتبة المختلفة، يمكن إنشاء شجرة بحث ثنائية حيث يُدرج كل مفتاح في التسلسل كطرف من أطراف الشجرة، دون تغيير بنية المفاتيح المُدرجة سابقًا. ويمكن إيجاد موضع كل إدراج من خلال بحث ثنائي في الشجرة السابقة. أما نموذج التبديل العشوائي ، لمجموعة معينة من المفاتيح، فيُعرَّف باختيار التسلسل عشوائيًا من بين تباديل المجموعة، مع تساوي احتمالية كل تبديل. ^{[ 6 ]}

على سبيل المثال، إذا أُدخلت المفاتيح الثلاثة 1 و3 و2 في شجرة بحث ثنائية بهذا الترتيب، فسيكون الرقم 1 في جذر الشجرة، والرقم 3 في ابنه الأيمن، والرقم 2 في ابنه الأيسر. توجد ستة تباديل مختلفة للمفاتيح 1 و2 و3، ولكن لا يمكن إنشاء سوى خمس أشجار منها. ذلك لأن التباديل 2 و1 و3 و2 و3 و1 تُشكل الشجرة نفسها. وبالتالي، فإن احتمال هذه الشجرة هو${\displaystyle {\tfrac {2}{6}}={\tfrac {1}{3}}}$من حيث التوليد، بينما لكل من الأشجار الأربع الأخرى احتمالية${\displaystyle {\tfrac {1}{6}}}$[ ^{5 ]​}

أطول مسار

أطول مسار من الجذر إلى الورقة، في شجرة بحث ثنائية عشوائية، أطول من طول المسار المتوقع، ولكن بمعامل ثابت فقط. طوله، بالنسبة لشجرة ذات${\displaystyle n}$العقد، باحتمالية عالية تقريبًا

${\displaystyle \displaystyle {\frac {1}{\beta }}\log n\approx 4.311\log n,}$

أين${\displaystyle \beta }$هو الرقم الفريد في النطاق${\displaystyle 0<\beta <1}$تحقيق المعادلة

${\displaystyle \displaystyle 2\beta e^{1-\beta }=1.}$^{[ 8 ]}

عدد الأشجار الثنائية التي${\displaystyle n}$العقدة هي رقم كاتالاني . ^{[ 13 ]} لـ${\displaystyle n=1,2,3,\dots }$هذه الأعداد من الأشجار هي

وبالتالي، إذا تم اختيار إحدى هذه الأشجار عشوائيًا وبشكل منتظم، فإن احتمالها يساوي مقلوب عدد كاتالان. تُسمى الأشجار المُولَّدة من نموذج في هذا التوزيع أحيانًا بأشجار كاتالان الثنائية العشوائية . ^{[ 14 ]} ولها عمق متوقع يتناسب مع الجذر التربيعي لـ${\displaystyle n}$بدلاً من اللوغاريتم. ^{[ 15 ]} وبشكل أدق، العمق المتوقع لعقدة مختارة عشوائياً في${\displaystyle n}$شجرة العقدة من هذا النوع هي

${\displaystyle {\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)}$[ ^{16 ]​}

العدد المتوقع لستراهلر لتوزيع عشوائي منتظم${\displaystyle n}$الشجرة الثنائية ذات العقدة هي${\displaystyle \log _{4}n+O(1)}$، أقل من عدد ستراهلر المتوقع لأشجار البحث الثنائية العشوائية. ^{[ 17 ]}

نظراً لارتفاعها الكبير، لا يُستخدم هذا النموذج من الأشجار العشوائية متساوية الاحتمالية عموماً في أشجار البحث الثنائية. ومع ذلك، له تطبيقات أخرى، منها:

• نمذجة أشجار تحليل التعبيرات الجبرية في تصميم المترجمات . ^{[ 18 ]} تمثل العقد الداخلية للشجرة العمليات الثنائية في التعبير، بينما تمثل العقد الخارجية المتغيرات أو الثوابت التي تُجرى عليها هذه التعبيرات. ويُترجم الحد الأقصى لعدد ستراهلر إلى عدد المسجلات اللازمة لتقييم التعبير. ^{[ 19 ]}
• نمذجة شبكات الأنهار ، وهو التطبيق الأصلي الذي طُوِّر من أجله رقم ستراهلر. ^{[ 20 ]}
• نمذجة الأشجار التطورية المحتملة لعدد ثابت من الأنواع. في هذا التطبيق، يتم استخدام شجرة ثنائية موسعة، مع وجود الأنواع عند عقدها الخارجية. ^{[ 21 ]}

تُنشئ خوارزمية جان لوك ريمي شجرة ثنائية عشوائية منتظمة بحجم مُحدد في زمن خطي يتناسب مع الحجم، وذلك باتباع الخطوات التالية: ابدأ بشجرة تتكون من عقدة خارجية واحدة. ثم، طالما لم تصل الشجرة الحالية إلى الحجم المستهدف، اختر بشكل متكرر إحدى عقدها (داخلية أو خارجية) عشوائيًا. استبدل العقدة المختارة بعقدة داخلية جديدة، بحيث تكون العقدة المختارة أحد أبنائها (باحتمالية متساوية بين اليسار واليمين)، ويكون الابن الآخر عقدة خارجية جديدة. توقف عند الوصول إلى الحجم المستهدف. ^{[ 22 ]}

تصف عملية غالتون -واتسون مجموعة من التوزيعات على الأشجار حيث يتم اختيار عدد الأبناء في كل عقدة عشوائيًا، بشكل مستقل عن العقد الأخرى. بالنسبة للأشجار الثنائية، يُستخدم إصداران من عملية غالتون-واتسون، ويختلفان فقط في ما إذا كان يُسمح بشجرة ثنائية موسعة ذات عقدة واحدة فقط، وهي عقدة الجذر الخارجية.

• في النسخة التي قد تكون فيها العقدة الجذرية خارجية، يتم اختيارها لتكون داخلية باحتمالية محددة.${\displaystyle p}$أو خارجي باحتمالية${\displaystyle 1-p}$إذا كان داخليًا، فإن طفليه عبارة عن شجرتين يتم إنشاؤهما بشكل متكرر بواسطة نفس العملية.
• في النسخة التي يجب أن تكون فيها العقدة الجذرية داخلية، يتم تحديد أن أبناءها الأيسر والأيمن داخليون باحتمالية${\displaystyle p}$أو خارجي باحتمالية${\displaystyle 1-p}$بشكل مستقل عن بعضها البعض. في حالة كونها داخلية، فإنها تمثل جذور الأشجار التي يتم إنشاؤها بشكل متكرر بواسطة نفس العملية.

تُسمى الأشجار المُولّدة بهذه الطريقة بأشجار غالتون-واتسون الثنائية . في الحالة الخاصة حيث${\displaystyle p={\tfrac {1}{2}}}$وتسمى هذه الأشجار بأشجار غالتون-واتسون الثنائية الحرجة . ^{[ 23 ]}

تحليل

الاحتمالية${\displaystyle p={\tfrac {1}{2}}}$يمثل هذا تحولاً طورياً لعملية غالتون-واتسون الثنائية: لـ${\displaystyle p\leq {\tfrac {1}{2}}}$من شبه المؤكد أن الشجرة الناتجة ستكون محدودة، بينما بالنسبة لـ${\displaystyle p>{\tfrac {1}{2}}}$إنها لانهائية باحتمالية موجبة. بتعبير أدق، لأي${\displaystyle p}$، احتمال أن تظل الشجرة محدودة هو

${\displaystyle \displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}}$[ ^{24 ]​}

هناك طريقة أخرى لتوليد نفس الأشجار وهي إجراء سلسلة من عمليات رمي ​​العملة ، باحتمالية${\displaystyle p}$عدد مرات ظهور الصورة واحتمالية ذلك${\displaystyle 1-p}$من الذيل، حتى أول رمية يتجاوز فيها عدد الذيل عدد الذيول (بالنسبة للنموذج الذي يسمح بجذر خارجي) أو يتجاوز واحدًا زائد عدد الذيول (عندما يجب أن يكون الجذر داخليًا)، ثم استخدم سلسلة رميات العملة هذه لتحديد الخيارات التي اتخذتها عملية التوليد التكرارية، بترتيب البحث العميق أولًا. ^{[ 25 ]}

لأن عدد العقد الداخلية يساوي عدد مرات ظهور الصورة في تسلسل رمي العملة هذا، فإن جميع الأشجار التي لها عدد معين${\displaystyle n}$يتم توليد عدد من العقد من تسلسلات رمي ​​العملة (الفريدة) ذات الطول نفسه، وتكون احتمالاتها متساوية، بغض النظر عن${\displaystyle p}$أي اختيار${\displaystyle p}$يؤثر ذلك على التباين في حجم الأشجار الناتجة عن هذه العملية، ولكن بالنسبة لحجم معين، يتم توليد الأشجار بشكل عشوائي منتظم. ^{[ 26 ]} بالنسبة لقيم${\displaystyle p}$أقل من الاحتمالية الحرجة${\displaystyle p={\tfrac {1}{2}}}$، قيم أصغر من${\displaystyle p}$سينتج عن ذلك أشجار ذات حجم متوقع أصغر ، بينما القيم الأكبر لـ${\displaystyle p}$سينتج أشجارًا ذات حجم متوقع أكبر. عند الاحتمال الحرج${\displaystyle p={\tfrac {1}{2}}}$لا يوجد حد أقصى لحجم الأشجار المتوقع الناتج عن هذه العملية. بتعبير أدق، لأي${\displaystyle p}$، العدد المتوقع للعقد عند العمق${\displaystyle i}$في الشجرة${\displaystyle (2p)^{i}}$ويمكن الحصول على الحجم المتوقع للشجرة عن طريق جمع الأعداد المتوقعة للعقد عند كل عمق.${\displaystyle p<{\tfrac {1}{2}}}$وهذا يعطي متسلسلة هندسية

${\displaystyle \displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}}$،

بالنسبة لحجم الشجرة المتوقع، ولكن بالنسبة لـ${\displaystyle p={\tfrac {1}{2}}}$وهذا يعطي 1 + 1 + 1 + 1 + ⋯ ، وهي متسلسلة متباعدة . ^{[ 27 ]}

ل${\displaystyle p={\tfrac {1}{2}}}$أي شجرة معينة مع${\displaystyle n}$يتم توليد العقد الداخلية باحتمالية${\displaystyle 1/2^{2n+1}}$واحتمالية أن يكون لشجرة عشوائية هذا الحجم هي هذه الاحتمالية مضروبة في عدد كاتالاني.

${\displaystyle {\frac {C_{n}}{2^{2n+1}}}={\frac {1}{2n+1}}{\binom {2n+1}{n}}{\frac {1}{2^{2n+1}}}\approx {\frac {1}{{\sqrt {4\pi }}\,n^{3/2}}}\displaystyle }$[ ^{28 ]​}

يُعدّ شكلٌ آخر من أشكال الأشجار الثنائية، وهو شجرة البحث الثنائية أو شجرة البحث الرقمية، مجموعةً من الأرقام الثنائية التي تُشير إلى بعض عُقدها الخارجية. تُمثّل العُقد الداخلية للشجرة بادئات تمثيلاتها الثنائية المشتركة بين رقمين أو أكثر. يتم الحصول على الابنين الأيسر والأيمن لعقدة داخلية بتمديد البادئة المقابلة ببتٍ إضافي، إما صفر أو واحد على التوالي. إذا لم يُطابق هذا التمديد أيًا من الأرقام المُعطاة، أو طابق واحدًا منها فقط، فإن النتيجة تكون عقدة خارجية؛ وإلا فهي عقدة داخلية أخرى. دُرست أشجار البحث الثنائية العشوائية، على سبيل المثال لمجموعات من الأعداد الحقيقية العشوائية المُولّدة بشكلٍ مستقل في الفترة [0, 1]. على الرغم من أن هذه الأشجار قد تحتوي على بعض العُقد الخارجية الفارغة، إلا أنها تميل إلى أن تكون أكثر توازنًا من أشجار البحث الثنائية العشوائية.${\displaystyle n}$بالنسبة للأعداد الحقيقية العشوائية المنتظمة في الفترة [0]، أو بشكل أعم لأي توزيع احتمالي قابل للتكامل التربيعي على الفترة [0]، يكون متوسط ​​عمق العقدة مقاربًا لـ${\displaystyle \log _{2}n}$ومتوسط ​​ارتفاع الشجرة بأكملها يكون مقارباً لـ${\displaystyle 2\log _{2}n}$يمكن تطبيق تحليل هذه الأشجار على التعقيد الحسابي لخوارزميات الفرز القائمة على الأشجار . ^{[ 33 ]}

يُعدّ نوعٌ مُعدّل من شجرة البحث، يُعرف بشجرة الجذر أو شجرة البحث المضغوطة، حيث يُزيل العقد الخارجية الفارغة وعقدها الداخلية الأصلية. وتُقابل العقد الداخلية المتبقية البادئات التي يُستخدم فيها كلا الامتدادين المُمكنين، إما بصفر أو بواحد، بواسطة واحد على الأقل من الأرقام المُختارة عشوائيًا. للحصول على شجرة الجذر لـ${\displaystyle n}$الأعداد الثنائية الموزعة بشكل منتظم، أقصر مسار بين الورقة والجذر له طول $${\displaystyle \log _{2}n-\log _{2}\log n+o(\log \log n)}$$ ويبلغ طول أطول مسار بين الورقة والجذر $${\displaystyle \log _{2}n+{\sqrt {2\log _{2}n}}+o({\sqrt {\log n}}),}$$ كلاهما باحتمالية عالية . ^{[ 34 ]}

يصف لوك ديفروي وبول كروزوسكي عملية تكرارية لإنشاء أشجار ثنائية عشوائية باستخدام${\displaystyle n}$العقد. يقوم بتوليد متغير عشوائي ذي قيمة حقيقية${\displaystyle x}$في الفترة الزمنية للوحدة${\displaystyle (0,1)}$، يُعيّن الأول${\displaystyle xn}$يتم نقل العقد (مع تقريبها إلى أقرب عدد صحيح) إلى الشجرة الفرعية اليسرى، ثم العقدة التالية إلى الجذر، والعقد المتبقية إلى الشجرة الفرعية اليمنى. بعد ذلك، تستمر العملية بشكل متكرر باستخدام نفس الأسلوب في الشجرتين الفرعيتين اليسرى واليمنى.${\displaystyle x}$إذا تم اختيار عقدة عشوائيًا وبشكل منتظم ضمن الفترة المحددة، فإن النتيجة تكون مماثلة لشجرة البحث الثنائية العشوائية الناتجة عن تبديل عشوائي للعقد، حيث يكون احتمال اختيار أي عقدة كجذر متساويًا. ومع ذلك، تسمح هذه الصيغة باستخدام توزيعات أخرى. على سبيل المثال، في نموذج الشجرة الثنائية العشوائية المنتظمة، بمجرد تحديد جذر، يجب أن تكون كل من شجرتيه الفرعيتين عشوائيتين بشكل منتظم أيضًا، لذا يمكن أيضًا إنشاء النموذج العشوائي المنتظم عن طريق اختيار توزيع مختلف (اعتمادًا على...).${\displaystyle n}$) ل${\displaystyle x}$كما توضح هذه النتائج، باختيار توزيع بيتا على${\displaystyle x}$وباستخدام شكل مناسب لرسم كل فرع من الفروع، يمكن استخدام الأشجار الرياضية الناتجة عن هذه العملية لإنشاء أشجار نباتية ذات مظهر واقعي. ^{[ 35 ]}