شجرة PQ
شجرة PQ هي بنية بيانات قائمة على الشجرة تمثل عائلة من التباديل على مجموعة من العناصر، وقد اكتشفها وأطلق عليها هذا الاسم كيلوج إس. بوث وجورج إس. لوكر في عام 1976. [ 1 ] وهي شجرة جذرية ومصنفة، حيث يتم تمثيل كل عنصر بإحدى العقد الورقية ، ويتم تصنيف كل عقدة غير ورقية بـ P أو Q. تحتوي عقدة AP على طفلين على الأقل، وتحتوي عقدة Q على ثلاثة أطفال على الأقل.
تمثل شجرة PQ تباديلها من خلال إعادة ترتيب مسموح بها لأبناء عقدها. يمكن إعادة ترتيب أبناء عقدة P بأي طريقة. يمكن وضع أبناء عقدة Q بترتيب عكسي، ولكن لا يمكن إعادة ترتيبهم بأي طريقة أخرى. تمثل شجرة PQ جميع ترتيبات العقد الطرفية التي يمكن تحقيقها بأي تسلسل لهاتين العمليتين. يمكن لشجرة PQ التي تحتوي على العديد من عقد P و Q أن تمثل مجموعات فرعية معقدة من مجموعة جميع الترتيبات الممكنة. ومع ذلك، قد لا تكون كل مجموعة من الترتيبات قابلة للتمثيل بهذه الطريقة؛ على سبيل المثال، إذا تم تمثيل ترتيب ما بواسطة شجرة PQ، فيجب أيضًا تمثيل عكس هذا الترتيب بواسطة الشجرة نفسها.
تُستخدم أشجار PQ لحل المشكلات التي تهدف إلى إيجاد ترتيب يُلبي قيودًا مختلفة. في هذه المشكلات، تُضاف قيود الترتيب واحدًا تلو الآخر، وذلك بتعديل بنية شجرة PQ بحيث لا تُمثل إلا الترتيبات التي تُلبي القيد. تشمل تطبيقات أشجار PQ إنشاء خريطة متجاورة من أجزاء الحمض النووي ، [ 2 ] واختبار مصفوفة لخاصية الواحدات المتتالية، والتعرف على الرسوم البيانية الفاصلية ، وتحديد ما إذا كان الرسم البياني مستويًا . [ 1 ]
أمثلة ورموز
إذا كانت جميع أوراق شجرة PQ متصلة مباشرةً بعقدة الجذر P، فإن جميع الترتيبات الممكنة مسموحة. أما إذا كانت جميع الأوراق متصلة مباشرةً بعقدة الجذر Q، فلا يُسمح إلا بترتيب واحد وعكسه. وإذا كانت العقد a وb وc متصلة بعقدة Q، التي بدورها متصلة بعقدة الجذر P، مع اتصال جميع العقد الورقية الأخرى مباشرةً بالجذر، فإن أي ترتيب تكون فيه a وb وc متجاورة مسموح به.
عندما يتعذر تمثيل الأشجار بيانيًا، غالبًا ما تُستخدم قوائم متداخلة بين قوسين لتمثيل أشجار PQ. يُمثل كل زوج متطابق من الأقواس المربعة عقدة Q، بينما يُمثل كل زوج متطابق من الأقواس المستديرة عقدة P. أما الأوراق فهي عناصر القوائم غير الموجودة بين قوسين. تُمثل الصورة على اليسار في هذا الترميز بالصيغة [1 (2 3 4) 5]. تُمثل شجرة PQ هذه التباديل الاثني عشر التالية على المجموعة {1، 2، 3، 4، 5}:
- 12345، 12435، 13245، 13425، 14235، 14325، 52341، 52431، 53241، 53421، 54231، 54321.
أشجار الكمبيوتر
شجرة PC ، التي طورها وي-كوان شيه ووين -ليان هسو ، هي تعميم أحدث لشجرة PQ. وكما هو الحال في شجرة PQ، فإنها تمثل التباديل بإعادة ترتيب العقد في الشجرة، حيث تُمثل العناصر عند أوراق الشجرة. وعلى عكس شجرة PQ، فإن شجرة PC غير جذرية. يمكن إعادة ترتيب العقد المجاورة لأي عقدة غير ورقية تحمل الرمز P بشكل عشوائي كما في شجرة PQ، بينما تتمتع العقد المجاورة لأي عقدة غير ورقية تحمل الرمز C بترتيب دوري ثابت ، ولا يمكن إعادة ترتيبها إلا بعكس هذا الترتيب. وبالتالي، لا يمكن لشجرة PC تمثيل سوى مجموعات من الترتيبات التي يكون فيها أي تبديل دائري أو عكس ترتيب في المجموعة موجودًا أيضًا في المجموعة. ومع ذلك، يمكن محاكاة شجرة PQ ذات n عنصرًا بشجرة PC ذات n + 1 عنصرًا، حيث يعمل العنصر الإضافي كجذر لشجرة PC. تُعد عمليات بنية البيانات المطلوبة لتنفيذ خوارزمية اختبار التسطح على أشجار PC أبسط إلى حد ما من العمليات المقابلة على أشجار PQ. [ 3 ]
انظر أيضاً
مراجع
- 1 2 بوث، كيلوج س.؛ لوكر، جورج س. (1976). "اختبار خاصية الواحدات المتتالية، والرسوم البيانية الفاصلية، وتسطيح الرسم البياني باستخدام خوارزميات شجرة PQ" . مجلة علوم الحاسوب والنظم . 13 (3): 335-379 . doi : 10.1016/S0022-0000(76)80045-1 .
- ↑ كارب، ريتشارد م. (1993). "رسم خريطة الجينوم: بعض المشكلات التوافقية الناشئة في البيولوجيا الجزيئية". في: كوساراجو، س. راو ؛ جونسون، ديفيد س .؛ أغاروال، ألوك (محررون). وقائع الندوة السنوية الخامسة والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة، 16-18 مايو 1993، سان دييغو، كاليفورنيا، الولايات المتحدة الأمريكية . جمعية آلات الحوسبة. الصفحات 278-285 . doi : 10.1145/167088.167170 .
- ↑ شيه، وي-كوان؛ هسو، وين-ليان (1999). "اختبار جديد للتسطيح" (ملف PDF) . علوم الحاسوب النظرية . 223 ( 1-2 ): 179-191 . doi : 10.1016/S0304-3975(98)00120-0 .
روابط خارجية
- الأشجار (هياكل البيانات)