الأشجار الثنائية في JavaScript: دليل كامل

إنفورماتيك ديجيتال » الخوارزميات » الأشجار الثنائية في جافا سكريبت: دليل شامل

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

الأشجار الثنائية في جافا سكريبت

الأشجار الثنائية هي بنية بيانات هرمية، حيث يمكن لكل عقدة أن تحتوي على طفلين على الأكثر: طفل أيسر وطفل أيمن. تُمثَّل كل عقدة بكائن يحتوي على قيمة ومراجع لأبنائها. تتميز هذه البنية بتعدد استخداماتها، وتُستخدم في العديد من مجالات علوم الحاسوب، مثل معالجة البيانات، وخوارزميات البحث ، والتحسين.

لماذا نتعلم عن الأشجار الثنائية في JavaScript؟

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

تنفيذ شجرة ثنائية في JavaScript

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

class Nodo {
  constructor(valor) {
    this.valor = valor;
    this.izquierdo = null;
    this.derecho = null;
  }
}

class ArbolBinario {
  constructor() {
    this.raiz = null;
  }
  
  // Métodos del árbol binario
}

في هذا المثال، نقوم بإنشاء فئة Nodo الذي يمثل كل عقدة من الشجرة، والفئة ArbolBinario والتي هي المسؤولة عن إدارة هيكل وعمليات الشجرة. تحتوي كل عقدة على قيمة ومراجع لأبنائها من اليسار واليمين، والتي يتم تهيئتها على النحو التالي: null تقصير. يتم تمثيل جذر الشجرة بواسطة السمة raiz الطبقة ArbolBinario.

العمليات الأساسية على الأشجار الثنائية

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

إدراج عنصر في شجرة ثنائية

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

class ArbolBinario {
  // ...

  insertar(valor) {
    const nuevoNodo = new Nodo(valor);

    if (this.raiz === null) {
      this.raiz = nuevoNodo;
    } else {
      this.insertarNodo(this.raiz, nuevoNodo);
    }
  }

  insertarNodo(nodo, nuevoNodo) {
    if (nuevoNodo.valor < nodo.valor) {
      if (nodo.izquierdo === null) {
        nodo.izquierdo = nuevoNodo;
      } else {
        this.insertarNodo(nodo.izquierdo, nuevoNodo);
      }
    } else {
      if (nodo.derecho === null) {
        nodo.derecho = nuevoNodo;
      } else {
        this.insertarNodo(nodo.derecho, nuevoNodo);
      }
    }
  }
}

في هذا المثال الدالة insertar(valor) ينشئ عقدة جديدة بالقيمة المحددة ويتحقق مما إذا كان جذر الشجرة هو null. إذا كان الأمر كذلك، قم بتعيين العقدة الجديدة كجذر. وإلا، قم باستدعاء الوظيفة insertarNodo(nodo, nuevoNodo) للعثور على الموضع الصحيح للعقدة الجديدة.

البحث عن عنصر في شجرة ثنائية

يتضمن البحث عن عنصر في شجرة ثنائية التنقل عبر الشجرة بطريقة منظمة للعثور على العقدة التي تحتوي على القيمة المطلوبة. فيما يلي مثال لكيفية تنفيذ البحث عن عنصر في شجرة ثنائية:

class ArbolBinario {
  // ...

  buscar(valor) {
    return this.buscarNodo(this.raiz, valor);
  }

  buscarNodo(nodo, valor) {
    if (nodo === null || nodo.valor === valor) {
      return nodo;
    } else if (valor < nodo.valor) {
      return this.buscarNodo(nodo.izquierdo, valor);
    } else {
      return this.buscarNodo(nodo.derecho, valor);
    }
  }
}

في هذا المثال الدالة buscar(valor) يستدعي الوظيفة buscarNodo(nodo, valor) تمرير جذر الشجرة والقيمة التي تريد البحث عنها. الوظيفة buscarNodo(nodo, valor) يقوم بإجراء بحث متكرر في الشجرة، للتحقق مما إذا كانت العقدة الحالية هي null أو إذا كانت قيمتها تتطابق مع القيمة التي تم البحث عنها. اعتمادًا على المقارنة، يستمر البحث عن الطفل الأيسر أو الأيمن.

حذف عنصر في شجرة ثنائية

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

class ArbolBinario {
  // ...

  eliminar(valor) {
    this.raiz = this.eliminarNodo(this.raiz, valor);
  }

  eliminarNodo(nodo, valor) {
    if (nodo === null) {
      return null;
    } else if (valor < nodo.valor) {
      nodo.izquierdo = this.eliminarNodo(nodo.izquierdo, valor);
      return nodo;
    } else if (valor > nodo.valor) {
      nodo.derecho = this.eliminarNodo(nodo.derecho, valor);
      return nodo;
    } else {
      if (nodo.izquierdo === null && nodo.derecho === null) {
        return null;
      } else if (nodo.izquierdo === null) {
        return nodo.derecho;
      } else if (nodo.derecho === null) {
        return nodo.izquierdo;
      } else {
        const sucesor = this.encontrarSucesor(nodo.derecho);
        nodo.valor = sucesor.valor;
        nodo.derecho = this.eliminarNodo(nodo.derecho, sucesor.valor);
        return nodo;
      }
    }
  }

  encontrarSucesor(nodo) {
    let sucesor = nodo;
    while (sucesor.izquierdo !== null) {
      sucesor = sucesor.izquierdo;
    }
    return sucesor;
  }
}

في هذا المثال الدالة eliminar(valor) يستدعي الوظيفة eliminarNodo(nodo, valor) تمرير جذر الشجرة والقيمة المراد حذفها. الوظيفة eliminarNodo(nodo, valor) يقوم بإجراء حذف متكرر، مع الأخذ في الاعتبار حالات مختلفة اعتمادًا على بنية الشجرة. إذا كانت العقدة الحالية هي null، يتم إرجاعه null. إذا كانت القيمة التي تم البحث عنها أقل من قيمة العقدة الحالية، فسيتم إجراء الحذف على الطفل الأيسر. إذا كان أكبر سناً يتم إجراؤه على الابن الأيمن. إذا كانت العقدة تحتوي على كلا الطفلين، فسيتم العثور على الخليفة الأقرب ويتم إجراء تبديل القيمة قبل إزالة الخليفة.

العمليات المتقدمة على الأشجار الثنائية

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

التنقل حسب الترتيب في شجرة ثنائية

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

class ArbolBinario {
  // ...

  recorridoEnOrden() {
    this.recorrerEnOrden(this.raiz);
  }

  recorrerEnOrden(nodo) {
    if (nodo !== null) {
      this.recorrerEnOrden(nodo.izquierdo);
      console.log(nodo.valor);
      this.recorrerEnOrden(nodo.derecho);
    }
  }
}

في هذا المثال الدالة recorridoEnOrden() يستدعي الوظيفة recorrerEnOrden(nodo) مرورا بجذر الشجرة. الوظيفة recorrerEnOrden(nodo) يقوم بإجراء عملية مسح متكررة بالترتيب، وطباعة قيمة العقدة الحالية بين الاستدعاءات للأطفال الأيسر والأيمن.

عبور مسبق لشجرة ثنائية

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

class ArbolBinario {
  // ...

  recorridoPreOrden() {
    this.recorrerPreOrden(this.raiz);
  }

  recorrerPreOrden(nodo) {
    if (nodo !== null) {
      console.log(nodo.valor);
      this.recorrerPreOrden(nodo.izquierdo);
      this.recorrerPreOrden(nodo.derecho);
    }
  }
}

في هذا المثال الدالة recorridoPreOrden() يستدعي الوظيفة recorrerPreOrden(nodo) مرورا بجذر الشجرة. الوظيفة recorrerPreOrden(nodo) يقوم بإجراء عملية مسح متكررة في الترتيب المسبق، وطباعة قيمة العقدة الحالية قبل استدعاء الأبناء الأيسر والأيمن.

عبور ما بعد الترتيب لشجرة ثنائية

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

class ArbolBinario {
  // ...

  recorridoPostOrden() {
    this.recorrerPostOrden(this.raiz);
  }

  recorrerPostOrden(nodo) {
    if (nodo !== null) {
      this.recorrerPostOrden(nodo.izquierdo);
      this.recorrerPostOrden(nodo.derecho);
      console.log(nodo.valor);
    }
  }
}

في هذا المثال الدالة recorridoPostOrden() يستدعي الوظيفة recorrerPostOrden(nodo) مرورا بجذر الشجرة. الوظيفة recorrerPostOrden(nodo) يقوم بإجراء عملية مسح متكررة بعد الترتيب، مع استدعاء الأطفال الأيسر والأيمن أولاً ثم طباعة قيمة العقدة الحالية.

أفضل الممارسات للتعامل مع الأشجار الثنائية في JavaScript

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

1. قم بتوثيق الكود الخاص بك بشكل صحيح:يمكن أن تصبح الأشجار الثنائية معقدة بسرعة، لذا من المهم توثيق الكود الخاص بك بوضوح ودقة. اشرح غرض كل طريقة، ومعلماتها، وقيمة العائد المتوقعة. سيؤدي هذا إلى جعل الكود أسهل للفهم بالنسبة لك وللمطورين الآخرين الذين قد يعملون على المشروع في المستقبل.
2. استخدم أسماء وصفية للمتغيرات والطرق:اختر أسماء تعكس الغرض ووظيفة كل متغير وطريقة في تنفيذ الشجرة الثنائية الخاصة بك. سيؤدي هذا إلى جعل الكود الخاص بك أكثر قابلية للقراءة والفهم، مما يجعل صيانته وتصحيح أخطائه أسهل.
3. إجراء اختبارات واسعة النطاق:قبل استخدام تنفيذ الشجرة الثنائية في مشروع حقيقي، تأكد من إجراء اختبار شامل للتأكد من أنه يعمل بشكل صحيح. إنشاء حالات اختبار تغطي سيناريوهات مختلفة والتحقق من أن النتائج كما هو متوقع. سيساعدك هذا في تحديد الأخطاء المحتملة والتأكد من أن التنفيذ الخاص بك موثوق.
4. ضع في اعتبارك الكفاءة:يمكن أن توفر الأشجار الثنائية كفاءة كبيرة في معالجة البيانات والبحث عنها، ولكن من المهم مراعاة كفاءة التنفيذ. قم بتقييم أداء الخوارزميات الخاصة بك وابحث عن فرص لتحسينها إذا لزم الأمر. على سبيل المثال، يمكنك استخدام تقنيات موازنة الأشجار لضمان بقاء ارتفاع الأشجار عند مستويات مقبولة.
5. الاستفادة من المكتبات والموارد الموجودةيحتوي JavaScript على مجموعة واسعة من المكتبات والموارد المتاحة التي يمكنها مساعدتك في العمل مع الأشجار الثنائية بكفاءة أكبر. ابحث عن المكتبات واستخدمها مثل binarytree أو bintrees للاستفادة من التنفيذات التي تم اختبارها وتحسينها بالفعل. بالإضافة إلى ذلك، راجع وثائق JavaScript الرسمية والموارد الموثوقة عبر الإنترنت لتوسيع نطاق معرفتك وحل التحديات المحتملة.
6. علق على الكود الخاص بك:بالإضافة إلى الوثائق الخارجية، من المهم إضافة التعليقات ذات الصلة داخل الكود الخاص بك. يشرح غرض أقسام أو أسطر معينة من التعليمات البرمجية، بالإضافة إلى الخوارزميات أو الأساليب المستخدمة. سيساعد هذا المطورين الآخرين (ونفسك في المستقبل) على فهم كيفية عمل التنفيذ الخاص بك بسرعة.

الأسئلة الشائعة

فيما يلي بعض الأسئلة الشائعة حول الأشجار الثنائية في JavaScript:

1. ما هو الفرق بين الشجرة الثنائية وشجرة البحث الثنائية؟ الشجرة الثنائية هي بنية بيانات هرمية حيث يمكن لكل عقدة أن تحتوي على ما يصل إلى طفلين. شجرة البحث الثنائية هي نوع معين من الشجرة الثنائية حيث يتم ترتيب قيم العقد بحيث تكون أصغر القيم في الطفل الأيسر وأكبر القيم في الطفل الأيمن. يتيح هذا إجراء عمليات بحث فعالة في الشجرة.
2. متى يجب عليك استخدام شجرة ثنائية بدلاً من هياكل البيانات الأخرى؟ يجب عليك استخدام شجرة ثنائية عندما تحتاج إلى بنية بيانات فعالة لتنظيم البيانات وتخزينها بشكل هرمي. تُعد الأشجار الثنائية مفيدة بشكل خاص عندما تحتاج إلى إجراء عمليات البحث والإدراج والحذف بكفاءة.
3. هل من الممكن موازنة الشجرة الثنائية بعد إجراء عمليات إدراج وحذف متعددة؟ نعم، من الممكن موازنة الشجرة الثنائية بعد إجراء العديد من عمليات الإدخال والحذف. توجد خوارزميات موازنة مختلفة، مثل شجرة AVL أو الشجرة الحمراء والسوداء، والتي تضمن الحفاظ على ارتفاع الشجرة عند مستويات مثالية ومنع الشجرة من أن تصبح غير متوازنة.
4. هل تستخدم الأشجار الثنائية لتخزين البيانات الرقمية فقط؟ لا، يمكن استخدام الأشجار الثنائية لتخزين أي نوع من البيانات، وليس فقط البيانات الرقمية. يمكنك تنفيذ أشجار ثنائية تخزن سلاسل نصية، أو كائنات مخصصة، أو أنواع أخرى من البيانات اعتمادًا على احتياجاتك.
5. هل هناك أي مكتبة JavaScript للعمل مع الأشجار الثنائية؟ نعم، هناك العديد من مكتبات JavaScript التي توفر وظائف متقدمة للعمل مع الأشجار الثنائية. تتضمن بعض المكتبات الشائعة "binarytree" و"bintrees" و"d3-binarytree". توفر لك هذه المكتبات تنفيذًا جاهزًا للاستخدام ووظائف إضافية للعمل مع الأشجار الثنائية.
6. ما هي التطبيقات العملية للأشجار الثنائية في العالم الحقيقي؟ تُستخدم الأشجار الثنائية في مجموعة متنوعة من التطبيقات في العالم الحقيقي مثل قواعد البيانات وخوارزميات البحث وخوارزميات الضغط، أنظمة الملفات وأكثر من ذلك بكثير. وهي ضرورية لتنظيم البيانات والبحث عنها بكفاءة عبر العديد من الأنظمة والتطبيقات.

اختتام

تُعد الأشجار الثنائية في JavaScript أداة فعالة لتنظيم البيانات ومعالجتها بكفاءة. في هذه المقالة، تعلمت أساسيات الأشجار الثنائية، وكيفية تنفيذها في JavaScript، والعمليات الأساسية والمتقدمة التي يمكنك إجراؤها عليها. بالإضافة إلى ذلك، قمنا باستكشاف بعض أفضل الممارسات والإجابة على الأسئلة الشائعة لمساعدتك في توسيع نطاق معرفتك.

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