Kth Smallest Element in a BST
تحصل على شجرة بحث ثنائية على شكل المصفوفة root بترتيب الكومة: الجذر عند الفهرس 0، وأبناء الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -1 إلى موضع فارغ. قد تنتهي المصفوفة بإدخالات -1 إضافية. عند كل عقدة، تحتوي الشجرة الفرعية اليسرى على قيم أصغر فقط، والشجرة الفرعية اليمنى على قيم أكبر فقط.
أعِد القيمة الأصغر رقم k في الشجرة، مع بدء العد من 1.
الدالة
- rootinteger-array
- شجرة البحث الثنائية بترتيب المستويات، مع استخدام -1 للمواقع الفارغة
- kinteger
- الموضع المطلوب إيجاده بالترتيب التصاعدي، بدءًا من 1
- تُرجعinteger
- القيمة الأصغر ذات الترتيب k في الشجرة
القيود
1 ≤ root.length ≤ 32767- كل قيمة من
root[i]إما-1أو قيمة تحقق0 ≤ root[i] ≤ 105. root[0]لا تكون أبدًا-1، لذا تحتوي الشجرة على عقدة واحدة على الأقل.- قد تنتهي المصفوفة بعناصر
-1إضافية بعد العقدة الأخيرة. - كلا الابنين في الموضع الفارغ فارغان أيضًا، والعمق لا يتجاوز
14. - تنطبق قاعدة الترتيب عند كل عقدة، لذا لا تظهر أي قيمة مرتين.
1 ≤ k ≤عدد العقد في الشجرة.
أمثلة
- المدخلات
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- المخرجات
- 29
- الشرح
- بترتيب تصاعدي، القيم هي
6, 17, 22, 29, 41, 65, 90، والقيمة الرابعة هي29. وهي الأكبر من بين القيم الأربع في الشجرة الفرعية اليسرى للجذر.
- المدخلات
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- المخرجات
- 2
- الشرح
- أصغر قيمة تنهي المسار الذي يستمر إلى اليسار:
12،5،2. لا يغيّر كلٌّ من7أسفل9وحشو-1ذلك.
سؤال إضافي
إذا كانت الشجرة تتغير كثيرًا وطُلب منك إيجاد القيمة الـk الأصغر مرات عديدة، فما الذي يمكن أن تخزّنه كل عقدة بحيث يستغرق كل استعلام O(h)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أي طريقة لاجتياز شجرة بحث ثنائية تسرد قيمها من الأصغر إلى الأكبر؟
تؤدي زيارة الشجرة الفرعية اليسرى، ثم العقدة، ثم الشجرة الفرعية اليمنى إلى ترتيب تصاعدي. القيمة رقم
kالتي ينتجها هذا الاجتياز هي الإجابة، لذا يمكنك التوقف عندها.استخدم مكدسًا. بدءًا من العقدة الحالية، أضف العقد إلى المكدس أثناء الانتقال إلى الابن الأيسر. أخرج العقدة من أعلى المكدس وعدّها؛ وتوقّف عند عملية الإخراج رقم
k. وإلا فانتقل إلى الابن الأيمن للعقدة التي أخرجتها عند2*i+2وكرّر.
الحل
تقرأ عملية الاجتياز بالترتيب الوسطي (الفرع الأيسر، العقدة، الفرع الأيمن) قيم شجرة البحث الثنائية بترتيب تصاعدي، لذا تكون القيمة رقم k التي تصل إليها هي الإجابة. نفّذ الاجتياز باستخدام مكدس خاص بك وتوقّف عندها؛ لا حاجة إلى الفرز.
اجمع كل القيم ورتّبها
الفكرة
تجاهل البنية: احتفظ بكل عنصر لا يساوي -1، ثم رتّب العناصر وأعِد القيمة في الموضع k-1. في المثال الأول، تكون القائمة المرتبة 6, 17, 22, 29, 41, 65, 90، ويحتوي الموضع 3 على 29.
هذا صحيح لأي شجرة، سواء كانت مرتبة أم لا. وهذه أيضًا كلفته: فهو يتجاهل الترتيب الموجود أصلًا في الشجرة، ويتطلب O(n log n) للترتيب وذاكرة بحجم O(n) لنسخ العناصر.
الخوارزمية
- اجمع كل قيمة في
rootلا تساوي-1. - رتّب القيم التي جمعتها بترتيب تصاعدي.
- أعِد القيمة الموجودة في الموضع
k-1.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]اجتياز بالترتيب إلى قائمة
الفكرة
أسفل أي عقدة، يحتوي الفرع الأيسر على قيم أصغر فقط، ويحتوي الفرع الأيمن على قيم أكبر فقط. زُر الفرع الأيسر، ثم العقدة، ثم الفرع الأيمن، وكرّر ذلك داخل كل فرع: تقع كل عقدة بعد جميع القيم الأصغر وقبل جميع القيم الأكبر، لذا يكون الناتج مرتبًا. في المثال الأول، ينتج عن المرور 6, 17, 22, 29, 41, 65, 90.
يمرّ واحد يستبدل عملية الفرز: زمن O(n)، ومساحة O(n) للقائمة. ومع ذلك، يزور الشجرة بأكملها، حتى عندما تكون k = 1، حيث تكون الإجابة عند نهاية المسار الأيسر الأقصى.
الخوارزمية
- اكتب
inorder(i): أعد القيمة عند موضع فارغ (بعد النهاية أو-1). - وإلا، استدعِ
inorder(2*i+1)، وأضفroot[i]إلى القائمة، ثم استدعِinorder(2*i+2). - استدعِ
inorder(0). - أعِد عنصر القائمة عند الموضع
k-1.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedاجتياز تكراري بالترتيب يتوقف عند k
الفكرة
تتيح لك المكدّسة الصريحة إيقاف الاجتياز في منتصفه. تحرّك إلى اليسار قدر الإمكان، مع دفع كل عقدة إلى المكدّسة. العقدة الموجودة في الأعلى هي أصغر قيمة لم تُحتسب بعد، لأن كل ما هو أصغر منها يقع في فرعها الأيسر، وهو فارغ أو سبق احتسابه. أخرجها من المكدّسة واحتسبها؛ يأتي فرعها الأيمن بعد ذلك في الترتيب التصاعدي.
بالنسبة إلى k = 4 في المثال الأول: ادفع 41، ثم 17، ثم 6. أخرج 6، ثم 17، وانتقل إلى ابنها الأيمن: ادفع 29 و22. أخرج 22، ثم 29، وهي الرابعة. لا يصل الاجتياز مطلقًا إلى 65 أو 90.
تحتوي المكدّسة على عقدة واحدة كحد أقصى لكل مستوى، لذا تكون المساحة O(h). ينزل الاجتياز مرة واحدة، ثم يجري الإخراج من المكدّسة k مرات: الزمن O(h + k).
الخوارزمية
- ابدأ بمكدس فارغ و
i = 0. - ما دام
iعقدة فعلية، ادفعه إلى المكدس وانتقل إلى2*i+1. - أخرج العنصر العلوي وضعه في
i، واطرح1منk. - إذا أصبح
kالآن0، فأعِدroot[i]. - وإلا، انتقل إلى
2*i+2وعُد إلى الخطوة 2.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
أخطاء شائعة وحالات حدّية
- قراءة المصفوفة بترتيب الفهارس. الترتيب حسب المستوى ليس مرتبًا: يبدأ المثال الأول بـ
41, 17, 65. - خطأ بمقدار واحد في
k. يبدأ العد من1: أعد العنصر عند الموضعk-1في القائمة، وأوقف عملية الاجتياز عندما يصل العد إلىk. - تجاوز الشجرة الفرعية اليمنى بعد إخراج عنصر من المكدس. في المثال الثاني، يقع
9و7في الشجرة الفرعية اليمنى للعقدة5، ولن تحتسبهما عملية الاجتياز أبدًا. - اعتبار الابن المفقود ابنًا حقيقيًا. يكون الابن فارغًا إذا كان فهرسه يتجاوز نهاية المصفوفة أو كانت قيمته
-1: تقع22عند الفهرس9، لذا يقع الابنان19و20بعد نهاية المصفوفة. - تبدأ المصفوفات في Lua وR من الفهرس 1. أبقِ فهارس العقد تبدأ من 0 عند استخدام
2*i+1، واقرأroot[i + 1].
أسئلة شائعة3
ما هو التعقيد الزمني لإيجاد العنصر الأصغر رقم k في شجرة بحث ثنائية (BST)؟
تستغرق الجولة التكرارية بالترتيب الوسطي زمنًا قدره O(h + k) ومساحة إضافية قدرها O(h) لشجرة عمقها h. في أسوأ الحالات، عندما يكون k = n أو تكون الشجرة على شكل مسار، يكون التعقيد O(n).
كيف تجد العنصر الأكبر رقم k في شجرة بحث ثنائية؟
اعكس ترتيب الاجتياز: الشجرة الفرعية اليمنى، ثم العقدة، ثم الشجرة الفرعية اليسرى. يسرد ذلك القيم بترتيب تنازلي. انتقل إلى اليمين قدر الإمكان مع دفع العقد إلى المكدس، ثم أخرج عقدة واحسبها، وانتقل إلى الابن الأيسر بعد كل إخراج. العقدة التي تُخرج في المرة k هي الأكبر رقم k.
كيف توقف الاجتياز التكراري بالترتيب عند القيمة رقم k؟
احتفظ بعدّاد خارج الاستدعاء الذاتي، وابدأه بالقيمة k. اطرح 1 بعد عودة الفرع الأيسر لعقدة، وسجّل قيمة العقدة عندما يصل العدّاد إلى 0. بعد كل استدعاء، ارجع فورًا إذا تم تسجيل الإجابة. عندها يصبح الاستدعاء الذاتي مماثلًا لنسخة المكدّس: زمن O(h + k)، ومساحة O(h).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def kthSmallest(root, k):
# اكتب الكود هنااختبار #1
اختبار #2
الوسائط
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
الإخراج المتوقع
29