რა არის ბინარული ძიების ხე (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
```

## სირთულე

| ოპერაცია | დაბალანსებული | სიცუდე (დეგენერაცია) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

**ყველაზე খराপი შემთხვევა** ხდება მაშინ, როდესაც გასაღებები ჩასმულია დალაგებული თანმიმდევრობით - ხე გადაიქცევა სიმაღლის `n` დაკავშირებული სიაში.

## ვაჭრობა

- **სიძლიერე:** დალაგებული გადაკვეთა O(n)-ში; მხარდაჭერს დიაპაზონის ცნობარი და მემკვიდრე/წინამორბელი.
- **სიცუცხე:** არ აქვს დაბალანსების გარანტია თავისთავად - საჭიროა AVL ან წითელი-შავი ვარიანტი O(log n)-ში დასაყენებლად.

## რატომ არის ეს მნიშვნელოვანი

BST გაძლევთ დალაგებულ, დინამიურ მონაცემებს ლოგარითმული ოპერაციებით - მონაცემთა ბაზის ინდექსების და დალაგებული რუქების კონცეპტუალური წინაპარი.

დეგენერაციის პრობლემა მოტივირებს **თვითდაბალანსირებელ ხეებს**, ინტერვიუში მნიშვნელოვანი მდგომარეობის თემა.