الأشجار الثنائية (Binary Trees) في جافا: شرح شامل ومفصل

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

مفهوم الأشجار الثنائية (Binary Trees)

الأشجار الثنائية هي هياكل بيانات شجرية (Tree Data Structures) تكون فيها كل عقدة (Node) إما عقدة فارغة (null) أو تحتوي على قيمة واحدة بالإضافة إلى مرجعين اثنين (يسمى كل منهما الابن الأيسر Left Child والابن الأيمن Right Child). لا يمكن للعقدة في الشجرة الثنائية أن تحتوي أكثر من طفلين.

الأشجار بشكل عام هي بنية غير خطية حيث كل عنصر يسمى “عقدة”، ويتم تنظيم العقد بشكل هرمي بحيث يوجد عقدة جذر (Root Node) وعقد فرعية. في الأشجار الثنائية، تقتصر عدد الأبناء لكل عقدة على اثنين كحد أقصى.

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

1. الشجرة الثنائية العامة (General Binary Tree)

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

2. الشجرة الثنائية الكاملة (Full Binary Tree)

شجرة حيث كل عقدة إما أن تكون ورقة (Leaf Node) بدون أبناء، أو تحتوي بالضبط على طفلين.

3. الشجرة الثنائية المثالية (Perfect Binary Tree)

شجرة كاملة حيث كل المستويات ممتلئة تمامًا بالعقد. عدد العقد فيها يكون $2^{h+1} – 1$ حيث $h$ هو ارتفاع الشجرة.

4. الشجرة الثنائية المكتملة (Complete Binary Tree)

شجرة يتم فيها ملء جميع المستويات ما عدا الأخير بالكامل من اليسار إلى اليمين.

5. شجرة البحث الثنائية (Binary Search Tree – BST)

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

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

يمكن تمثيل الأشجار الثنائية في جافا باستخدام صف (Class) خاص بالعقد Node يحتوي على البيانات (Data) ومؤشرين للابن الأيسر والأيمن.

هيكل العقدة الأساسية

java
CopyEdit
public class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

في هذا التمثيل، يحتوي كل عقدة على قيمة عددية data، ومؤشرين left و right يشيران إلى الأبناء.

بناء شجرة ثنائية

لإنشاء شجرة، نحتاج إلى صف يحتوي على جذر الشجرة (Root) ويوفر طرقًا لإضافة العقد وتنفيذ العمليات المختلفة.

مثال بسيط لبناء شجرة:

java
CopyEdit
public class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }

    // طريقة لإضافة عقدة جديدة
    public void add(int data) {
        root = addRecursive(root, data);
    }

    private Node addRecursive(Node current, int data) {
        if (current == null) {
            return new Node(data);
        }
        // لإضافة في الشجرة الثنائية العامة - نضيف العقدة في اليسار إذا كانت فارغة، وإلا في اليمين
        if (current.left == null) {
            current.left = addRecursive(current.left, data);
        } else {
            current.right = addRecursive(current.right, data);
        }
        return current;
    }
}

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

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

1. الزيارات (Traversal)

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

أنواع الزيارات الأساسية:

• زيارة ما قبل الترتيب (Pre-order Traversal): زيارة العقدة الحالية، ثم اليسار، ثم اليمين.

• زيارة الترتيب الوسيط (In-order Traversal): زيارة اليسار، ثم العقدة الحالية، ثم اليمين.

• زيارة ما بعد الترتيب (Post-order Traversal): زيارة اليسار، ثم اليمين، ثم العقدة الحالية.

• زيارة حسب المستوى (Level-order Traversal): زيارة العقد حسب مستوى الشجرة من الأعلى للأسفل، وعادة ما تُستخدم مع طابور (Queue).

تطبيق الزيارات في جافا:

java
CopyEdit
// زيارة ما قبل الترتيب
public void preOrderTraversal(Node node) {
    if (node != null) {
        System.out.print(node.data + " ");
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

// زيارة الترتيب الوسيط
public void inOrderTraversal(Node node) {
    if (node != null) {
        inOrderTraversal(node.left);
        System.out.print(node.data + " ");
        inOrderTraversal(node.right);
    }
}

// زيارة ما بعد الترتيب
public void postOrderTraversal(Node node) {
    if (node != null) {
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        System.out.print(node.data + " ");
    }
}

// زيارة حسب المستوى باستخدام طابور
public void levelOrderTraversal(Node root) {
    if (root == null) return;

    Queue nodes = new LinkedList<>();
    nodes.add(root);

    while (!nodes.isEmpty()) {
        Node node = nodes.remove();
        System.out.print(node.data + " ");

        if (node.left != null) {
            nodes.add(node.left);
        }
        if (node.right != null) {
            nodes.add(node.right);
        }
    }
}

2. البحث في الشجرة (Search)

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

البحث في شجرة البحث الثنائية (BST):

java
CopyEdit
public boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    }
    if (value == current.data) {
        return true;
    }
    return value < current.data
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
}

أمثلة متقدمة وتطبيقات عملية

إنشاء شجرة بحث ثنائية (Binary Search Tree)

java
CopyEdit
public class BinarySearchTree {
    Node root;

    public void insert(int value) {
        root = insertRecursive(root, value);
    }

    private Node insertRecursive(Node current, int value) {
        if (current == null) {
            return new Node(value);
        }
        if (value < current.data) {
            current.left = insertRecursive(current.left, value);
        } else if (value > current.data) {
            current.right = insertRecursive(current.right, value);
        } else {
            // القيمة موجودة مسبقًا، لا نسمح بتكرار القيم
            return current;
        }
        return current;
    }

    public boolean contains(int value) {
        return containsNodeRecursive(root, value);
    }

    private boolean containsNodeRecursive(Node current, int value) {
        if (current == null) {
            return false;
        }
        if (value == current.data) {
            return true;
        }
        return value < current.data
          ? containsNodeRecursive(current.left, value)
          : containsNodeRecursive(current.right, value);
    }

    // حذف عقدة
    public void delete(int value) {
        root = deleteRecursive(root, value);
    }

    private Node deleteRecursive(Node current, int value) {
        if (current == null) {
            return null;
        }
        if (value == current.data) {
            // حالة 1: لا يحتوي العقدة على أبناء
            if (current.left == null && current.right == null) {
                return null;
            }
            // حالة 2: يحتوي على ابن واحد فقط
            if (current.right == null) {
                return current.left;
            }
            if (current.left == null) {
                return current.right;
            }
            // حالة 3: يحتوي على ابنين
            int smallestValue = findSmallestValue(current.right);
            current.data = smallestValue;
            current.right = deleteRecursive(current.right, smallestValue);
            return current;
        } 
        if (value < current.data) {
            current.left = deleteRecursive(current.left, value);
            return current;
        }
        current.right = deleteRecursive(current.right, value);
        return current;
    }

    private int findSmallestValue(Node root) {
        return root.left == null ? root.data : findSmallestValue(root.left);
    }
}

تفسير العمليات:

• الإدخال (Insert): يتم وضع القيمة في المكان الصحيح الذي يحافظ على ترتيب الشجرة.

• البحث (Contains): يتم تحديد وجود القيمة عبر مقارنة متكررة في العقد.

• الحذف (Delete): عملية معقدة تشمل حالات مختلفة حسب عدد أبناء العقدة المراد حذفها، مع تعويض مناسب لضمان الحفاظ على ترتيب الشجرة.

تحليل الأداء (Time Complexity)

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

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

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

• شجرة AVL (AVL Tree): تحافظ على توازن الفرق في ارتفاع العقد الفرعية بحيث يكون الفرق بين ارتفاع الفرع الأيسر والفرع الأيمن لا يزيد عن واحد.

• شجرة الأحمر-أسود (Red-Black Tree): شجرة بحث ثنائية ذات خاصية تلوين العقدة لتضمن التوازن بطريقة مرنة.

هذه الأشجار تضمن أداء أفضل في عمليات الإدخال والحذف والبحث.

تطبيق عملي: إنشاء شجرة ثنائية وعرض البيانات

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

java
CopyEdit
public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // إضافة قيم
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);

        // استعراض البيانات بزيارة الترتيب الوسيط (In-order Traversal)
        System.out.print("In-order traversal: ");
        bst.inOrderTraversal(bst.root);  // يجب أن يعرض القيم مرتبة تصاعديًا
    }
}

ملخص وتعريف جدول مقارنة بين أنواع الأشجار الثنائية

خلاصة

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

الاستفادة من التوازن في الأشجار الثنائية مثل أشجار AVL أو الأحمر-أسود تعزز من أداء التطبيقات الحساسة للسرعة، خصوصًا في قواعد البيانات وأنظمة الملفات. مع تنوع الاستخدامات وتعقيدها، تظل الأشجار الثنائية مجالًا واسعًا للبحث والتطوير في علوم الحاسوب.

المصادر

1. Data Structures and Algorithms in Java – Robert Lafore

2. Introduction to Algorithms – Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

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