Validate Binary Search Tree
تحصل على شجرة ثنائية مخزنة في المصفوفة tree بترتيب المستويات. يقع الجذر عند الفهرس 0، ويقع ابنا العقدة عند الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -1 إلى موضع فارغ، وقد تنتهي المصفوفة بعناصر -1 إضافية.
اكتب دالة باسم isValidBST تُرجع true إذا كانت الشجرة شجرة بحث ثنائية، وfalse خلاف ذلك. في شجرة البحث الثنائية، تكون قيمة كل عقدة أكبر تمامًا من كل قيمة في شجرتها الفرعية اليسرى، وأصغر تمامًا من كل قيمة في شجرتها الفرعية اليمنى. لا يمكن أبدًا أن توجد قيمتان متساويتان معًا في شجرة صالحة.
الدالة
- treeinteger-array
- الشجرة الثنائية بترتيب المستويات، مع استخدام -1 للدلالة على موضع فارغ
- تُرجعboolean
- صحيح إذا كانت الشجرة شجرة بحث ثنائية، وخطأ خلاف ذلك
القيود
1 ≤ tree.length ≤ 32767- كل
tree[i]تساوي-1أو قيمةً تحقق0 ≤ tree[i] ≤ 105. tree[0]لا تكون أبدًا-1، لذا تحتوي الشجرة على عقدة واحدة على الأقل.- قد تنتهي المصفوفة بإدخالات
-1إضافية بعد العقدة الأخيرة. - كلا الابنين في الموضع الفارغ فارغان أيضًا، والعمق لا يتجاوز
14. - قد تتكرر القيم.
أمثلة
- المدخلات
- tree = [8, 3, 12, 1, 6, 10, 15]
- المخرجات
- true
- الشرح
- تقع كل عقدة على الجانب الصحيح من كل عقدة تعلوها. عند القراءة بالترتيب (الشجرة الفرعية اليسرى، العقدة، الشجرة الفرعية اليمنى)، تظهر القيم على النحو التالي:
1, 3, 6, 8, 10, 12, 15، بترتيب متزايد تمامًا، وهذا ما توفره شجرة البحث.
- المدخلات
- tree = [10, 5, 15, -1, -1, 6, 20]
- المخرجات
- false
- الشرح
- كل عقدة أكبر من ابنها الأيسر وأصغر من ابنها الأيمن، ومع ذلك فالشجرة غير صالحة. تقع القيمة
6عند الفهرس5في الشجرة الفرعية اليمنى للجذر10، لذا يجب أن تكون أكبر من10، لكنها ليست كذلك.
- المدخلات
- tree = [12, 7, 12]
- المخرجات
- false
- الشرح
- يحتوي الابن الأيمن للجذر على
12، وهي القيمة نفسها الموجودة في الجذر. يجب أن تكون الشجرة الفرعية اليمنى أكبر تمامًا، لذا فإن تساوي القيمتين يخالف القاعدة.
+16 اختبارات مخفية عند الإرسال
سؤال إضافي
يقع الأب للعقدة عند الفهرس i في الموضع (i-1)/2، بعد التقريب إلى الأسفل. هل يمكنك اجتياز الشجرة بالترتيب باستخدام مساحة إضافية O(1)، والتنقل عبر الآباء بدلًا من الاحتفاظ بمكدس أو استخدام الاستدعاء الذاتي؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
في
[10, 5, 15, -1, -1, 6, 20]، كل عقدة أكبر من ابنها الأيسر وأصغر من ابنها الأيمن. لماذا لا تزال هذه الشجرة ليست شجرة بحث؟يضع كل سلف حدًا للعقدة: يكون الحد أدنى منها إذا كانت العقدة على يساره، وأعلى منها إذا كانت على يمينه. تشكّل هذه الحدود معًا نطاقًا مفتوحًا. يؤدي الانتقال يسارًا من قيمة
vإلى خفض الحد الأعلى إلىv؛ ويؤدي الانتقال يمينًا إلى رفع الحد الأدنى إلىv.احتفظ بمكدّس من
(index, low, high)، بدءًا من الجذر وبنطاق أوسع من كل قيمة مسموح بها. أخرج عنصرًا من المكدّس، وأخفِق إذا لم تكن القيمة واقعة ضمن النطاق بشكل صارم، وأضف كل ابن حقيقي إلى المكدّس مع نطاقه المُضيَّق.
الحل
القاعدة تتعلق بالأشجار الفرعية كاملةً، لا بعقدة وابنيها. قد تجتاز الشجرة اختبار الأب والابن عند كل عقدة، ومع ذلك تكون غير صحيحة، لأن عقدةً في عمق الشجرة قد تخالف حدًا وضعه سلفٌ لها على بُعد عدة مستويات. هناك فكرتان تعالجان ذلك ببساطة: قراءة الشجرة بالترتيب والتحقق من أن القيم تزداد بصرامة، أو إعطاء كل عقدة نطاق القيم الذي تسمح به أسلافها والتحقق من أن قيمتها تقع ضمن ذلك النطاق.
قارن كل عقدة بأشجارها الفرعية كاملة
الفكرة
أولًا، كيفية التنقل في المصفوفة. العقدة عند الفهرس i يكون ابنها الأيسر عند الفهرس 2*i+1 وابنها الأيمن عند الفهرس 2*i+2. لا يكون الابن حقيقيًا إلا إذا كان فهرسه داخل المصفوفة وكانت القيمة هناك ليست -1. في [10, 5, 15, -1, -1, 6, 20]، للعقدة الجذرية 10 العقدتان 5 و15 عند الفهرسين 1 و2، وللعقدة 15 العقدتان 6 و20 عند الفهرسين 5 و6.
الفكرة الأولى التي يجربها معظم الناس هي مقارنة كل عقدة بابنيها فقط. هذه الشجرة هي سبب فشل ذلك: تتحقق جميع العلاقات 5 < 10 و15 > 10 و6 < 15 و20 > 15، لكن العقدة 6 تقع إلى يمين العقدة 10. يتناول التعريف كل قيمة في الشجرة الفرعية، لذا تحقّق من ذلك تحديدًا.
بالنسبة إلى عقدة تحمل القيمة v، تكون كل القيم على يسارها أصغر من v بالضبط عندما تكون أكبر قيمة على يسارها أصغر من v. وبالمثل، تكون كل القيم على يمينها أكبر من v عندما تكون أصغر قيمة هناك أكبر من v. تعثر دالتان مساعدتان عوديتان بسيطتان على أكبر قيمة وأصغر قيمة. إذا كان أحد الجانبين فارغًا، فإن أكبر قيمة فيه هي -1 وأصغر قيمة هي 100001، وهما قيمتان خارج النطاق المسموح به، لذا لا يؤدي الجانب الفارغ إلى الفشل أبدًا.
هذا صحيح، لكنه يكرر العمل. تُفحَص العقدة مرة واحدة لكل سلف لها، لذا يبلغ الإجمالي نحو n × h زيارة لشجرة عمقها h. ومع عمق لا يتجاوز 14، فهذا مناسب هنا، لكن في شجرة تشكّل مسارًا طويلًا واحدًا من n عقد، يرتفع التعقيد إلى O(n²).
الخوارزمية
- مرّ على كل فهرس
iتكون قيمته غير-1. - اعثر على أكبر قيمة في الشجرة الفرعية اليسرى التي تبدأ عند
2*i+1، أو-1إذا كان ذلك الموضع فارغًا. - اعثر على أصغر قيمة في الشجرة الفرعية اليمنى التي تبدأ عند
2*i+2، أو100001إذا كان ذلك الموضع فارغًا. - إذا كانت القيمة الأكبر أكبر من أو تساوي
tree[i]، أو كانت القيمة الأصغر أقل من أو تساويtree[i]، فأعِدfalse. - بعد العقدة الأخيرة، أعِد
true.
def isValidBST(tree):
n = len(tree)
def largest(i):
# Largest value in the subtree at index i, or -1 when that spot is empty.
if i >= n or tree[i] == -1:
return -1
return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))
def smallest(i):
# Smallest value in the subtree at index i, or 100001 when that spot is empty.
if i >= n or tree[i] == -1:
return 100001
return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))
for i in range(n):
if tree[i] == -1:
continue
# Everything on the left must be smaller, everything on the right larger.
if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
return False
return Trueيجب أن تزداد القيم بالترتيب الوسطي زيادةً صارمة
الفكرة
تزور عملية الاجتياز بالترتيب الفرعي الأيسر، ثم العقدة، ثم الفرعي الأيمن. في شجرة البحث الثنائية، يكون هذا الترتيب مرتبًا: كل ما في اليسار أصغر، لذا يأتي أولًا، وكل ما في اليمين أكبر، لذا يأتي بعده. يقرأ المثال الأول 1, 3, 6, 8, 10, 12, 15.
ويصح العكس أيضًا، وهذا ما يجعلها اختبارًا. خذ أي عقدة v. في التسلسل الناتج عن الاجتياز بالترتيب، يقع الفرعي الأيسر بأكمله قبلها مباشرة، والفرعي الأيمن بأكمله بعدها مباشرة. إذا كان التسلسل يتزايد بصرامة، فكل قيمة تسبق v أصغر منها، وكل قيمة تليها أكبر منها، وبذلك تتحقق القاعدة عند v، وكذلك عند كل عقدة أخرى.
لذا اجتز الشجرة بالترتيب، واجمع القيم، وتحقق من كل قيمة بمقارنتها بالقيمة التي تسبقها. يقرأ المثال الثاني 5, 10, 6, 15, 20: فالانتقال من 10 إلى 6 يكشف أن العقدة في الجانب الخطأ. ويقرأ المثال الثالث 7, 12, 12، وتفشل القيمة المتكررة 12 في اجتياز التحقق الصارم. تُزار كل عقدة مرة واحدة، بزمن O(n)، وتستهلك القائمة مساحة O(n).
الخوارزمية
- اكتب
walk(i): إذا كان الموضع فارغًا، فتوقف؛ وإلا فانتقل إلى2*i+1، وأضفtree[i]، ثم انتقل إلى2*i+2. - استدعِ
walk(0)لجمع القيم بالترتيب. - لكل موضع
kبدءًا من1، إذا كانvalues[k-1] ≥ values[k]، فأعِدfalse. - أعِد
true.
def isValidBST(tree):
n = len(tree)
values = []
def walk(i):
# Left subtree, then the node, then the right subtree.
if i >= n or tree[i] == -1:
return
walk(2 * i + 1)
values.append(tree[i])
walk(2 * i + 2)
walk(0)
# A search tree read in order gives strictly increasing values.
for k in range(1, len(values)):
if values[k - 1] >= values[k]:
return False
return Trueمرّر النطاق المسموح به إلى أسفل الشجرة
الفكرة
انظر إلى القاعدة من منظور العقدة. يضع كل سلف حدًا واحدًا لها. إذا كانت العقدة تقع في الشجرة الفرعية اليسرى لسلف يحمل a، فيجب أن تكون قيمتها أقل من a؛ وإذا كانت تقع في الشجرة الفرعية اليمنى، فيجب أن تكون أكبر من a. تشكّل هذه الحدود مجتمعةً نطاقًا مفتوحًا واحدًا (low, high)، وتكون العقدة في موضعها الصحيح بالضبط عندما تقع قيمتها داخل هذا النطاق بصرامة.
يمكنك بناء هذا النطاق أثناء النزول. ليس للجذر أي حد. عند الانتقال من عقدة تحمل v إلى ابنها الأيسر، احتفظ بـ low وخفّض high إلى v؛ وعند الانتقال إلى ابنها الأيمن، احتفظ بـ high وارفع low إلى v. يكون الحد الجديد دائمًا أضيق من الحد الذي يحلّ محله، لأن v نفسها اجتازت التحقق ضمن النطاق القديم.
في المثال الثاني، تحصل 15 على النطاق (10, no limit) وتمرره إلى ابنها الأيسر على هيئة (10, 15). قيمة 6 أقل من 10، لذا يفشل التحقق عندها مباشرةً، من دون النظر إلى أي عقدة أخرى. تقع القيم بين 0 و10^5، لذا يؤدي -1 و100001 دور «لا حد».
احتفظ بالعقد المعلّقة في مكدس، مع نطاق كل منها. يُتحقَّق من كل عقدة مرة واحدة، بزمن O(n)، ويحتوي المكدس على العقد المعلّقة على امتداد مسار واحد، بمساحة O(h). ينهي أول نطاق غير صالح البحث.
الخوارزمية
- أضف
(0, -1, 100001)إلى المكدس: فهرس الجذر ونطاق مفتوح بلا حدّ فعلي. - اسحب
(i, low, high). إذا لم تكنtree[i]واقعةً بصرامة بينlowوhigh، فأعِدfalse. - إذا كان الابن الأيسر
2*i+1موجودًا، فأضِفه إلى المكدس بالنطاق(low, tree[i]). - إذا كان الابن الأيمن
2*i+2موجودًا، فأضِفه إلى المكدس بالنطاق(tree[i], high). - عندما يصبح المكدس فارغًا، أعِد
true.
def isValidBST(tree):
n = len(tree)
# Each entry: a node index and the open range (low, high) its value must fall in.
# -1 and 100001 lie outside every allowed value, so they mean "no limit".
stack = [(0, -1, 100001)]
while stack:
i, low, high = stack.pop()
value = tree[i]
if not (low < value < high):
return False
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append((left, low, value)) # the left side must stay below value
if right < n and tree[right] != -1:
stack.append((right, value, high)) # the right side must stay above value
return True
أخطاء شائعة وحالات حدّية
تتحقق معظم الإجابات الخاطئة من عدد قليل جدًا من الشروط، أو تتحقق من الشرط الصحيح باستخدام مقارنة غير صحيحة.
- مقارنة العقدة بأبنائها فقط. في
[10, 5, 15, -1, -1, 6, 20]تبدو كل علاقة بين أب وابنه صحيحة، لكن6لا يزال يخالف الحد الذي وضعته العقدة الجذرية قبل مستويين. - السماح بالقيم المتساوية. الترتيب صارم على كلا الجانبين، لذا فإن
[12, 7, 12]غير صالح. استخدمlow < v < highوvalues[k-1] < values[k]، ولا تستخدم أبدًا≤. - تمرير قيمة الأب وحدها إلى الأسفل. يحتاج الابن الأيسر إلى كلا الحدين: أن يكون أدنى من أبيه وأعلى من أي حد أدنى كان لدى أبيه. احتفظ بالنطاق الكامل.
- اختيار قيمة «بلا حد» يمكن أن تحملها إحدى العقد. تبدأ القيم من
0، لذا فإن حدًا أدنى مقداره0سيرفض عقدة صالحة تحمل0، كما في[0]. ابدأ بقيمة أدنى من كل القيم المسموح بها. - القراءة بعد نهاية المصفوفة. تحقّق من
2*i+1 < tree.lengthقبل قراءة ابن، واعتبر-1دالًا على عدم وجود ابن. - الخلط بين الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد تبدأ من 0 عند إجراء حساب
2*i+1، واقرأtree[i + 1].
أسئلة شائعة4
لماذا لا يكفي التحقق من كل عقدة مقارنةً بأبنائها للتأكد من صحة شجرة البحث الثنائية (BST)؟
تنطبق القاعدة على الأشجار الفرعية بأكملها. يجب أن تكون قيمة العقدة المتعمقة في الشجرة الفرعية اليمنى للجذر أكبر من قيمة الجذر، حتى لو كانت الابن الأيسر لعقدة أكبر بكثير. في [10, 5, 15, -1, -1, 6, 20]، تُعد 6 ابنًا أيسر مناسبًا للعقدة 15، لكنها تقع على يمين 10، لذا فالشجرة ليست شجرة بحث. تحتاج إلى الحدود التي يحددها كل سلف، وليس الوالد فقط.
ما هو التعقيد الزمني للتحقق من صحة شجرة بحث ثنائية؟
تتحقق كلتا الطريقتين القياسيتين، التحقق بالترتيب الوسطي والتحقق بالنطاق، من كل عقدة مرة واحدة، لذا تستغرقان زمنًا قدره O(n). يحتاج التحقق بالنطاق إلى مساحة إضافية قدرها O(h) للمكدس، حيث إن h هو العمق. تعمل أيضًا مقارنة كل عقدة بمجموعتيها الفرعيتين كاملتين، لكنها تكلّف O(n × h)، وهو ما يصل إلى O(n²) في شجرة على شكل مسار.
هل يمكنك التحقق من صحة شجرة بحث ثنائية (BST) باستخدام الاجتياز بالترتيب الوسطي دون تخزين كل قيمة؟
نعم. لا يقارن فحص الترتيب الوسطي القيمة إلا بالقيمة التي تسبقها مباشرةً، لذا احتفظ بالقيمة السابقة في متغير بدلًا من قائمة. اجتز الشجرة بالترتيب الوسطي باستخدام الاستدعاء الذاتي أو مكدس صريح، وأعِد false فور أن تكون قيمة ما غير أكبر من القيمة السابقة. بذلك تنخفض المساحة الإضافية إلى O(h).
هل يمكن لشجرة البحث الثنائية أن تحتوي على قيم مكررة؟
ليس وفقًا للتعريف الصارم المستخدم هنا: يجب أن تكون كل قيمة يسارًا أصغر، وكل قيمة يمينًا أكبر، لذلك لا يمكن أبدًا أن تتوافق قيمتان متساويتان معًا. تسمح بعض الكتب المدرسية بالقيم المكررة في أحد الجانبين، على سبيل المثال القيم المتساوية إلى اليمين. وفقًا لهذه القاعدة، ستغيّر إحدى المقارنتين الصارمتين إلى ≤، لذا اقرأ التعريف قبل كتابة التحقق.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def isValidBST(tree):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
tree = [8, 3, 12, 1, 6, 10, 15]
المتوقع
true