بناء شجرة بحث ثنائية من مصفوفة جافا سكريبت

بناء شجرة البحث الثنائية مع المصفوفات

تعد أشجار البحث الثنائية (BSTs) بنية بيانات أساسية في علوم الكمبيوتر، مما يتيح البحث الفعال وإدراج وحذف العناصر. عند إنشاء BST من مصفوفة، يكمن المفتاح في فهم كيفية تقسيم المصفوفة للحفاظ على خصائص BST. يتضمن ذلك تقسيم المصفوفة بشكل متكرر إلى مصفوفتين فرعيتين يسارية ويمينية بناءً على قيمة الجذر المختارة.

في هذه المقالة، سنتعرف على عملية إنشاء BST من مصفوفة باستخدام JavaScript. الهدف هو تحديد جذر من المصفوفة، وتقسيم العناصر إلى شجرتين فرعيتين يمنى ويسرى، وتكرار هذه العملية بشكل متكرر لكل شجرة فرعية حتى يتم ترتيب جميع العناصر بشكل مناسب في الشجرة.

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

يسمح لنا هذا الأسلوب ببناء BST متوازن بكفاءة، بشرط أن يتم فرز المصفوفة. باتباع الخطوات الموضحة، ستتمكن من تنفيذ BST عامل في JavaScript، وحل المشكلات الشائعة مثل البحث بكفاءة عبر البيانات أو الحفاظ على البيانات المصنفة ديناميكيًا.

يأمر	مثال للاستخدام
Math.floor()	يُستخدم هذا الأمر لحساب نقطة المنتصف للمصفوفة عن طريق التقريب للأسفل. من المهم في بناء شجرة البحث الثنائية العثور على جذر الشجرة الفرعية. مثال: Let mid = Math.floor(nums.length / 2);
Array.prototype.slice()	تُستخدم هذه الطريقة لتقسيم المصفوفة إلى مصفوفتين فرعيتين يمنى ويسرى بناءً على نقطة المنتصف. فهو يساعد في تقسيم المصفوفة إلى أجزاء أصغر لإنشاء BST العودي. مثال: Let lSide = nums.slice(0, mid);
Array.prototype.push()	يدفع العناصر إلى مصفوفة أو قائمة انتظار، وهو أمر ضروري للنهج التكراري عند إضافة عقد جديدة لتتم معالجتها. مثال: queue.push({ العقدة: العقدة. اليسار، النطاق: الجانب الأيسر });
throw new Error()	يستخدم هذا الأمر لمعالجة الأخطاء. فهو يضمن عدم استمرار البرنامج مع المدخلات غير الصالحة. مثال: throw new Error("إدخال غير صالح: يجب أن تكون الأعداد مصفوفة غير فارغة.");
Array.isArray()	يتحقق مما إذا كان الإدخال عبارة عن صفيف صالح. يعد هذا الأمر مفيدًا للتحقق من صحة الإدخال لتجنب الأخطاء المحتملة أثناء إنشاء الشجرة. مثال: إذا (!Array.isArray(nums))
console.error()	يسجل رسائل الخطأ إلى وحدة التحكم لأغراض التصحيح. يساعد في تتبع المشكلات أثناء تنفيذ البرنامج. مثال: console.error(error.message);
Node()	تقوم وظيفة المنشئ هذه بإنشاء عقدة جديدة في شجرة البحث الثنائية بقيمة معينة. فهو الأساس لبناء هيكل الشجرة. مثال: Let Node = new Node(nums[mid]);
while()	يستخدم للتكرار على العناصر حتى يتم استيفاء الشرط. في النهج التكراري، تضمن هذه الحلقة معالجة جميع العقد في قائمة الانتظار. مثال: while (queue.length) { ... }
try { ... } catch { ... }	يتم استخدام هذه البنية لمعالجة الاستثناءات، مما يضمن أنه في حالة حدوث خطأ، يمكن للبرنامج إدارته دون التعطل. مثال: حاول { ... } التقاط (خطأ) { ... }

فهم بناء شجرة البحث الثنائية في جافا سكريبت

النص الأول الذي اكتشفناه يبني ملف باستخدام نهج العودي. تفيد هذه الطريقة في حل المشكلات التي تتطلب تقسيم البيانات إلى مشكلات فرعية أصغر. من خلال إيجاد العنصر الأوسط للمصفوفة، يمكننا تحديده باعتباره العقدة الجذرية للشجرة. يصبح الجانب الأيسر من المصفوفة، الذي يحتوي على عناصر أصغر من الجذر، الشجرة الفرعية اليسرى، بينما يصبح الجانب الأيمن، الذي يحتوي على عناصر أكبر، الشجرة الفرعية اليمنى. تتكرر هذه العملية بشكل متكرر حتى يتم إدراج جميع العناصر في الشجرة.

يسمح العودية بتدفق نظيف ومنطقي للخوارزمية. الأمر الرئيسي في هذا البرنامج النصي هو ، والذي يستخدم لحساب نقطة المنتصف للمصفوفة ويساعد في تقسيمها لمزيد من المعالجة. أمر مهم آخر هو ، الذي يقسم المصفوفة إلى نصفين، مما يسمح لنا بإنشاء الشجرتين الفرعيتين اليمنى واليسرى بشكل متكرر. يضمن هذا النهج المعياري تشكيل BST بشكل صحيح مع الحفاظ على هيكله المفرز. تضمن هذه الإستراتيجية العودية أن تكون الشجرة متوازنة، بشرط أن يتم فرز المصفوفة.

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

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

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  buildTree(nums) {
    if (nums.length === 0) return null;
    let mid = Math.floor(nums.length / 2);
    let node = new Node(nums[mid]);
    node.left = this.buildTree(nums.slice(0, mid));
    node.right = this.buildTree(nums.slice(mid + 1));
    return node;
  }
}
const nums = [1, 2, 3, 4, 5, 6, 7];
const bst = new BinarySearchTree();
bst.root = bst.buildTree(nums);
console.log(bst.root);

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  buildTree(nums) {
    if (nums.length === 0) return null;
    let mid = Math.floor(nums.length / 2);
    this.root = new Node(nums[mid]);
    let queue = [{ node: this.root, range: nums }];
    while (queue.length) {
      let { node, range } = queue.shift();
      let midIndex = Math.floor(range.length / 2);
      let leftSide = range.slice(0, midIndex);
      let rightSide = range.slice(midIndex + 1);
      if (leftSide.length) {
        node.left = new Node(leftSide[Math.floor(leftSide.length / 2)]);
        queue.push({ node: node.left, range: leftSide });
      }
      if (rightSide.length) {
        node.right = new Node(rightSide[Math.floor(rightSide.length / 2)]);
        queue.push({ node: node.right, range: rightSide });
      }
    }
  }
}
const nums = [1, 2, 3, 4, 5, 6, 7];
const bst = new BinarySearchTree();
bst.buildTree(nums);
console.log(bst.root);

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  buildTree(nums) {
    if (!Array.isArray(nums) || nums.length === 0) {
      throw new Error("Invalid input: nums must be a non-empty array.");
    }
    return this._buildRecursive(nums);
  }
  _buildRecursive(nums) {
    if (nums.length === 0) return null;
    let mid = Math.floor(nums.length / 2);
    let node = new Node(nums[mid]);
    node.left = this._buildRecursive(nums.slice(0, mid));
    node.right = this._buildRecursive(nums.slice(mid + 1));
    return node;
  }
}
try {
  const nums = [1, 2, 3, 4, 5, 6, 7];
  const bst = new BinarySearchTree();
  bst.root = bst.buildTree(nums);
  console.log(bst.root);
} catch (error) {
  console.error(error.message);
}

خوارزميات شجرة البحث الثنائية الفعالة

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

هناك اعتبار آخر مهم عند إنشاء BST وهو كيفية التعامل مع القيم المكررة. في كثير من الحالات، يتم إما عدم السماح بالتكرارات أو معالجتها عن طريق وضعها بشكل متسق في الشجرة الفرعية اليسرى أو اليمنى. على سبيل المثال، يمكن للمرء وضع التكرارات على الشجرة الفرعية الصحيحة بشكل افتراضي للحفاظ على سلامة BST. يمكن أن تؤثر إدارة التكرارات بشكل مناسب على كفاءة وأداء الشجرة أثناء مرحلة الإنشاء والعمليات اللاحقة.

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

1. كيف يساعد العودية في بناء BST؟
2. يقسم التكرار المصفوفة إلى مصفوفات فرعية أصغر ويعين العنصر الأوسط كالجذر، وهي عملية تتكرر حتى يتم وضع جميع العناصر.
3. كيف تتعامل مع القيم المكررة في شجرة البحث الثنائية؟
4. يمكنك وضع التكرارات بشكل متسق في الشجرة الفرعية اليسرى أو اليمنى. وهذا يضمن الحفاظ على خصائص BST.
5. ما هي أهمية في البناء BST؟
6. يساعد في تحديد العنصر الأوسط للمصفوفة، والذي يصبح جذر الشجرة الفرعية.
7. لماذا تعتبر موازنة الأشجار مهمة في BST؟
8. تمنع عملية التوازن الشجرة من الانحراف، مما يضمن أن العمليات مثل البحث والإدراج والحذف تستغرق وقتًا O(log n).
9. كيف يمكن تحسين بناء الشجرة؟
10. يتم استخدامه لتقسيم المصفوفة إلى مصفوفتين فرعيتين يسارية ويمينية، مما يسمح بالبناء المتكرر للأشجار الفرعية للشجرة.
11. ما الذي يجب التحقق منه عند التحقق من صحة الإدخال؟
12. تحقق مما إذا كان الإدخال عبارة عن مصفوفة مرتبة ومرتبة. وهذا يضمن إمكانية إنشاء الشجرة بشكل صحيح دون أخطاء.
13. ما هو الدور الذي تلعبه معالجة الأخطاء في بناء BST؟
14. معالجة الأخطاء، مثل الاستخدام ، يساعد في تحديد المشكلات مبكرًا ويمنع التطبيق من التعطل.
15. لماذا قد تختار النهج التكراري بدلاً من التكرار؟
16. التكرار باستخدام أ ، يتجنب المشكلات المحتملة المتعلقة بعمق التكرار، خاصة في مجموعات البيانات الكبيرة حيث يمكن أن يحدث تجاوز لسعة المكدس.
17. كيف يمكن لأشجار AVL وأشجار الأحمر والأسود الحفاظ على التوازن؟
18. تقوم هذه الخوارزميات بإعادة توازن الشجرة تلقائيًا بعد كل إدراج أو حذف لضمان أوقات البحث اللوغاريتمية.
19. ما أهمية اختيار العنصر الأوسط كجذر؟
20. اختيار العنصر الأوسط يضمن بقاء الشجرة متوازنة، مما يمنع مسارات البحث غير الفعالة.

يتضمن إنشاء شجرة بحث ثنائية من مصفوفة تقسيم المصفوفة إلى مصفوفات فرعية وتعيين العنصر الأوسط كجذر. تساعد هذه العملية في الحفاظ على بنية شجرة فعالة ومتوازنة. تعد الشجرة المتوازنة أمرًا ضروريًا لضمان عمليات البحث والإدراج والحذف السريعة.

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