شجرة البحث ذات الأولوية

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
الموسوعة الحرة

في علم الحاسوب ، تُعد شجرة البحث ذات الأولوية بنية بيانات شجرية لتخزين النقاط في بُعدين. وقد قدمها إدوارد إم. مكريت في الأصل . [ 1 ] وهي في الواقع امتداد لطابور الأولوية بهدف تحسين زمن البحث من O( n ) إلى O( s + log n )، حيث n هو عدد النقاط في الشجرة و s هو عدد النقاط التي يُعيدها البحث.

وصف

تُستخدم شجرة البحث ذات الأولوية لتخزين مجموعة من النقاط ثنائية الأبعاد مرتبة حسب الأولوية وقيمة مفتاحية. ويتم ذلك من خلال إنشاء مزيج بين قائمة انتظار ذات أولوية وشجرة بحث ثنائية .

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

العمليات

بناء

يتطلب بناء الشجرة زمنًا قدره O( n log n ) ومساحة تخزين قدرها O( n ). فيما يلي خوارزمية مقترحة للبناء:

دالة ` construct_tree ( data ) `: إذا كان طول البيانات أكبر من 1 ، فسيتم تحديد نقطة العقدة ذات الأولوية الأدنى. ثم يتم حذف نقطة العقدة من البيانات . بعد ذلك، يتم حساب الوسيط باستخدام ` calculate_median ( reduced_data ) ` ، مع استبعاد النقطة المحددة . يتم تقسيم البيانات إلى مصفوفتين فارغتين: ` left_data = [ ]` و ` right_data = [ ] ` . لكل نقطة في البيانات المُخفّضة ، يتم إضافة النقطة إلى البيانات اليسرى ، وإلا يتم إضافتها إلى البيانات اليمنى .left_subtree = construct_tree ( left_data ) right_subtree = construct_tree ( right_data )إرجاع العقدة // العقدة التي تحتوي على مفتاح العقدة، ونقطة العقدة، والشجرتين الفرعيتين اليسرى واليمنى } وإلا إذا كان طول ( البيانات ) يساوي 1 { إرجاع عقدة الورقة // عقدة الورقة التي تحتوي على نقطة البيانات المتبقية الوحيدة } وإلا إذا كان طول ( البيانات ) يساوي 0 { إرجاع null // هذه العقدة فارغة } }

مع ذلك، إذا رُتِّبت النقاط وفقًا لقيمها الرئيسية، يُمكن إنشاء الشجرة في زمن خطي. [ 3 ] يُمكن تحقيق ذلك بسهولة عن طريق إنشاء شجرة ثنائية متوازنة على القيم الرئيسية (كأوراق) في زمن خطي. تخزن كل عقدة داخلية مؤشرًا إلى العقدة ذات الأولوية الأدنى وعدد العناصر في الشجرة الفرعية المتفرعة من تلك العقدة. بالتالي، يُمكن تحديد العقدة ذات الأولوية الأدنى في زمن ثابت. يُمكن تحديد وسيط النقاط المتبقية والعنصر ذي الأولوية الأدنى التالية في زمن O(log n). ومن ثم، تكون العلاقة التكرارية هي T(n) = 2T(n/2) + O(log n) = O(n).

يمكن الاستعلام بكفاءة عن شجرة البحث ذات الأولوية للحصول على مفتاح ضمن نطاق مغلق وقيمة أولوية قصوى. أي، يمكن تحديد نطاق [ min_key , max_key ] ونطاق آخر [-∞ , max_priority ] وإرجاع النقاط الموجودة ضمنه. يوضح ذلك الكود الزائف التالي:

نقاط بحث_الشجرة ( الشجرة ، المفتاح_الأدنى ، المفتاح_الأعلى ، الأولوية_الأعلى ) { الجذر = الحصول_على_العقدة_الجذرية ( الشجرة ) النتيجة = []إذا كان عدد الأبناء ( الجذر ) أكبر من صفر ، وإذا كانت أولوية النقطة ( الجذر ) أكبر من الحد الأقصى للأولوية ، فأرجع قيمة فارغة (null ) // لن يكون هناك شيء مهم في هذا الفرع.إذا كان min_key <= get_point_key ( root ) <= max_key // هل نقطة الجذر هي نقطة مهمة؟ أضف ( get_point ( node )) إلى النتيجة . إذا كان min_key < get_node_key ( root ) // هل يجب البحث في الشجرة الفرعية اليسرى؟ أضف ( search_tree ( root.left_sub_tree , min_key , max_key , max_priority ) ) إلى النتيجة .إذا كان مفتاح العقدة الجذرية أقل من المفتاح الأقصى ، فهل يجب البحث في الشجرة الفرعية اليمنى؟ أضف نتيجة البحث إلى النتيجة . وإلا ، فهذه عقدة طرفية إذا كانت أولوية النقطة الجذرية أقل من الأولوية القصوى ، وكان المفتاح الأدنى أقل من أو يساوي مفتاح النقطة الجذرية أقل من أو يساوي المفتاح الأقصى . هل النقطة الطرفية هي نقطة الاهتمام ؟ أضف نتيجة الحصول على النقطة من العقدة .

انظر أيضاً

مراجع

  1. ↑ مكريت، إدوارد (مايو 1985). "أشجار البحث ذات الأولوية". مجلة SIAM للحوسبة العلمية . 14 (2): 257-276 . doi : 10.1137/0214021 .
  2. ↑ لي، دي تي؛ يو، هونغ-آي (2018). "19: أشجار البحث الفاصلة، والقطاعية، والمدى، والأولوية"في: ميهتا، دينش؛ ساهني، سرتاج (محرران). دليل هياكل البيانات وتطبيقاتها (الطبعة الثانية  ). لندن: تشابمان آند هول/سي آر سي. الصفحات  19:1-19:17. doi : 10.1201/9781315119335 . ISBN 9781315119335.
  3. ↑ مارك بيرج، أوتفريد تشيونج، مارك كريفيلد، مارك أوفرمارس، الهندسة الحسابية، الخوارزميات والتطبيقات، الطبعة الثالثة، سبرينغر، 2008