Τι είναι ένα δυαδικό δέντρο αναζήτησης (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).

## Γιατί έχει σημασία

Τα BST σας δίνουν ταξινομημένα, δυναμικά δεδομένα με λογαριθμικές πράξεις — ο εννοιολογικός προγονός των δεικτών βάσης δεδομένων και των ταξινομημένων χαρτών.

Το πρόβλημα εκφυλισμού προκαλεί **δέντρα αυτοϊσορροπίας**, ένα βασικό θέμα παρακολούθησης σε συνεντεύξεις.

Πράξη	Ισορροπημένο	Χειρότερη περίπτωση (εκφυλισμένο)
αναζήτηση	O(log n)	O(n)
εισαγωγή	O(log n)	O(n)
διαγραφή	O(log n)	O(n)