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

لماذا نستخدم شجرة البحث الثنائية؟
تقدم BSTs العديد من المزايا:

البحث الفعال: متوسط ​​التعقيد الزمني هو O(log n) للبحث والإدراج والحذف.
مجموعة العناصر الديناميكية: تدعم العمليات الديناميكية، على عكس المصفوفات الثابتة.
العناصر المرتبة: يؤدي اجتياز BST بالترتيب إلى ظهور عناصر مرتبة.
دليل خطوة بخطوة لبناء BST
الخطوة 1: تحديد بنية العقدة
الخطوة الأولى هي تحديد بنية العقدة في الشجرة. سيكون لكل عقدة ثلاث سمات: قيمة، وإشارة إلى الطفل الأيسر، وإشارة إلى الطفل الأيمن.

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

الخطوة 2: إنشاء فئة BST باستخدام المُنشئ
بعد ذلك، نقوم بإنشاء فئة BST التي تحتوي على مرجع إلى جذر الشجرة وطرق إدراج العناصر.

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }
}

الخطوة 3: تنفيذ طريقة الإدراج
لإدراج عنصر في BST، نحتاج إلى العثور على الموضع الصحيح للعقدة الجديدة. عادة ما يتم تنفيذ طريقة الإدراج كدالة متكررة.

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

private TreeNode insertRec(TreeNode root, int value) {
    // Base case: if the tree is empty, return a new node
    if (root == null) {
        root = new TreeNode(value);
        return root;
    }

    // Otherwise, recur down the tree
    if (value  root.value) {
        root.right = insertRec(root.right, value);
    }

    // Return the (unchanged) node pointer
    return root;
}

التصور
لفهم كيفية عمل الإدراج بشكل أفضل، دعونا نفكر في مثال. لنفترض أننا نريد إدراج التسلسل التالي من الأرقام في BST: 50، 30، 70، 20، 40، 60، 80.

50

  50
 /
30

  50
 /  \
30  70

50
 /  \
30  70
/

أدخل 40:

  50
 /  \
30  70
/ \

أدخل 60

  50
 /  \
30  70
/ \  /

أدخل 80:

  50
 /  \
30  70
/ \  / \

الكود الكامل
إليك الكود الكامل لإنشاء BST وإدراج العناصر:

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

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

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value  root.value) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Additional methods for traversal, search, and delete can be added here

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }

        // Add code to print or traverse the tree
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}