Balanced Binary Tree

+10

تحتوي المصفوفة root على شجرة ثنائية. يوجد الجذر عند الفهرس 0، ويوجد ابنا الفهرس i عند 2*i+1 (الأيسر) و2*i+2 (الأيمن)، وتشير -1 إلى موضع فارغ، وقد تتبعها عناصر إضافية قيمتها -1 في النهاية.

أعِد true إذا كانت الشجرة متوازنة الارتفاع، أي إذا كان الفرق بين ارتفاعَي الشجرتين الفرعيتين اليسرى واليمنى عند كل عقدة لا يتجاوز 1، وإلا فأعِد false. ارتفاع الشجرة الفرعية هو عدد العقد في أطول مسار نزولي فيها؛ وارتفاع الشجرة الفرعية الفارغة هو 0.

الدالة

isBalanced(root: integer-array) → boolean

rootinteger-array: الشجرة الثنائية بترتيب المستويات، مع ‎-1‎ للدلالة على موضع فارغ
تُرجعboolean: صحيح إذا كان ارتفاعا الشجرتين الفرعيتين لكل عقدة يختلفان بمقدار لا يتجاوز 1، وخطأ خلاف ذلك

القيود

1 ≤ root.length ≤ 32767
كل root[i] يساوي -1 أو قيمة ضمن النطاق 0 ≤ root[i] ≤ 10⁵.
root[0] لا تكون أبدًا -1، لذا تحتوي الشجرة على عقدة واحدة على الأقل.
قد تنتهي المصفوفة بإدخالات -1 إضافية بعد العقدة الأخيرة.
كلا ابني الموضع الفارغ فارغان أيضًا، والعمق لا يتجاوز 14.
قيم العقد متميزة.

أمثلة

المدخلات: root = [5, 2, 9, -1, -1, 7, 11]
المخرجات: true
الشرح: الشجرة الفرعية اليسرى للجذر هي العقدة الوحيدة 2، وارتفاعها 1. أما شجرته الفرعية اليمنى 9 و7 و11 فارتفاعها 2. والفرق بينهما 1، ولكل عقدة أخرى شجرتان فرعيتان متساويتان في الارتفاع.

المدخلات: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
المخرجات: false
الشرح: يبلغ ارتفاع كلا جانبي الجذر 3، لكن العقدة 3 لا تحقق الشرط: ارتفاع شجرتها الفرعية اليسرى 1، 0 هو 2، أما اليمنى فهي فارغة.

المدخلات: root = [4, 2, -1, 1]
المخرجات: false
الشرح: للعقدة الجذر سلسلة 2، و1 على يسارها، وارتفاعها 2، ولا شيء على يمينها، وارتفاعه 0. الفرق البالغ 2 كبير جدًا.

سؤال إضافي

هل يمكنك فحص الشجرة دون استخدام الاستدعاء الذاتي، باستخدام مكدس صريح؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

تنطبق القاعدة على كل عقدة، لذا قد تفشل شجرة تبدو جذورها متوازنة حتى لو بدت متوازنة، عند مستوى أدنى، كما يحدث في المثال الثاني عند 3. تحسب عملية المرور بترتيب لاحق ارتفاع كل شجرة فرعية مرة واحدة، وتنقل الإشارة إلى الإخفاق إلى الأعلى فور ظهوره، بزمن O(n).

أعِد حساب الارتفاعات عند كل عقدة

الفكرة

حوّل التعريف إلى شيفرة. تكون height(i) مساويةً لـ 0 في الموضع الفارغ، وتساوي ارتفاع الابن الأطول زائد 1 في غير ذلك. قارن ارتفاعَي الابنين عند كل عقدة فعلية؛ أول عقدة يختلف فيها الارتفاعان بأكثر من 1 تجعل الإجابة false.

يفحص كل اختبار الشجرة الفرعية بأكملها أسفل عقدته، لذا تُفحص العقدة مرةً واحدةً لكل عقدة فوقها: O(n·h). مع 14 مستوى على الأكثر، تستهلك شجرة كاملة تضم 16,383 عقدة نحو 2 × 10^5 خطوة. أما سلسلة من n عقد، فتستهلك O(n²).

الخوارزمية

عرّف height(i) بأنه 0 للمؤشر الذي يتجاوز نهاية البنية أو يساوي -1، وبأنه 1 + max(height(2*i+1), height(2*i+2)) للعقدة الفعلية.
زُر كل مؤشر i يحتوي على عقدة فعلية.
إذا اختلفت height(2*i+1) وheight(2*i+2) بأكثر من 1، فأعِد false.
إذا انتهت الحلقة من دون إخفاق، فأعِد true.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

اجتياز واحد بالترتيب اللاحق يُبلغ عن الارتفاع أو الإخفاق

الفكرة

يتطلب الفحص عند العقدة معرفة ارتفاعَي شجرتَيها الفرعيتين، وهما أيضًا ما تحتاج إليه العقدة للإبلاغ عن ارتفاعها. لذا احصل على كليهما من زيارة واحدة بترتيب ما بعد الترتيب: يُرجع كل استدعاء ارتفاع شجرته الفرعية بعد عودة كلا الابنين.

يجب أيضًا أن ينتقل الإخفاق في مستوى أدنى إلى الأعلى. فالارتفاع الحقيقي لا يكون سالبًا أبدًا، لذا استخدم -1 للدلالة عليه: يُرجع الاستدعاء -1 عندما يُرجع أحد الأبناء -1 أو يختلف ارتفاعا الابنين بأكثر من 1. في المثال الثاني، ترى العقدة 3 الارتفاعين 2 و0 وتُرجع -1، وتمرره الجذر كما هو من دون زيارة جانبه الأيمن.

لا تتم زيارة أي عقدة مرتين، لذا فالزمن هو O(n)، مع O(h) من الاستدعاءات على المكدس.

الخوارزمية

اكتب check(i). إذا كان الفهرس يتجاوز النهاية أو يساوي -1، فأعد 0.
احسب left = check(2*i+1). إذا كانت قيمته -1، فأعد -1.
احسب right = check(2*i+2). إذا كانت قيمته -1، أو كان الفرق بين left وright أكبر من 1، فأعد -1.
وإلا فأعد 1 + max(left, right).
أعِد ما إذا كانت قيمة check(0) لا تساوي -1.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

أخطاء شائعة وحالات حدّية

التحقق من الجذر فقط. في المثال الثاني، ارتفاع كل جانب من الجذر هو 3، ومع ذلك فإن العقدة 3 يختلف ارتفاعها بمقدار 2.
مقارنة أقصر الأوراق وأعمقها. في أصغر شجرة متوازنة ارتفاعها 6، تقع الأوراق عند العمقين 4 و6، وتجتاز كل عقدة فيها الاختبار.
فقدان حالة الفشل أثناء الصعود. إذا أعادت إحدى العقد الفرعية -1 وحسبت العقدة الأم 1 + max(-1, 2)، تتحول حالة الفشل مجددًا إلى ارتفاع.
استخدام طول المصفوفة بوصفه الارتفاع. تجعل العناصر اللاحقة -1 المصفوفة أطول من عمق الشجرة.
في Lua وR، تبدأ المصفوفات من 1. أبقِ فهارس العقد تبدأ من 0 لاستخدام 2*i+1، واقرأ root[i + 1].

أسئلة شائعة3

ما هو التعقيد الزمني للشجرة الثنائية المتوازنة؟

تمريرة واحدة بترتيب ما بعد الترتيب تزور كل عقدة مرة واحدة: زمن O(n) ومساحة مكدس O(h) لشجرة ارتفاعها h. إعادة حساب الارتفاعات عند كل عقدة تكلّف O(n·h)، وتصبح O(n²) في سلسلة.

ماذا يعني أن تكون الشجرة الثنائية متوازنة من حيث الارتفاع؟

في كل عقدة، لا يختلف ارتفاعا الشجرتين الفرعيتين اليسرى واليمنى بأكثر من 1. تستعيد أشجار AVL هذه الخاصية بعد كل عملية إدراج وحذف، مما يحافظ على ارتفاعها عند O(log n).

هل تكون الشجرة الثنائية الكاملة متوازنة دائمًا؟

نعم. كل مستوى في الشجرة المكتملة ممتلئ باستثناء المستوى الأخير ربما، الذي يمتلئ من اليسار، لذا يختلف ارتفاعا الشجرتين الفرعيتين عند أي عقدة بمقدار لا يزيد على 1. والعكس غير صحيح: فقد تحتوي الشجرة المتوازنة على فجوات في الجهة اليسرى من مستواها الأخير.

def isBalanced(root):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

root = [5, 2, 9, -1, -1, 7, 11]

الإخراج المتوقع

true