الشجرة الثنائية

الشجرة الثنائية (binary tree) بنية بيانات غير خطية تصوّر العلاقة الهرمية بين «الأسلاف» و«الأحفاد»، وتتجسد فيها فكرة التقسيم والتغلب التي يتفرع فيها كل انقسام إلى اثنين. وعلى غرار القائمة المترابطة، فإن الوحدة الأساسية في الشجرة الثنائية هي العقدة، وتحتوي كل عقدة على قيمة، ومرجع إلى عقدة ابنها الأيسر، ومرجع إلى عقدة ابنها الأيمن.

/* عقدة الشجرة الثنائية */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
/* دالة البناء */
func NewTreeNode(v int) *TreeNode {
    return &TreeNode{
        Left:  nil, // مؤشر إلى عقدة الابن الأيسر
        Right: nil, // مؤشر إلى عقدة الابن الأيمن
        Val:   v,   // قيمة العقدة
    }
}

/* عقدة الشجرة الثنائية */
class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val; // قيمة العقدة
        this.left = left === undefined ? null : left; // مرجع إلى عقدة الابن الأيسر
        this.right = right === undefined ? null : right; // مرجع إلى عقدة الابن الأيمن
    }
}

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

في الشجرة الثنائية، تمتلك كل عقدة غير ورقية عقداً ابنة، ومن ثم أشجاراً فرعية غير فارغة. وكما يوضح الشكل أدناه، إذا اعتُبرت «العقدة 2» عقدة أب، فإن عقدتي ابنيها الأيسر والأيمن هما «العقدة 4» و«العقدة 5» على التوالي. وتتكون الشجرة الفرعية اليسرى من «العقدة 4» وجميع العقد الواقعة تحتها، بينما تتكون الشجرة الفرعية اليمنى من «العقدة 5» وجميع العقد الواقعة تحتها.

المصطلحات الشائعة للأشجار الثنائية

تظهر المصطلحات الشائعة للأشجار الثنائية في الشكل أدناه.

• عقدة الجذر (root node): العقدة في المستوى الأعلى من الشجرة الثنائية، وهي لا تمتلك عقدة أب.
• العقدة الورقية (leaf node): عقدة لا تمتلك أي عقد ابنة، ويشير مؤشراها معاً إلى None.
• الضلع (edge): قطعة مستقيمة تربط عقدتين، وتمثل مرجعاً (مؤشراً) بين العقدتين.
• مستوى العقدة: يزداد من الأعلى إلى الأسفل، وتكون عقدة الجذر في المستوى 1.
• درجة العقدة: عدد عقد الابن التي تمتلكها العقدة. وفي الشجرة الثنائية، يمكن أن تكون الدرجة 0 أو 1 أو 2.
• ارتفاع الشجرة الثنائية: عدد الأضلاع من عقدة الجذر إلى أبعد عقدة ورقية.
• عمق العقدة: عدد الأضلاع من عقدة الجذر إلى العقدة.
• ارتفاع العقدة: عدد الأضلاع من أبعد عقدة ورقية إلى العقدة.

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

تهيئة شجرة ثنائية

على غرار القائمة المترابطة، تتضمن تهيئة الشجرة الثنائية أولاً إنشاء العقد ثم إقامة المراجع (المؤشرات) بينها.

/* تهيئة شجرة ثنائية */
// تهيئة العقد
n1 := NewTreeNode(1)
n2 := NewTreeNode(2)
n3 := NewTreeNode(3)
n4 := NewTreeNode(4)
n5 := NewTreeNode(5)
// ربط المراجع (المؤشرات) بين العقد
n1.Left = n2
n1.Right = n3
n2.Left = n4
n2.Right = n5

/* تهيئة شجرة ثنائية */
// تهيئة العقد
let n1 = new TreeNode(1),
    n2 = new TreeNode(2),
    n3 = new TreeNode(3),
    n4 = new TreeNode(4),
    n5 = new TreeNode(5);
// ربط المراجع (المؤشرات) بين العقد
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

إدراج العقد وحذفها

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

/* إدراج العقد وحذفها */
// إدراج العقدة P بين n1 وn2
p := NewTreeNode(0)
n1.Left = p
p.Left = n2
// حذف العقدة P
n1.Left = n2

/* إدراج العقد وحذفها */
const P = new TreeNode(0);
// إدراج العقدة P بين n1 وn2
n1.left = P;
P.left = n2;
// حذف العقدة P
n1.left = n2;

الأنواع الشائعة للأشجار الثنائية

الشجرة الثنائية التامة

كما يوضح الشكل أدناه، تكون جميع المستويات في الشجرة الثنائية التامة (perfect binary tree) ممتلئة بالكامل. وفي الشجرة الثنائية التامة، تكون درجة العقد الورقية $0$، بينما تكون درجة جميع العقد الأخرى $2$. وإذا كان ارتفاع الشجرة $h$، فإن العدد الإجمالي للعقد هو $2^{h+1} - 1$، وفق نمط أسي معياري يحاكي ظاهرة انقسام الخلايا الشائعة في الطبيعة.

الشجرة الثنائية الكاملة

كما يوضح الشكل أدناه، لا تسمح الشجرة الثنائية الكاملة (complete binary tree) إلا بأن يكون المستوى السفلي غير ممتلئ امتلاءً كاملاً، ويجب ملء عقد المستوى السفلي باستمرار من اليسار إلى اليمين. ولاحظ أن الشجرة الثنائية التامة هي أيضاً شجرة ثنائية كاملة.

الشجرة الثنائية الممتلئة

كما يوضح الشكل أدناه، في الشجرة الثنائية الممتلئة (full binary tree)، تمتلك جميع العقد باستثناء العقد الورقية عقدتي ابن.

الشجرة الثنائية المتوازنة

كما يوضح الشكل أدناه، في الشجرة الثنائية المتوازنة (balanced binary tree)، لا يتجاوز الفرق المطلق بين ارتفاع الشجرتين الفرعيتين اليسرى واليمنى لأي عقدة 1.

تدهور الأشجار الثنائية

يقابل الشكل أدناه البنى المثالية والبنى المتدهورة للأشجار الثنائية. فعندما يمتلئ كل مستوى، تصبح الشجرة «شجرة ثنائية تامة»؛ وعندما تنحرف جميع العقد إلى جهة واحدة، تتدهور الشجرة الثنائية إلى «قائمة مترابطة».

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

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

جدول   أفضل بنى الأشجار الثنائية وأسوأها