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

مقدمة عملية إلى شجرة البحث الثنائية

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

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

ما هي شجرة البحث الثنائية BST؟

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

• كل عقدة في الجهة اليسرى يجب أن تحمل قيمة أصغر من قيمة العقدة الأب.
• كل عقدة في الجهة اليمنى يجب أن تحمل قيمة أكبر من قيمة العقدة الأب.
• كل عقدة يمكن أن تمتلك صفراً أو ابناً واحداً أو ابنين كحد أقصى.

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

لماذا تُعد مهمة للمبرمجين المبتدئين؟

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

تعريف عقدة الشجرة في JavaScript

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

function TreeNode ( val, left, right ) {
  this.val = val
  this.left = left
  this.right = right
}

في هذا التعريف:

• val تمثل القيمة المخزنة داخل العقدة.
• left تشير إلى العقدة الموجودة في الجهة اليسرى.
• right تشير إلى العقدة الموجودة في الجهة اليمنى.

طرق اجتياز شجرة البحث الثنائية

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

أشهر طرق الاجتياز في شجرة البحث الثنائية ثلاث:

• Inorder
• Postorder
• Preorder

اجتياز Inorder

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

/**
 * @param {TreeNode} root
 */
const inorder = ( root ) => {
  const nodes = []
  if (root) {
    inorder(root.left)
    nodes.push(root.val)
    inorder(root.right)
  }
  return nodes
}

// for our example tree, this returns [1,2,3,4,5,6]

كيف يعمل Inorder؟

1. إذا كانت العقدة الحالية فارغة null فلا نفعل شيئاً.
2. ننتقل أولاً إلى الابن الأيسر بشكل متكرر.
3. بعد الوصول إلى أقصى يسار ممكن، نعالج العقدة الحالية.
4. ثم ننتقل إلى الابن الأيمن.

هذا الأسلوب ممتاز عندما تحتاج إلى استخراج عناصر الشجرة بترتيب مرتب.

اجتياز Postorder

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

/**
 * @param {TreeNode} root
 */
const postorder = ( root ) => {
  const nodes = []
  if (root) {
    postorder(root.left)
    postorder(root.right)
    nodes.push(root.val)
  }
  return nodes
}

// for our example tree, this returns [1,3,2,6,5,4]

متى يكون Postorder مفيداً؟

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

اجتياز Preorder

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

/**
 * @param {TreeNode} root
 */
const preorder = ( root ) => {
  const nodes = []
  if (root) {
    nodes.push(root.val)
    preorder(root.left)
    preorder(root.right)
  }
  return nodes
}

// for our example tree, this returns [4,2,1,3,5,6]

فائدة Preorder في التطبيقات العملية

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

مقارنة سريعة بين أنواع الاجتياز

كيف تتحقق من أن الشجرة هي Valid BST؟

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

لهذا السبب لا يكفي أن تقارن العقدة بأبنائها فقط، بل يجب أن تتأكد من أن كل عقدة تقع ضمن نطاق صحيح من القيم المسموح بها.

/**
 * @param {TreeNode} root
 */
const isValidBST = ( root ) => {
  const helper = ( node, min, max ) => {
    if (!node) return true
    if (node.val <= min || node.val >= max) return false
    return helper(node.left, min, node.val) && helper(node.right, node.val, max)
  }
  return helper(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
}

فكرة الخوارزمية

1. نمرر مع كل عقدة حداً أدنى min وحداً أقصى max.
2. إذا خرجت قيمة العقدة عن هذا النطاق، فالشجرة غير صالحة.
3. عند النزول يساراً، يصبح الحد الأقصى هو قيمة العقدة الحالية.
4. عند النزول يميناً، يصبح الحد الأدنى هو قيمة العقدة الحالية.

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

حساب أقصى عمق في الشجرة الثنائية

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

/**
 * @param {TreeNode} root
 */
const maxDepth = function ( root ) {
  const calc = ( node ) => {
    if (!node) return 0
    return Math.max(1 + calc(node.left), 1 + calc(node.right))
  }
  return calc(root)
};

شرح سريع لآلية العمل

• إذا كانت العقدة فارغة، فعمقها يساوي 0.
• إذا كانت موجودة، نحسب عمق الفرع الأيسر وعمق الفرع الأيمن.
• نختار القيمة الأكبر بينهما ثم نضيف 1 للعقدة الحالية.

بهذا نحصل في النهاية على ارتفاع الشجرة بالكامل.

إيجاد السلف المشترك الأدنى بين عقدتين

السلف المشترك الأدنى أو Lowest Common Ancestor هو أقرب عقدة مشتركة يمكن الوصول منها إلى عقدتين داخل الشجرة. ويُختصر غالباً بالرمز LCA.

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

متى نعتبر أننا وجدنا LCA؟

• إذا وُجدت عقدة في الفرع الأيسر وأخرى في الفرع الأيمن للعقدة الحالية.
• أو إذا كانت العقدة الحالية نفسها تمثل إحدى العقدتين، بينما تقع الأخرى في أحد الفروع التابعة لها.

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 */
const lowestCommonAncestor = function ( root, p, q ) {
  let lca = null

  const isCommonPath = ( node ) => {
    if (!node) return false

    var isLeft = isCommonPath(node.left)
    var isRight = isCommonPath(node.right)
    var isMid = node == p || node == q

    if (isMid && isLeft || isMid && isRight || isLeft && isRight) {
      lca = node
    }

    return isLeft || isRight || isMid
  }

  isCommonPath(root)
  return lca
};

لماذا هذه الخوارزمية مهمة؟

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

نصائح لفهم خوارزميات الشجرة بشكل أفضل

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

الخلاصة التقنية

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