ما هي شجرة البحث الثنائية (BST) وما هي تعقيدات عملياتها؟

Question

Accepted Answer

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

## الخاصية الثابتة

```text
        8
       / \
      3    10
     / \     \
    1   6     14     left < node < right at every node
```

## البحث والإدراج

```python
def search(node, key):
    while node:
        if key == node.val: return node
        node = node.left if key < node.val else node.right  # go one way
    return None

def insert(node, key):
    if node is None: return Node(key)
    if key < node.val: node.left  = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node
```

## التعقيد

| العملية | متوازنة | الأسوأ (متدهورة) |
|---|---|---|
| بحث | O(log n) | O(n) |
| إدراج | O(log n) | O(n) |
| حذف | O(log n) | O(n) |

**الحالة الأسوأ** تحدث عندما يتم إدراج المفاتيح بترتيب مرتب — الشجرة تتدهور إلى قائمة مرتبطة بارتفاع `n`.

## المقارنات

- **المزايا:** الاجتياز المرتب في O(n)؛ يدعم استعلامات النطاق والخليفة/السلف.
- **العيوب:** لا توجد ضمانة توازن بمفردها — تحتاج إلى متغير AVL أو red-black للبقاء في O(log n).

## لماذا يهم

شجرة البحث الثنائية تعطيك بيانات ديناميكية مرتبة مع عمليات لوغاريتمية — السلف المفاهيمي لفهارس قواعد البيانات والخرائط المرتبة.

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