Range Sum of BST
لديك شجرة بحث ثنائية مخزّنة في المصفوفة tree بترتيب المستويات، ورقمان low وhigh. يقع الجذر عند الفهرس 0، ويقع ابنا العقدة عند الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -1 إلى موضع فارغ، وقد تنتهي المصفوفة بعناصر -1 إضافية. في شجرة البحث الثنائية، تكون كل قيمة في الشجرة الفرعية اليسرى للعقدة أصغر من قيمة العقدة، وتكون كل قيمة في شجرتها الفرعية اليمنى أكبر منها.
اكتب دالة باسم rangeSumBST تُعيد مجموع قيم جميع العقد 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.
+14 اختبارات مخفية عند الإرسال
سؤال إضافي
إذا كان عليك الإجابة عن آلاف الاستعلامات المختلفة (low, high) على الشجرة نفسها، فكيف يمكنك الإجابة عن كل واحد منها في زمن O(log n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تؤدي زيارة كل عقدة وجمع القيم الواقعة ضمن النطاق إلى الإجابة الصحيحة. ماذا يخبرك ترتيب شجرة البحث عن القيم الموجودة أسفل عقدة؟
كل ما في الشجرة الفرعية اليسرى للعقدة أصغر من العقدة، وكل ما في الشجرة الفرعية اليمنى لها أكبر منها. إذا كانت قيمة العقدة أقل من أو تساوي
low، فهل يمكن أن يكون أي شيء على يسارها ضمن النطاق؟تجوّل في الشجرة باستخدام مكدس من الفهارس بدءًا من الجذر. أضف قيمة العقدة عندما تكون ضمن النطاق، وادفع ابنها الأيسر عند
2*i+1فقط عندما تكون القيمة أكبر منlow، وابنها الأيمن عند2*i+2فقط عندما تكون القيمة أقل منhigh.
الحل
جمع كل قيمة في النطاق هو اجتياز عادي: زُر كل عقدة واحتفظ بالعقد التي تناسب النطاق. يتيح لك ترتيب شجرة البحث أداء ذلك بشكل أفضل. تخبرك قيمة العقدة بأي جانب توجد القيم الأصغر والأكبر، لذا يمكنك تخطي أشجار فرعية كاملة دون النظر إلى أي عقدة داخلها.
زُر كل عقدة
الفكرة
أولًا، كيفية التنقّل داخل المصفوفة. للعقدة عند الفهرس i ابن أيسر عند 2*i+1 وابن أيمن عند 2*i+2. يكون الابن حقيقيًا فقط إذا كان فهرسه ضمن حدود المصفوفة وكانت القيمة فيه ليست -1. في [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]، تكون للعقدة الجذرية 20 العقدتان 8 و31 عند الفهرسين 1 و2، وللعقدة 12 عند الفهرس 4 العقدتان 10 و15 عند الفهرسين 9 و10، وللعقدة 31 موضع أيسر فارغ عند الفهرس 5.
والآن الفكرة. تقع كل قيمة ضمن النطاق في عقدة ما، لذا فإن اجتيازًا يصل إلى كل عقدة ويضيف القيم التي تحقق low ≤ v ≤ high يعطي المجموع الصحيح. استخدم مكدسًا لفهارس العقد. ابدأ بالجذر، وأخرج فهرسًا من المكدس، وأضف قيمته إذا كانت ضمن النطاق، ثم أضف كل ابن حقيقي إلى المكدس.
يتجاهل هذا خاصية شجرة البحث تمامًا؛ فهو يعمل على أي شجرة ثنائية. يزور جميع العقد n، بزمن O(n)، ويحفظ المكدس الأبناء المنتظرين على مسار واحد، بمساحة O(h) لعمق h. عندما يغطي النطاق بضع قيم فقط في شجرة تضم آلاف العقد، يكون معظم هذا العمل مهدورًا.
الخوارزمية
- ادفع فهرس الجذر
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، فكل هذه القيم أصغر من low، لذا لا يمكن للفرع الأيسر أن يضيف أي شيء: تخطَّه. وبالمثل، إذا كان v ≥ high، فلا يحتوي فرعها الأيمن إلا على قيم أكبر من high: تخطَّه. لذلك، أضف الابن الأيسر إلى المكدس فقط عندما يكون v > low، والابن الأيمن فقط عندما يكون v < high.
في المثال الأول ذي النطاق [9, 31]، تساوي 31 القيمة high، لذا لا تُضاف العقدة الابنة اليمنى 40 إلى المكدس مطلقًا. تقع 8 دون low، لذا يُتخطى ابنها الأيسر 3، بينما تظل زيارة ابنها الأيمن 12 مطلوبة، لأن القيم الواقعة بين 8 و20 قد تكون ضمن النطاق.
العقد التي تزورها هي القيم k الواقعة ضمن النطاق، بالإضافة إلى مسارين على الأكثر من الجذر إلى ورقة على طول حافتيه، لذا يكون الزمن O(h + k). عندما يشمل النطاق الشجرة بأكملها، يظل التعقيد O(n)، لكن النطاق الضيق في شجرة كبيرة لا يمس إلا بضع عشرات من العقد. يحتاج المكدس إلى مساحة O(h).
الخوارزمية
- ادفع فهرس الجذر
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. - تقليم الشجرة قبل الأوان بخطوة واحدة. عندما تكون
vمساوية لـlow، يمكن تخطي الشجرة الفرعية اليسرى، لكن عندما تكونvهيlow + 1فلا يمكن ذلك: فقد تحتوي علىlowنفسه. - التوقف عند عقدة خارج النطاق. لا يزال من الممكن أن تحتوي الشجرة الفرعية اليمنى لعقدة أقل من
lowعلى قيم تقع ضمن النطاق، لذا تخطَّ فقط الجانب الذي تستبعده قواعد الترتيب. - قراءة فهرس ابن يتجاوز نهاية المصفوفة. تحقّق من
2*i+1 < tree.lengthقبل قراءة القيمة، واعتبر-1دلالة على عدم وجود ابن. - الخلط بين الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد تبدأ من 0 لحساب
2*i+1، واقرأtree[i + 1].
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة مجموع نطاق قيم شجرة البحث الثنائية؟
الاجتياز الذي يستبعد الفروع وفق ترتيب شجرة البحث يزور العقد k الواقعة ضمن النطاق، بالإضافة إلى العقد الموجودة على مسارين كحد أقصى من الجذر، بزمن O(h + k) لشجرة عمقها h. في أسوأ الحالات، عندما تكون كل قيمة ضمن النطاق، يكون الزمن O(n). والمساحة الإضافية هي O(h) للمكدس أو للاستدعاء التكراري.
لماذا يمكنك تخطي الأشجار الفرعية في Range Sum of BST؟
في شجرة بحث ثنائية، تكون كل قيمة على يسار العقدة أصغر منها، وكل قيمة على يمينها أكبر منها. إذا كانت قيمة العقدة أقل من أو تساوي low، فلن تصل أي قيمة على يسارها إلى النطاق، وإذا كانت أكبر من أو تساوي high، فلن تصل أي قيمة على يمينها إلى النطاق. تخطّي هذين الجانبين لا يؤدي أبدًا إلى تفويت قيمة ضمن النطاق.
هل يمكن حل مسألة مجموع النطاق في شجرة بحث ثنائية باستخدام اجتياز الترتيب الوسطي؟
نعم. يعرض الاجتياز بالترتيب الوسطي لشجرة البحث الثنائية القيم بترتيب تصاعدي، لذا يمكنك جمع القيم بمجرد بلوغها low، والتوقف فور تجاوز إحدى القيم high. يعطي ذلك الإجابة نفسها، ويوفّر التوقف المبكر العمل في الجانب الأيمن من الشجرة، بينما يوفّر البحث مع التقليم العمل في الجانب الأيسر أيضًا.
هل ينبغي أن تستخدم الاستدعاء الذاتي أم المكدس لحساب مجموع النطاق في شجرة بحث ثنائية؟
كلاهما يعمل. الاستدعاء الذاتي أقصر، والعمق هنا لا يتجاوز 14، لذا يظل مكدس الاستدعاءات صغيرًا. يتجنب المكدس الصريح حدّ الاستدعاء الذاتي تمامًا، وهذا مهم في شجرة طويلة تضم آلاف المستويات، وهو ما تستخدمه الحلول في هذه الصفحة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
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