ต้นไม้ค้นหาแบบไบนารี (BST) คืออะไร และมีความซับซ้อนของการดำเนินการอย่างไร

Question

IT Interview Practice · 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)

คุณสมบัติเรียงลำดับ

การค้นหาและการแทรก

ความซับซ้อน

การแลกเปลี่ยน

เหตุใดจึงสำคัญ

คำถามที่เกี่ยวข้อง