مسألة بناء شجرة ثنائية

تحديد ما إذا كانت المسألة من مسائل التقسيم والتغلب

تُعرَّف المسألة الأصلية بأنها بناء شجرة ثنائية من preorder وinorder، وهي مسألة نموذجية من مسائل التقسيم والتغلب.

• المسألة قابلة للتفكيك: من منظور التقسيم والتغلب، يمكننا تقسيم المسألة الأصلية إلى مسألتين فرعيتين: بناء الشجرة الفرعية اليسرى وبناء الشجرة الفرعية اليمنى، إضافةً إلى عملية واحدة: تهيئة عقدة الجذر. ولكل شجرة فرعية (مسألة فرعية)، يمكننا إعادة استخدام طريقة التقسيم السابقة، وتقسيمها إلى أشجار فرعية (مسائل فرعية) أصغر حتى الوصول إلى أصغر مسألة فرعية (شجرة فرعية فارغة).
• المسائل الفرعية مستقلة: الشجرتان الفرعيتان اليسرى واليمنى مستقلتان إحداهما عن الأخرى، ولا تداخل بينهما. فعند بناء الشجرة الفرعية اليسرى، لا نحتاج إلا إلى التركيز على الأجزاء المقابلة للشجرة الفرعية اليسرى في الاجتيازين الوسطي والمسبق. وينطبق الشيء نفسه على الشجرة الفرعية اليمنى.
• حلول المسائل الفرعية قابلة للدمج: بمجرد أن نحصل على الشجرتين الفرعيتين اليسرى واليمنى (حلّي المسألتين الفرعيتين)، يمكننا ربطهما بعقدة الجذر للحصول على حل المسألة الأصلية.

كيفية تقسيم الأشجار الفرعية

استناداً إلى التحليل السابق، يمكن حل هذه المسألة باستخدام التقسيم والتغلب، لكن كيف نقسّم الشجرتين الفرعيتين اليسرى واليمنى عبر الاجتياز المسبق preorder والاجتياز الوسطي inorder؟

وفقاً للتعريف، يمكن تقسيم كل من preorder وinorder إلى ثلاثة أجزاء.

• الاجتياز المسبق: [ عقدة الجذر | الشجرة الفرعية اليسرى | الشجرة الفرعية اليمنى ]، فمثلاً تقابل الشجرة في الشكل أعلاه [ 3 | 9 | 2 1 7 ].
• الاجتياز الوسطي: [ الشجرة الفرعية اليسرى | عقدة الجذر | الشجرة الفرعية اليمنى ]، فمثلاً تقابل الشجرة في الشكل أعلاه [ 9 | 3 | 1 2 7 ].

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

1. العنصر الأول 3 في الاجتياز المسبق هو قيمة عقدة الجذر.
2. ابحث عن فهرس عقدة الجذر 3 في inorder، واستخدم هذا الفهرس لتقسيم inorder إلى [ 9 | 3 | 1 2 7 ].
3. استناداً إلى نتيجة تقسيم inorder، يسهل تحديد أن الشجرتين الفرعيتين اليسرى واليمنى تحتويان على 1 و3 عقد على التوالي، مما يتيح لنا تقسيم preorder إلى [ 3 | 9 | 2 1 7 ].

تمثيل مجالات الأشجار الفرعية بالمتغيرات

استناداً إلى طريقة التقسيم السابقة، حصلنا على مجالات فهارس عقدة الجذر والشجرة الفرعية اليسرى والشجرة الفرعية اليمنى في preorder وinorder. ولتمثيل مجالات الفهارس هذه، نحتاج إلى استخدام عدة متغيرات فهرس.

• نرمز لفهرس عقدة جذر الشجرة الحالية في preorder بـ$i$.
• نرمز لفهرس عقدة جذر الشجرة الحالية في inorder بـ$m$.
• نرمز لمجال فهارس الشجرة الحالية في inorder بـ$[l, r]$.

وكما يوضح الجدول أدناه، يمكننا عبر هذه المتغيرات تمثيل فهرس عقدة الجذر في preorder ومجالات فهارس الأشجار الفرعية في inorder.

الجدول   فهارس عقدة الجذر والأشجار الفرعية في الاجتيازين المسبق والوسطي

لاحظ أن $(m-l)$ في فهرس عقدة جذر الشجرة الفرعية اليمنى يعني "عدد العقد في الشجرة الفرعية اليسرى". ويُستحسن فهم ذلك بالاقتران مع الشكل أدناه.

تنفيذ الشيفرة

لتحسين كفاءة الاستعلام عن $m$، نستخدم جدول تجزئة hmap لتخزين التعيين من عناصر مصفوفة inorder إلى فهارسها:

/* بناء شجرة ثنائية */
func buildTree(preorder, inorder []int) *TreeNode {
	// هيّئ جدول التجزئة، وخزّن التعيين من عناصر inorder إلى الفهارس
	inorderMap := make(map[int]int, len(inorder))
	for i := 0; i < len(inorder); i++ {
		inorderMap[inorder[i]] = i
	}

	root := dfsBuildTree(preorder, inorderMap, 0, 0, len(inorder)-1)
	return root
}

/* بناء شجرة ثنائية */
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    // هيّئ جدول التجزئة، وخزّن التعيين من عناصر inorder إلى الفهارس
    let inorderMap = new Map<number, number>();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }
    const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}

يوضح الشكل أدناه العملية التعاودية لبناء الشجرة الثنائية. فكل عقدة تُنشأ أثناء عملية "التعاود" النازلة، بينما يُنشأ كل ضلع (مرجع) أثناء عملية "العودة" الصاعدة.

وتظهر نتائج تقسيم الاجتياز المسبق preorder والاجتياز الوسطي inorder داخل كل دالة تعاودية في الشكل أدناه.

لنفترض أن عدد العقد في الشجرة $n$. تستغرق تهيئة كل عقدة (تنفيذ دالة تعاودية dfs() واحدة) زمن $O(1)$. لذا فإن التعقيد الزمني الإجمالي هو $O(n)$.

ويخزّن جدول التجزئة التعيين من عناصر inorder إلى فهارسها، بتعقيد مكاني $O(n)$. وفي أسوأ الحالات، عندما تتدهور الشجرة الثنائية إلى قائمة مترابطة، يبلغ عمق التعاود $n$، مستهلكاً مساحة إطارات المكدس $O(n)$. لذا فإن التعقيد المكاني الإجمالي هو $O(n)$.