Range Sum of BST
تُخزَّن شجرة البحث الثنائية في المصفوفة tree بترتيب المستويات: يكون الجذر عند الفهرس 0، ويكون ابنا العقدة عند الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -1 إلى موضع فارغ. في شجرة البحث الثنائية، تكون كل قيمة في الشجرة الفرعية اليسرى للعقدة أصغر من قيمة العقدة، وتكون كل قيمة في شجرتها الفرعية اليمنى أكبر منها.
أعِد مجموع قيم جميع العقد v التي تحقق low ≤ v ≤ high، أو 0 إذا لم توجد أيٌّ منها.
الدالة
- treeinteger-array
- شجرة البحث الثنائية بترتيب المستويات، مع استخدام -1 للدلالة على موضع فارغ
- lowinteger
- أصغر قيمة للعدّ
- highinteger
- أكبر قيمة للعدّ
- تُرجعinteger
- مجموع قيم العقد الواقعة بين low وhigh، شاملًا كلا الحدّين
القيود
1 ≤ tree.length ≤ 32767- كل
tree[i]إما-1أو قيمة تحقق0 ≤ tree[i] ≤ 105. tree[0]لا تساوي أبدًا-1، لذا تحتوي الشجرة على عقدة واحدة على الأقل.- قد تنتهي المصفوفة بعناصر إضافية قيمتها
-1بعد العقدة الأخيرة. - كلا الابنين في الموضع الفارغ فارغان أيضًا، والعمق لا يزيد عن
14. - الشجرة هي شجرة بحث ثنائية صالحة، لذا فإن جميع قيمها مختلفة.
0 ≤ low ≤ high ≤ 105- الإجابة تقع ضمن نطاق عدد صحيح موقّع من 32 بت.
أمثلة
- المدخلات
- tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
- المخرجات
- 88
- الشرح
- القيم من
9إلى31هي10و12و15و20و31، ومجموعها88. أما3و8و40فتقع خارج النطاق.
- المدخلات
- tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
- المخرجات
- 0
- الشرح
- تحتوي الشجرة على
25و50و75، ولا يقع أيٌّ منها بين60و70، لذا فالمجموع هو0. تمثل الإدخالات الأربعة-1مواضع الأبناء الفارغة للعقدتين25و75.
- المدخلات
- tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
- المخرجات
- 4
- الشرح
- عندما تكون قيمتا
lowوhighكلتاهما4، لا تُحتسب إلا عقدة قيمتها4. تقع قيمة4عند الفهرس4، وهي الابن الأيمن للعقدة2، لذا فالإجابة هي4.
سؤال إضافي
إذا كان عليك الإجابة عن آلاف الاستعلامات المختلفة (low, high) على الشجرة نفسها، فكيف يمكنك الإجابة عن كل واحد منها في زمن O(log n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تؤدي زيارة كل عقدة وجمع القيم ضمن النطاق إلى الإجابة الصحيحة. ماذا يخبرك ترتيب شجرة البحث عن القيم الموجودة أسفل العقدة؟
كل ما في الشجرة الفرعية اليسرى للعقدة أصغر من العقدة، وكل ما في الشجرة الفرعية اليمنى أكبر منها. إذا كانت قيمة العقدة أقل من أو تساوي
low، فهل يمكن أن يكون أي شيء في جهتها اليسرى ضمن النطاق؟اجتز الشجرة باستخدام مكدس من الفهارس بدءًا من الجذر. أضف قيمة العقدة عندما تقع ضمن النطاق، وأضف ابنها الأيسر عند
2*i+1إلى المكدس فقط عندما تكون القيمة أكبر منlow، وابنها الأيمن عند2*i+2فقط عندما تكون القيمة أقل منhigh.
الحل
إن زيارة كل عقدة وجمع القيم الواقعة ضمن النطاق أمر صحيح. ويتيح لك ترتيب شجرة البحث القيام بعمل أقل: فقيمة العقدة تخبرك بالجانب الذي يحتوي على القيم الأصغر والقيم الأكبر، لذا لا تُفتح أبدًا شجرة فرعية لا يمكنها الوصول إلى النطاق.
زُر كل عقدة
الفكرة
لا يكون الابن حقيقيًا إلا إذا كان فهرسه داخل المصفوفة وكانت القيمة عنده لا تساوي -1. في المثال الأول، تكون قيمة 12 عند الفهرس 4 هي 10 و15 عند الفهرسين 9 و10، وتكون قيمة 31 عند الفهرس 2 ذات موضع أيسر فارغ عند الفهرس 5.
تقع كل قيمة ضمن النطاق في عقدة ما، لذا فإن اجتيازًا بالمكدس يصل إلى كل عقدة ويجمع القيم التي تحقق low ≤ v ≤ high يعطي المجموع الصحيح. يتجاهل ترتيب شجرة البحث، لذا يزور جميع العقد n حتى عندما لا يحتوي النطاق إلا على بضع قيم.
الخوارزمية
- ادفع فهرس الجذر
0إلى المكدس واضبطtotal = 0. - أخرج فهرسًا
iمن المكدس. إذا كانlow ≤ tree[i] ≤ high، فأضفtree[i]إلىtotal. - ادفع
2*i+1و2*i+2عندما يكونان ضمن حدود المصفوفة ولا يساويان-1. - عندما يصبح المكدس فارغًا، أعد
total.
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append(left)
if right < n and tree[right] != -1:
stack.append(right)
return totalقلِّم وفق ترتيب شجرة البحث
الفكرة
تحتوي الشجرة الفرعية اليسرى للعقدة التي تحمل v على قيم أصغر من v فقط. إذا كانت v ≤ low، فلا تقع أيٌّ منها ضمن النطاق، لذا تخطَّ تلك الشجرة الفرعية. وإذا كانت v ≥ high، فتحتوي الشجرة الفرعية اليمنى على قيم أكبر من high فقط، لذا تخطَّها. في المثال الأول، تساوي 31 القيمة high، لذا لا يُضاف ابنها الأيمن 40 إلى المكدس مطلقًا. تقع 8 دون low، لذا يُتخطى ابنها الأيسر 3، لكن يُزار ابنها الأيمن 12، لأن القيم بين 8 و20 قد تقع ضمن النطاق.
تزور قيم k الواقعة ضمن النطاق، بالإضافة إلى العقد الموجودة على مسارين كحد أقصى من الجذر: يستغرق ذلك O(h + k) من الوقت لعمق h. وحتى عندما يشمل النطاق الشجرة بأكملها، يظل التعقيد O(n).
الخوارزمية
- ادفع فهرس الجذر
0إلى المكدس واضبطtotal = 0. - أخرج فهرسًا
iواقرأv = tree[i]. إذا كانlow ≤ v ≤ high، فأضفvإلىtotal. - إذا كان
v > low، فادفع الابن الأيسر2*i+1إلى المكدس إذا كان موجودًا. - إذا كان
v < high، فادفع الابن الأيمن2*i+2إلى المكدس إذا كان موجودًا. - عندما يصبح المكدس فارغًا، أعد
total.
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
# Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
if value > low and left < n and tree[left] != -1:
stack.append(left)
if value < high and right < n and tree[right] != -1:
stack.append(right)
return total
أخطاء شائعة وحالات حدّية
- استخدام مقارنات صارمة. يُحتسب الطرفان، لذا يجب أن يحتسب المثال الثالث، حيث
low = high = 4، القيمة4. - التقليم مبكرًا بخطوة واحدة. عند
v = lowيمكن استبعاد الشجرة الفرعية اليسرى، لكن عندv = low + 1قد تحتوي علىlowنفسها. - استبعاد جانبي عقدة تقع خارج النطاق. القيمة
8في المثال الأول أقل منlow، ومع ذلك تحتوي شجرتها الفرعية اليمنى على10و12و15. - قراءة ابن بعد نهاية المصفوفة. تحقّق من
2*i+1 < tree.lengthقبل القراءة، واعتبر-1على أنه لا يوجد ابن. - في Lua وR، تبدأ المصفوفات من 1: أبقِ فهارس العقد بدءًا من 0 لإجراء الحساب
2*i+1، واقرأtree[i + 1].
أسئلة شائعة3
ما هو التعقيد الزمني لمجموع النطاق في شجرة البحث الثنائية؟
يزور الاجتياز المُقلَّم العقد k الواقعة ضمن النطاق، بالإضافة إلى العقد الموجودة على مسارين كحد أقصى من الجذر: يستغرق ذلك زمنًا O(h + k) لشجرة عمقها h، وO(n) عندما تكون كل القيم ضمن النطاق. وتستهلك المكدسة أو الاستدعاءات العودية مساحة O(h).
هل يمكن حل مسألة مجموع النطاق في شجرة البحث الثنائية (BST) باستخدام الاجتياز بالترتيب الوسيط؟
نعم. يعرض الاجتياز بالترتيب القيم بترتيب تصاعدي، لذا أضِف القيم عندما تصل إلى low وتوقّف عند أول قيمة تتجاوز high. يوفّر التوقّف المبكر العمل في الجانب الأيمن من الشجرة؛ أما التقليم فيوفّره على كلا الجانبين.
هل ينبغي استخدام الاستدعاء الذاتي أم المكدس لحساب مجموع النطاق في شجرة بحث ثنائية؟
كلاهما يعمل. هنا لا يتجاوز العمق 14، لذا يظل الاستدعاء الذاتي محدود العمق. تتجنب المكدسة الصريحة حدّ الاستدعاء الذاتي في شجرة طويلة تضم آلاف المستويات.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def rangeSumBST(tree, low, high):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] low = 9 high = 31
الإخراج المتوقع
88