ملخص Tree للمقابلات البرمجية

مقدمة

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

الـTree هي Graph غير موجه ومتصل وخالٍ من الدورات. لا توجد فيها دورات أو حلقات. ويمكن لكل عقدة أن تكون كالعقدة الجذر لشجرتها الفرعية الخاصة، مما يجعل الـRecursion تقنية مفيدة لاجتياز الـTrees.

لأغراض المقابلات، سيُطلب منك عادةً التعامل مع الـTrees الثنائية بدلاً من الـTrees الثلاثية (3 أبناء) أو N-ية (N ابناً). في هذه الصفحة سنتناول الـTrees الثنائية وBinary Search Trees، وهي حالة خاصة من الـTrees الثنائية.

تُستخدم الـTrees عادةً لتمثيل البيانات الهرمية، مثل أنظمة الملفات ومستندات JSON وHTML. اطّلع أيضاً على قسم Trie، وهي Tree متقدمة تُستخدم للتخزين الفعال للسلاسل النصية والبحث فيها.

مصادر التعلم

• فيديوهات
  • Trees، University of California San Diego
  • A Brief Guide to Binary Search Trees (الشرائح)، Samuel Albanie، University of Cambridge
  • A Brief Guide to Red-Black Trees (الشرائح)، Samuel Albanie، University of Cambridge
  • A Brief Guide to B-trees (الشرائح)، Samuel Albanie، University of Cambridge
• قراءات
  • How To Not Be Stumped By Trees، basecs
  • Leaf It Up To Binary Trees، basecs
• إضافية (فقط إذا كان لديك وقت)
  • The Little AVL Tree That Could، basecs
  • Busying Oneself With B-Trees، basecs
  • Painting Nodes Black With Red-Black Trees، basecs

مصطلحات شائعة تحتاج إلى معرفتها

• الجار — والد العقدة أو ابنها
• السلف — عقدة يمكن الوصول إليها باجتياز سلسلة الوالدين
• الخلف — عقدة في الـTree الفرعية للعقدة
• الدرجة — عدد أبناء العقدة
• درجة الـTree — أقصى درجة للعقد في الـTree
• المسافة — عدد الحواف على طول أقصر مسار بين عقدتين
• المستوى/العمق — عدد الحواف على طول المسار الفريد بين عقدة والعقدة الجذر
• العرض — عدد العقد في مستوى ما

الـTree الثنائية

ثنائي تعني اثنان، لذا فإن العقد في الـTree الثنائية لها ابنان كحد أقصى.

مصطلحات الـTree الثنائية

• الـTree الثنائية المكتملة — هي Tree ثنائية يكون فيها كل مستوى، باستثناء الأخير ربما، ممتلئاً تماماً، وتكون جميع العقد في المستوى الأخير في أقصى اليسار قدر الإمكان.
• الـTree الثنائية المتوازنة — بنية Tree ثنائية تختلف فيها الشجرتان الفرعيتان اليسرى واليمنى لكل عقدة في الارتفاع بما لا يزيد عن 1.

الاجتيازات

لمثل هذه الـTree، هذه هي نتائج الاجتيازات المختلفة.

• الاجتياز بالترتيب الداخلي (In-order) — يسار ← جذر ← يمين
  • النتيجة: 2، 7، 5، 6، 11، 1، 9، 5، 9
• الاجتياز بالترتيب السابق (Pre-order) — جذر ← يسار ← يمين
  • النتيجة: 1، 7، 2، 6، 5، 11، 9، 9، 5
• الاجتياز بالترتيب اللاحق (Post-order) — يسار ← يمين ← جذر
  • النتيجة: 2، 5، 11، 6، 7، 5، 9، 9، 1

لاحظ أن الاجتياز بالترتيب الداخلي لـTree ثنائية غير كافٍ لإجراء تسلسل فريد للـTree. فالاجتياز بالترتيب السابق أو اللاحق مطلوب أيضاً.

Binary Search Tree (BST)

الاجتياز بالترتيب الداخلي لBinary Search Tree سيعطيك جميع العناصر مرتبة.

كن على دراية تامة بخصائص Binary Search Tree والتحقق من أن Tree ثنائية هي Binary Search Tree. يظهر هذا أكثر مما هو متوقع.

عندما يتضمن السؤال Binary Search Tree، يبحث المحاور عادةً عن حل أسرع من O(n).

الـtime complexity

الـspace complexity لاجتياز الـTrees المتوازنة هو O(h) حيث h ارتفاع الـTree، بينما اجتياز الـTrees شديدة الانحراف (التي هي في جوهرها Linked List) سيكون O(n).

أمور يجب الانتباه إليها أثناء المقابلات

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

الحالات الحدّية

• Tree فارغة
• عقدة واحدة
• عقدتان
• Tree شديدة الانحراف (كالـLinked List)

إجراءات شائعة

كن على دراية بالإجراءات التالية لأن العديد من أسئلة الـTrees تستخدم واحداً أو أكثر منها في الحل:

• إدراج قيمة
• حذف قيمة
• عدّ عدد العقد في الـTree
• ما إذا كانت قيمة موجودة في الـTree
• حساب ارتفاع الـTree
• Binary Search Tree
  • تحديد ما إذا كانت Binary Search Tree
  • إيجاد القيمة العظمى
  • إيجاد القيمة الصغرى

تقنيات

استخدم الـRecursion

الـRecursion هي الأسلوب الأكثر شيوعاً لاجتياز الـTrees. عندما تلاحظ أن مسألة الـTree الفرعية يمكن استخدامها لحل المسألة بأكملها، جرّب استخدام الـRecursion.

عند استخدام الـRecursion، تذكر دائماً فحص حالة الأساس، وهي عادةً حيث تكون العقدة null.

أحياناً قد تحتاج دالتك الـRecursion إلى إعادة قيمتين.

الاجتياز بالمستوى

عندما يُطلب منك اجتياز Tree مستوى بمستوى، استخدم BFS.

جمع العقد

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

أسئلة أساسية

هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.

• الـTree الثنائية
  • Maximum Depth of Binary Tree
  • Invert/Flip Binary Tree
• Binary Search Tree
  • Lowest Common Ancestor of a Binary Search Tree

أسئلة تدريب موصى بها

هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.

• الـTree الثنائية
  • Same Tree
  • Binary Tree Maximum Path Sum
  • Binary Tree Level Order Traversal
  • Lowest Common Ancestor of a Binary Tree
  • Binary Tree Right Side View
  • Subtree of Another Tree
  • Construct Binary Tree from Preorder and Inorder Traversal
  • Serialize and Deserialize Binary Tree
• Binary Search Tree
  • Validate Binary Search Tree
  • Kth Smallest Element in a BST

المصدر والرخصة

هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.